Лінійний конгруентний метод
Лінійний конгруентний метод — один із методів генерації псевдовипадкових чисел. Застосовується в простих випадках і не володіє криптографічною стійкістю. Входить в стандартні бібліотеки різних компіляторів.
Опис
Лінійний конгруентний метод був запропонований Д. Г. Лемером в 1949 році.[1] Суть методу полягає в обчисленні послідовності випадкових чисел , вважаючи
де — модуль (натуральне число, відносно якого обчислюють остачу від ділення; ), — множник ( ), — приріст ( ), — початкове значення ( ).
Ця послідовність називається лінійною конгруентною послідовністю. Наприклад, для отримаємо послідовність [2]:21—37</ref>
Властивості
Лінійна конгруентна послідовність, визначена числами , , і періодична з періодом, не більшим за . При цьому довжина періоду рівна тоді і тільки тоді, коли[2]:21—37:
- Числа і взаємно прості;
- кратно для кожного простого , що є дільником ;
- кратно , якщо кратно .
Наявність цієї властивості для випадку , де — число бітів в машинному слові, було доведено М. Грінбергом (англ. M. Greenberg).[3] Наявність цієї властивості для загального випадку і достатність умов були доведені Т. Е. Халлом (англ. T. E. Hull) і А. Р. Добеллом (англ. A. R. Dobell).[4]
Метод генерації лінійної конгруентної послідовності при називають мультиплікативним конгруентним методом, а при — змішаним конгруентним методом. При згенеровані числа будуть мати менший період, ніж при , але при певних умовах можна отримати період довжиною , якщо — просте число. Той факт, що умова може призводити до появи більш довгих періодів, був встановлений В. Е. Томсоном (англ. W. T. Thomson) і незалежно від нього А. Ротенбергом (англ. A. Rotenberg).[2]Щоб гарантувати максимальність циклу повторення послідовності при , необхідно в якості значення параметра обирати просте число. Найвідомішим генератором подібного типу є так званий мінімальний стандартний генератор випадкових чисел, запропонований Стівеном Парком (англ. Stephen Park) і Кейтом Міллером (англ. Keith Miller) в 1988 році. Для нього , а .[5][6]
Методом генерації послідовностей псевдовипадкових чисел, що найчастіше використовують є змішаний конгруентний метод.[джерело не вказане 2530 днів]
Параметри, що часто використовуються
При виборі числа необхідно враховувати наступні умови:
- число повинно бути достатньо великим, так як період не може мати більше ніж елементів;
- значення числа повинно бути таким, щоб обчислювалось швидко.
На практиці при реалізації методу виходячи з вказаних умов частіше всього обирають , де — число бітів в машинному слові. При цьому варто враховувати, що молодші двійкові розряди згенерованих таким чином випадкових чисел демонструють поведінку, далеку від випадкової, тому рекомендується використовувати лише старші розряди. Подібна ситуація не виникає, коли , де — довжина машинного слова. В такому випадку молодші розряди поводять себе так же випадково, як і старші.[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].
Див. також
- Генератор псевдовипадкових чисел
- Інверсний конгруентний метод
Джерела
Посилання
- Л. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел. — Безопасность информационных технологий, 2005. — № 2. — С. 27-38.