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

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

Опис

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

X_{n+1}=(aX_{n}+c)~~{\bmod {~}}~m,

де $m$ — модуль (натуральне число, відносно якого обчислюють остачу від ділення; $m\geqslant 2$ ), $a$ — множник ( $0\leqslant a<m$ ), $c$ — приріст ( $0\leqslant c<m$ ), $X_{0}$ — початкове значення ( $0\leqslant X_{0}<m$ ).

Ця послідовність називається лінійною конгруентною послідовністю. Наприклад, для $m=10,X_{0}=a=c=7$ отримаємо послідовність $7,6,9,0,7,6,9,0,\dots$ ^[2]^:21—37

Властивості

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

Числа $c$ і $m$ взаємно прості;
$b=a-1$ кратно $p$ для кожного простого $p$ , що є дільником $m$ ;
$b$ кратно $4$ , якщо $m$ кратно $4$ .

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

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

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

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

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

число $m$ повинно бути достатньо великим, так як період не може мати більше ніж $m$ елементів;
значення числа $m$ повинно бути таким, щоб $(aX_{n}+c)\mod m$ обчислювалось швидко.

На практиці при реалізації методу виходячи з вказаних умов частіше всього обирають $m=2^{e}$ , де $e$ — число бітів в машинному слові. При цьому варто враховувати, що молодші двійкові розряди згенерованих таким чином випадкових чисел демонструють поведінку, далеку від випадкової, тому рекомендується використовувати лише старші розряди. Подібна ситуація не виникає, коли $m=w\pm 1$ , де $w$ — довжина машинного слова. В такому випадку молодші розряди $X_{n}$ поводять себе так же випадково, як і старші.^[2] Вибір множника $a$ і приросту $c$ зазвичай обумовлений необхідністю виконання умови досягнення періоду максимальної довжини.

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

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

Переповнюється при	a	c	m
2²⁰	106	1283	6075
2²¹	211	1663	7875
2²²	421	1663	7875
2²³	430	2531	11979
2²³	936	1399	6655
2²³	1366	1283	6075
2²⁴	171	11213	53125
2²⁴	859	2531	11979
2²⁴	419	6173	29282
2²⁴	967	3041	14406
2²⁵	141	28411	134456
2²⁵	625	6571	31104
2²⁵	1541	2957	14000
2²⁵	1741	2731	12960
2²⁵	1291	4621	21870
2²⁵	205	29573	139968
2²⁶	421	17117	81000
2²⁶	1255	6173	29282
2²⁶	281	28411	134456
2²⁷	1093	18257	86436
2²⁷	421	54773	259200
2²⁷	1021	24631	116640
2²⁸	1277	24749	117128
2²⁸	2041	25673	121500
2²⁹	2311	25367	120050
2²⁹	1597	51749	244944
2²⁹	2661	36979	175000
2²⁹	4081	25673	121500
2²⁹	3661	30809	145800
2³⁰	3877	29573	139968
2³⁰	3613	45289	214326
2³⁰	1366	150889	714025
2³¹	8121	28411	134456
2³¹	4561	51349	243000
2³¹	7141	54773	259200
2³²	9301	49297	233280
2³²	4096	150889	714025
2³³	2416	374441	1771875
2³⁴	17221	107839	510300
2³⁴	36261	66037	312500
2³⁵	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]	2³²	1664525	1013904223
Borland C/C++	2³²	22695477	1	bits 30..16 in rand(), 30..0 in lrand()
glibc (used by GCC)^[9]	2³¹	1103515245	12345	bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++^[10]	2³¹	1103515245	12345	bits 30..16
C99, C11: Suggestion in the ISO/IEC 9899^[11]	2³²	1103515245	12345	bits 30..16
Borland Delphi, Virtual Pascal	2³²	134775813	1	bits 63..32 of (seed L)*
Microsoft Visual/Quick C/C++	2³²	214013 (343FD₁₆)	2531011 (269EC3₁₆)	bits 30..16
Microsoft Visual Basic (6 and earlier)^[12]	2²⁴	1140671485 (43FD43FD₁₆)	12820163 (C39EC3₁₆)
RtlUniform from Native API^[13]	2³¹ − 1	2147483629 (7FFFFFED₁₆)	2147483587 (7FFFFFC3₁₆)
Apple CarbonLib, C++11's `minstd_rand0`^[14]	2³¹ − 1	16807	0	see MINSTD
C++11's `minstd_rand`^[14]	2³¹ − 1	48271	0	see MINSTD
MMIX by Donald Knuth	2⁶⁴	6364136223846793005	1442695040888963407
Newlib	2⁶⁴	6364136223846793005	1	bits 63...32
VAX's MTH$RANDOM,^[15] old versions of glibc	2³²	69069	1
Java	2⁴⁸	25214903917	11	bits 47...16
Раніше в багатьох компіляторах:
RANDU	2³¹	65539	0

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

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

Див. також

Джерела

↑ 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] [Архівовано 24 грудня 2013 у Wayback Machine.]
↑ ^а ^б ^в ^г Дональд Кнут. Seminumerical Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 2. — 762 с. — ISBN 0-201-89684-2.(англ.)
↑ M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177—179.[2] [Архівовано 24 грудня 2013 у Wayback Machine.]
↑ T.E. Hull and A.R. Dobell «Random Number Generators»,SIAM Review 4-3(1962),230-254 [3] [Архівовано 24 грудня 2013 у Wayback Machine.]
↑ Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. — Delphi Informant Magazine, 2002.
↑ Stephen K. Park; Keith W. Miller (1988). Random Number Generators: Good Ones Are Hard To Find (PDF). Communications of the ACM (англ.). 31 (10): 1192—1201. Архів оригіналу (PDF) за 20 березня 2018. Процитовано 26 грудня 2017.
↑ ^а ^б Брюс Шнайєр. Прикладная криптография. — Триумф, 2002. — С. 275. Архівовано з джерела 28 лютого 2014
↑ Numerical recipies in C. The art of scientific computing (вид. 2-nd edition). Cambridge University Press. 1992.
↑ 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 [Архівовано 2 лютого 2015 у Wayback Machine.] that reproduces the random sequence from this library.
↑ A collection of selected pseudorandom number generators with linear structures, K. Entacher, 1997. Архів оригіналу за 5 червня 2013. Процитовано 16 червня 2012.
↑ Last public Committee Draft from April 12, 2011, page 346f (PDF). Архів оригіналу (PDF) за 29 березня 2018. Процитовано 21 грудня 2014.
↑ How Visual Basic Generates Pseudo-Random Numbers for the RND Function. Microsoft Support. Microsoft. Архів оригіналу за 17 квітня 2011. Процитовано 17 червня 2011.
↑ In spite of documentation on MSDN [Архівовано 8 березня 2016 у Wayback Machine.], 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
↑ ^а ^б ISO/IEC 14882:2011. ISO. 2 September 2011. Архів оригіналу за 29 січня 2013. Процитовано 3 September 2011.
↑ GNU Scientific Library: Other random number generators. Архів оригіналу за 11 грудня 2014. Процитовано 26 грудня 2017.

Посилання

Л. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел. — Безопасность информационных технологий, 2005. — № 2. — С. 27-38.

[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] [Архівовано 24 грудня 2013 у Wayback Machine.]

[Кнут2-2] а ^б ^в ^г Дональд Кнут. Seminumerical Algorithms // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1997. — Т. 2. — 762 с. — ISBN 0-201-89684-2.(англ.)

[3] M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177—179.[2] [Архівовано 24 грудня 2013 у Wayback Machine.]

[4] T.E. Hull and A.R. Dobell «Random Number Generators»,SIAM Review 4-3(1962),230-254 [3] [Архівовано 24 грудня 2013 у Wayback Machine.]

[Бакнелл-5] Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. — Delphi Informant Magazine, 2002.

[ParkMiller-6] Stephen K. Park; Keith W. Miller (1988). Random Number Generators: Good Ones Are Hard To Find (PDF). Communications of the ACM (англ.). 31 (10): 1192—1201. Архів оригіналу (PDF) за 20 березня 2018. Процитовано 26 грудня 2017.

[autogenerated2-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 [Архівовано 2 лютого 2015 у Wayback Machine.] that reproduces the random sequence from this library.

[10] A collection of selected pseudorandom number generators with linear structures, K. Entacher, 1997. Архів оригіналу за 5 червня 2013. Процитовано 16 червня 2012.

[11] Last public Committee Draft from April 12, 2011, page 346f (PDF). Архів оригіналу (PDF) за 29 березня 2018. Процитовано 21 грудня 2014.

[12] How Visual Basic Generates Pseudo-Random Numbers for the RND Function. Microsoft Support. Microsoft. Архів оригіналу за 17 квітня 2011. Процитовано 17 червня 2011.

[13] In spite of documentation on MSDN [Архівовано 8 березня 2016 у Wayback Machine.], 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

[cpp11-14] а ^б ISO/IEC 14882:2011. ISO. 2 September 2011. Архів оригіналу за 29 січня 2013. Процитовано 3 September 2011.

[15] GNU Scientific Library: Other random number generators. Архів оригіналу за 11 грудня 2014. Процитовано 26 грудня 2017.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]