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

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

ОписаниеПравить

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

\text{[math]}

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

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

Эта последовательность называется линейной конгруэнтной последовательностью. Например, для $\text{[math]}$ $\text{[math]}$ $m=10,X_{0}=a=c=7$ получим последовательность $\text{[math]}$ $\text{[math]}$ $7,6,9,0,7,6,9,0,\dots$ ^[2]

СвойстваПравить

Линейная конгруэнтная последовательность, определенная числами $\text{[math]}$ $\text{[math]}$ $m$ , $\text{[math]}$ $\text{[math]}$ $a$ , $\text{[math]}$ $\text{[math]}$ $c$ и $\text{[math]}$ $\text{[math]}$ $X_{0}$ периодична с периодом, не превышающим $\text{[math]}$ $\text{[math]}$ $m$ . При этом длина периода равна $\text{[math]}$ $\text{[math]}$ $m$ тогда и только тогда, когда^[3]:

Числа $\text{[math]}$ $\text{[math]}$ $c$ и $\text{[math]}$ $\text{[math]}$ $m$ взаимно простые;
$\text{[math]}$ $\text{[math]}$ $b=a-1$ кратно $\text{[math]}$ $\text{[math]}$ $p$ для каждого простого $\text{[math]}$ $\text{[math]}$ $p$ , являющегося делителем $\text{[math]}$ $\text{[math]}$ $m$ ;
$\text{[math]}$ $\text{[math]}$ $b$ кратно $\text{[math]}$ $\text{[math]}$ $4$ , если $\text{[math]}$ $\text{[math]}$ $m$ кратно $\text{[math]}$ $\text{[math]}$ $4$ .

Наличие этого свойства для случая $\text{[math]}$ $\text{[math]}$ $m=2^{e}$ , где $\text{[math]}$ $\text{[math]}$ $e$ — число битов в машинном слове, было доказано М. Гринбергом (англ. M. Greenberg).^[4] Наличие этого свойства для общего случая и достаточность условий были доказаны Т. Е. Халлом (англ. T. E. Hull) и А. Р. Добеллом (англ. A. R. Dobell).^[5]

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

Наиболее часто практикуемым методом генерации последовательностей псевдослучайных чисел является смешанный конгруэнтный метод.^{[источник не указан 2032 дня]}

Часто используемые параметрыПравить

При выборе числа $\text{[math]}$ $\text{[math]}$ $m$ необходимо учитывать следующие условия:

1) число $\text{[math]}$ $\text{[math]}$ $m$ должно быть довольно большим, так как период не может иметь больше $\text{[math]}$ $\text{[math]}$ $m$ элементов;

2) значение числа $\text{[math]}$ $\text{[math]}$ $m$ должно быть таким, чтобы $\text{[math]}$ $\text{[math]}$ $(aX_{n}+c)\mod m$ вычислялось быстро.

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

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

Все приведенные константы обеспечивают работу генератора с максимальным периодом. Таблица упорядочена по максимальному произведению, которое не вызывает переполнение в слове указанной длины.^[8]

Переполняется при	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^[9]	2³²	1664525	1013904223
Borland C/C++	2³²	22695477	1	bits 30..16 in rand(), 30..0 in lrand()
glibc (used by GCC)^[10]	2³¹	1103515245	12345	bits 30..0
ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++^[11]	2³¹	1103515245	12345	bits 30..16
C99, C11: Suggestion in the ISO/IEC 9899^[12]	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)^[13]	2²⁴	1140671485 (43FD43FD₁₆)	12820163 (C39EC3₁₆)
RtlUniform from Native API^[14]	2³¹ − 1	2147483629 (7FFFFFED₁₆)	2147483587 (7FFFFFC3₁₆)
Apple CarbonLib, C++11's `minstd_rand0`^[15]	2³¹ − 1	16807	0	see MINSTD
C++11's `minstd_rand`^[15]	2³¹ − 1	48271	0	see MINSTD
MMIX by Donald Knuth	2⁶⁴	6364136223846793005	1442695040888963407
Newlib	2⁶⁴	6364136223846793005	1	bits 63…32
VAX's MTH$RANDOM,^[16] old versions of glibc	2³²	69069	1
Java	2⁴⁸	25214903917	11	bits 47…16
Ранее во многих компиляторах:
RANDU	2³¹	65539	0

Возможность использования в криптографииПравить

Хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким. Генераторы на основе линейного конгруэнтного метода являются предсказуемыми, поэтому их нельзя использовать в криптографии. Впервые генераторы на основе линейного конгруэнтного метода были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бояр (Joan Boyar). Ей удалось также вскрыть квадратические и кубические генераторы. Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального генератора. Таким образом, была доказана бесполезность генераторов на основе конгруэнтных методов для криптографии. Однако генераторы на основе линейного конгруэнтного метода сохраняют свою полезность для некриптографических приложений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестов демонстрируют хорошие статистические характеристики^[8].

См. такжеПравить

ПримечанияПравить

↑ 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. Получисленные методы // Искусство программирования. Указ. соч. — С. 21—37.
↑ Кнут Д. Э., Искусство программирования. Том 2. Получисленные методы — Вильямс. 2001. с.21-37
↑ 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. Библиотека программиста. 2002 год. журнал Delphi Informant Magazine. Глава 6.
↑ Stephen K. Park and Keith W. Miller (1988). Random Number Generators: Good Ones Are Hard To Find. Communications of the ACM 31 (10): 1192—1201[4] Архивная копия от 4 апреля 2019 на Wayback Machine
↑ ¹ ² Брюс Шнайер. Глава 16. // Прикладная криптография.Триумф.2002. Указ. соч. — С. 275.[5] Архивная копия от 28 февраля 2014 на Wayback Machine
↑ Numerical recipies in C. The art of scientific computing. 2-nd edition. — Cambridge University Press, 1992. — 925 pp.
↑ 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 (неопр.). Дата обращения: 16 июня 2012. Архивировано 5 июня 2013 года.
↑ Last public Committee Draft from April 12, 2011, page 346f (неопр.). Дата обращения: 21 декабря 2014. Архивировано 25 декабря 2021 года.
↑ 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 сентября 2011). Дата обращения: 3 сентября 2011. Архивировано 17 мая 2013 года.
↑ GNU Scientific Library: Other random number generators (неопр.). Дата обращения: 10 января 2015. Архивировано 11 декабря 2014 года.

ЛитератураПравить

Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2000. — Т. 2. Получисленные алгоритмы. — 832 с. — 7000 экз. — ISBN 5-8459-0081-6 (рус.) ISBN 0-201-89684-2 (англ.).

СсылкиПравить

Л. Бараш. Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел // Безопасность информационных технологий. — 2005. — № 2. — С. 27—38.
Stephen K. Park and Keith W. Miller. Random Number Generators: Good Ones Are Hard To Find. — 1988. — № 2. — С. 1192—1201.
Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi.Библиотека программиста.[6] // Delphi Informant Magazine. — 2002.

[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

[multiple-2] ¹ ² ³ Дональд Кнут. Том 2. Получисленные методы // Искусство программирования. Указ. соч. — С. 21—37.

[autogenerated1-3] Кнут Д. Э., Искусство программирования. Том 2. Получисленные методы — Вильямс. 2001. с.21-37

[4] M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177—179.[2] Архивная копия от 24 декабря 2013 на Wayback Machine

[5] T.E. Hull and A.R. Dobell «Random Number Generators»,SIAM Review 4-3(1962),230-254 [3] Архивная копия от 24 декабря 2013 на Wayback Machine

[6] "Бакнелл Д. М. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. 2002 год. журнал Delphi Informant Magazine. Глава 6.

[7] Stephen K. Park and Keith W. Miller (1988). Random Number Generators: Good Ones Are Hard To Find. Communications of the ACM 31 (10): 1192—1201[4] Архивная копия от 4 апреля 2019 на Wayback Machine

[autogenerated2-8] ¹ ² Брюс Шнайер. Глава 16. // Прикладная криптография.Триумф.2002. Указ. соч. — С. 275.[5] Архивная копия от 28 февраля 2014 на Wayback Machine

[9] Numerical recipies in C. The art of scientific computing. 2-nd edition. — Cambridge University Press, 1992. — 925 pp.

[10] 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.

[11] A collection of selected pseudorandom number generators with linear structures, K. Entacher, 1997 (неопр.). Дата обращения: 16 июня 2012. Архивировано 5 июня 2013 года.

[12] Last public Committee Draft from April 12, 2011, page 346f (неопр.). Дата обращения: 21 декабря 2014. Архивировано 25 декабря 2021 года.

[13] How Visual Basic Generates Pseudo-Random Numbers for the RND Function (неопр.). Microsoft Support. Microsoft. Дата обращения: 17 июня 2011. Архивировано 17 апреля 2011 года.

[14] 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-15] ¹ ² ISO/IEC 14882:2011 (неопр.). ISO (2 сентября 2011). Дата обращения: 3 сентября 2011. Архивировано 17 мая 2013 года.

[16] GNU Scientific Library: Other random number generators (неопр.). Дата обращения: 10 января 2015. Архивировано 11 декабря 2014 года.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]