Лінійний конгруентний метод

Лінійний конгруентний метод — один із методів генерації псевдовипадкових чисел. Застосовується в простих випадках і не володіє криптографічною стійкістю. Входить в стандартні бібліотеки різних компіляторів.

ОписРедагувати

Лінійний конгруентний метод був запропонований Д. Г. Лемером в 1949 році.[1] Суть методу полягає в обчисленні послідовності випадкових чисел  , вважаючи

 

де   — модуль (натуральне число, відносно якого обчислюють остачу від ділення;  ),   — множник ( ),   — приріст ( ),   — початкове значення ( ).

Ця послідовність називається лінійною конгруентною послідовністю. Наприклад, для   отримаємо послідовність  [2]:21—37</ref>

ВластивостіРедагувати

Лінійна конгруентна послідовність, визначена числами  ,  ,   і   періодична з періодом, не більшим за  . При цьому довжина периоду рівна   тоді і тільки тоді, коли[2]:21—37:

  1. Числа   і   взаємно прості;
  2.   кратно   для кожного простого  , що є дільником  ;
  3.   кратно  , якщо   кратно  .

Наявність цієї властивості для випадку  , де   — число бітів в машинному слові, було доведено М. Грінбергом (англ. M. Greenberg).[3] Наявність цієї властивості для загального випадку і достатність умов були доведені Т. Е. Халлом (англ. T. E. Hull) і А. Р. Добеллом (англ. A. R. Dobell).[4]

Метод генерації лінійної конгруентної послідовності при   називають мультиплікативним конгруентним методом, а при  змішаним конгруентним методом. При   згенеровані числа будуть мати менший період, ніж при  , али при певних умовах можна отримати період довжиною  , якщо   — просте число. Той факт, що умова   може призводити до появи більш довгих періодів, був встановлений В. Е. Томсоном (англ. W. T. Thomson) і незалежно від нього А. Ротенбергом (англ. A. Rotenberg).[2] Щоб гарантувати максимальність циклу повторення послідовності при  , необхідно в якості значення параметра   обирати просте число. Найвідомішим генератором подібного типу є так званий мінімальний стандартний генератор випадкових чисел, запропонований Стівеном Парком (англ. Stephen Park) і Кейтом Міллером (англ. Keith Miller) в 1988 році. Для нього  , а  .[5][6]

Методом генерації послідовностей псевдовипадкових чисел, що найчастіше використовують є змішаний конгруентний метод.[джерело не вказане 904 дні]

Параметри, що часто використовуютьсяРедагувати

При виборі числа   необхідно враховувати наступні умови:

  1. число   повинно бути достатньо великим, так як період не може мати більше ніж   елементів;
  2. значення числа   повинно бути таким, щоб   обчислювалось швидко.

На практиці при реалізації методу виходячи з вказаних умов частіше всього обирають  , де   — число бітів в машинному слові. При цьому варто враховувати, що молодші двійкові розряди згенерованих таким чином випадкових чисел демонструють поведінку, далеку від випадкової, тому рекомендується використовувати лише старші розряди. Подібна ситуація не виникає, коли  , де   — довжина машинного слова. В такому випадку молодші розряди   поводять себе так же випадково, як і старші.[2] Вибір множника   і приросту   зазвичай обумовлений необхідністю виконання умови досягнення періоду максимальної довжини.

Таблиця хороших констант для лінійних конгруентних генераторів 

Всі наведені константи забезпечують роботу генератора з максимальним періодом. Таблиця упорядкована по максимальному добутку, яке не викликає переповнення в слові заданої довжини.[7]

Переповнюється при a c m
220 106 1283 6075
221 211 1663 7875
222 421 1663 7875
223 430 2531 11979
223 936 1399 6655
223 1366 1283 6075
224 171 11213 53125
224 859 2531 11979
224 419 6173 29282
224 967 3041 14406
225 141 28411 134456
225 625 6571 31104
225 1541 2957 14000
225 1741 2731 12960
225 1291 4621 21870
225 205 29573 139968
226 421 17117 81000
226 1255 6173 29282
226 281 28411 134456
227 1093 18257 86436
227 421 54773 259200
227 1021 24631 116640
228 1277 24749 117128
228 2041 25673 121500
229 2311 25367 120050
229 1597 51749 244944
229 2661 36979 175000
229 4081 25673 121500
229 3661 30809 145800
230 3877 29573 139968
230 3613 45289 214326
230 1366 150889 714025
231 8121 28411 134456
231 4561 51349 243000
231 7141 54773 259200
232 9301 49297 233280
232 4096 150889 714025
233 2416 374441 1771875
234 17221 107839 510300
234 36261 66037 312500
235 84589 45989 217728

Відомий «невдалий» (с точки зору якості вихідної послідовності) алгоритм RANDU, що протягом багатьох десятиліть використовували в різних компіляторах.

Для покращення статистичних властивостей числової послідовності в багатьох генераторах псевдовипадкових чисел використовується лише частина бітів результату. Наприклад, в стандарті ISO/IEC 9899 на мові Сі приведений (але не вказаний в якості обов'язкового) приклад функції rand(), що примусово відкидає молодші 16 і один старший розряд.

#define RAND_MAX 32767 

static unsigned long int next = 1;

int rand(void)
{
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) % (RAND_MAX + 1);
}

void srand(unsigned int seed)
{
  next = seed;
}

Саме в такому вигляді функція rand() використовується в компіляторах Watcom C/C++. Відомі числові параметри інших алгоритмів, що застосовуються в різних компіляторах і бібліотеках.

Source m множник a доданок c використані біти
Numerical Recipes[8] 232 1664525 1013904223
Borland C/C++ 232 22695477 1 bits 30..16 in rand(), 30..0 in lrand()
glibc (used by GCC)[9] 231 1103515245 12345 bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ [10] 231 1103515245 12345 bits 30..16
C99, C11: Suggestion in the ISO/IEC 9899 [11] 232 1103515245 12345 bits 30..16
Borland Delphi, Virtual Pascal 232 134775813 1 bits 63..32 of (seed * L)
Microsoft Visual/Quick C/C++ 232 214013 (343FD16) 2531011 (269EC316) bits 30..16
Microsoft Visual Basic (6 and earlier)[12] 224 1140671485 (43FD43FD16) 12820163 (C39EC316)
RtlUniform from Native API[13] 231 − 1 2147483629 (7FFFFFED16) 2147483587 (7FFFFFC316)
Apple CarbonLib, C++11's minstd_rand0[14] 231 − 1 16807 0 see MINSTD
C++11's minstd_rand[14] 231 − 1 48271 0 see MINSTD
MMIX by Donald Knuth 264 6364136223846793005 1442695040888963407
Newlib 264 6364136223846793005 1 bits 63...32
VAX's MTH$RANDOM,[15] old versions of glibc 232 69069 1
Java 248 25214903917 11 bits 47...16
Раніше в багатьох компіляторах:
RANDU 231   65539 0

Можливість використання в криптографіїРедагувати

Хоча лінійний конгруентний метод породжує статистично хорошу псевдовипадкову послідовність чисел, він не є криптографічно стійким. Генератори на основі лінійного конгруентного методу передбачувані, тому їх не можна використовувати в криптографії. Вперше генератори на основі лінійного конгруентного методу були зламані Джимом Рідсом (Jim Reeds), а потім Джоан Бояр (Joan Boyar). Їй вдалося також виявити недоліки квадратичних і кубічних генераторів. Інші дослідники розширили ідеї Бояр, розробивши способи виявлення недоліків будь-якого поліноміального генератора. Таким чином, було доведено, що генератори на основі конгруентних методів не підходять для використання в криптографії. Однак генератори на основі лінійного конгруентного методу зберігають свою корисність для некриптографічних додатків, наприклад, для моделювання. Вони ефективні і в найбільш використовуваних емпіричних тестах демонструють хороші статистичні характеристики[7].

Див. такожРедагувати

ДжерелаРедагувати

  1. D. H. Lehmer, Mathematical methods in large-scale computing units, Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 1949, Harvard University Press, Cambridge, Mass., 1951, pp. 141—146. MR 0044899 (13,495f)[1]
  2. а б в г Дональд Кнут. Искусство программирования = The Art of Computer Programming. — 3-е изд. — Москва : Вільямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 прим. — ISBN 5-8459-0081-6 (рус.) ISBN 0-201-89684-2 (англ.).
  3. M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177—179.[2]
  4. T.E. Hull and A.R. Dobell «Random Number Generators»,SIAM Review 4-3(1962),230-254 [3]
  5. Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. — Delphi Informant Magazine, 2002.
  6. Stephen K. Park; Keith W. Miller (1988). Random Number Generators: Good Ones Are Hard To Find. Communications of the ACM (en) 31 (10): 1192–1201. 
  7. а б Брюс Шнайєр. Прикладная криптография. — Триумф, 2002. — С. 275. Архівовано з джерела 28 лютого 2014
  8. Numerical recipies in C. The art of scientific computing (вид. 2-nd edition). Cambridge University Press. 1992. 
  9. The GNU C library's rand() in stdlib.h uses a simple (single state) linear congruential generator only in case that the state is declared as 8 bytes. If the state is larger (an array), the generator becomes an additive feedback generator and the period increases. See the simplified code that reproduces the random sequence from this library.
  10. A collection of selected pseudorandom number generators with linear structures, K. Entacher, 1997. Процитовано 16 June 2012. 
  11. Last public Committee Draft from April 12, 2011, page 346f. Процитовано 21 Dec 2014. 
  12. How Visual Basic Generates Pseudo-Random Numbers for the RND Function. Microsoft Support. Microsoft. Процитовано 17 June 2011. 
  13. In spite of documentation on MSDN, RtlUniform uses LCG, and not Lehmer's algorithm, implementations before Windows Vista are flawed, because the result of multiplication is cut to 32 bits, before modulo is applied
  14. а б ISO/IEC 14882:2011. ISO. 2 September 2011. Процитовано 3 September 2011. 
  15. GNU Scientific Library: Other random number generators

ПосиланняРедагувати