Линейный конгруэнтный метод — один из методов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.
Описание Линейный конгруэнтный метод был предложен Д. Г. Лемером на проходившем в 1949 году симпозиуме и опубликован в 1951 году в трудах симпозиума.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) Суть метода заключается в вычислении последовательности случайных чисел , полагая
где — модуль (натуральное число, относительно которого вычисляет остаток от деления; ), — множитель (), — приращение (), — начальное значение ().
Эта последовательность называется линейной конгруэнтной последовательностью. Например, для получим последовательность
Свойства Линейная конгруэнтная последовательность, определенная числами , , и периодична с периодом, не превышающим . При этом длина периода равна тогда и только тогда, когдаКнут Д. Э., Искусство программирования. Том 2. Получисленные методы — Вильямс. 2001. с.21-37:
Числа и взаимно простые; кратно для каждого простого , являющегося делителем ; кратно , если кратно .
Наличие этого свойства для случая , где — число битов в машинном слове, было доказано М. Гринбергом ().M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177—179. Наличие этого свойства для общего случая и достаточность условий были доказаны Т. Е. Халлом () и А. Р. Добеллом ().T.E. Hull and A.R. Dobell «Random Number Generators»,SIAM Review 4-3(1962),230-254
Метод генерации линейной конгруэнтной последовательности при называют мультипликативным конгруэнтным методом, а при — смешанным конгруэнтным методом. При генерируемые числа будут иметь меньший период, чем при , но при определенных условиях можно получить период длиной , если — простое число. Тот факт, что условие может приводить к появлению более длинных периодов, был установлен В. Е. Томсоном () и независимо от него А. Ротенбергом (). Чтобы гарантировать максимальность цикла повторения последовательности при , необходимо в качестве значения параметра выбирать простое число. Самым известным генератором подобного рода является так называемый минимальный стандартный генератор случайных чисел, предложенный Стивеном Парком () и Кейтом Миллером () в 1988 году. Для него , а ."Бакнелл Д. М. Фундаментальные алгоритмы и структуры данных в 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
Наиболее часто практикуемым методом генерации последовательностей псевдослучайных чисел является смешанный конгруэнтный метод.
Часто используемые параметры При выборе числа необходимо учитывать следующие условия:
1) число должно быть довольно большим, так как период не может иметь больше элементов;
2) значение числа должно быть таким, чтобы вычислялось быстро.
На практике при реализации метода исходя из указанных условий чаще всего выбирают , где — число битов в машинном слове. При этом стоит учитывать, что младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Подобная ситуация не возникает, когда , где — длина машинного слова. В таком случае младшие разряды ведут себя так же случайно, как и старшие. Выбор множителя и приращения в основном обусловлен необходимостью выполнения условия достижения периода максимальной длины.
Все приведенные константы обеспечивают работу генератора с максимальным периодом. Таблица упорядочена по максимальному произведению, которое не вызывает переполнение в слове указанной длины.
Переполняется при 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 RecipesNumerical recipies in C. The art of scientific computing. 2-nd edition. — Cambridge University Press, 1992. — 925 pp. 232 1664525 1013904223 Borland C/C++ 232 22695477 1 bits 30..16 in rand(), 30..0 in lrand() glibc (used by GCC)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. 231 1103515245 12345 bits 30..0 ANSI C: Watcom, Digital Mars, CodeWarrior, IBM VisualAge C/C++ 231 1103515245 12345 bits 30..16 C99, C11: Suggestion in the ISO/IEC 9899 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) 224 1140671485 (43FD43FD16) 12820163 (C39EC316) RtlUniform from Native APIIn 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 231 − 1 2147483629 (7FFFFFED16) 2147483587 (7FFFFFC316) Apple CarbonLib, C++11's minstd_rand0 231 − 1 16807 0 see MINSTD C++11's minstd_rand 231 − 1 48271 0 see MINSTD MMIX by Donald Knuth 264 6364136223846793005 1442695040888963407 Newlib 264 6364136223846793005 1 bits 63…32 VAX's MTH$RANDOM, old versions of glibc 232 69069 1 Java 248 25214903917 11 bits 47…16 Ранее во многих компиляторах: RANDU 231 65539 0
Возможность использования в криптографии Хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким. Генераторы на основе линейного конгруэнтного метода являются предсказуемыми, поэтому их нельзя использовать в криптографии. Впервые генераторы на основе линейного конгруэнтного метода были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бойяр. Ей удалось также вскрыть квадратические и кубические генераторы. Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального генератора. Таким образом, была доказана бесполезность генераторов на основе конгруэнтных методов для криптографии. Однако генераторы на основе линейного конгруэнтного метода сохраняют свою полезность для некриптографических приложений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестов демонстрируют хорошие статистические характеристики.
См. также Генератор псевдослучайных чисел Инверсный конгруэнтный метод
Примечания
Литература
Ссылки
Категория:Генераторы псевдослучайных чисел