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

Линейный конгруэнтный метод (ЛКМ, англ. Linear Congruential Generator, LCG) — это алгоритм генерации псевдослучайных чисел, основанный на рекуррентном линейном соотношении по модулю. Является одним из старейших и наиболее изученных генераторов псевдослучайных последовательностей, широко применявшихся в компьютерных системах и математическом моделировании. ЛКМ генерирует последовательность целых чисел, которая при определённом выборе параметров может имитировать равномерное распределение случайных величин.

История

Первое описание линейного конгруэнтного метода было предложено американским математиком Дерриком Генри Лемером в 1949 году. Лемер, работавший в корпорации RAND Corporation, искал эффективный способ генерации случайных чисел для компьютерного моделирования и статистических расчётов. Его идея заключалась в использовании простого рекуррентного соотношения, которое можно было быстро вычислять на ранних электронных вычислительных машинах.

В 1950-х годах метод был популяризирован в работах Джона фон Неймана, который использовал его в своих исследованиях по методу Монте-Карло. В 1958 году Кеннет Томпсон и Деннис Ритчи применили ЛКМ в операционной системе UNIX для генерации случайных чисел в утилите rand. В 1960-х годах метод стал стандартом де-факто для многих языков программирования, включая FORTRAN и C.

С развитием криптографии и требований к качеству случайных чисел в 1980-х годах были выявлены недостатки ЛКМ, такие как предсказуемость и корреляция между последовательными значениями. Тем не менее, метод оставался популярным для не криптографических приложений вплоть до конца XX века. В 1990-х годах появились более совершенные генераторы, такие как Mersenne Twister и вихрь Мерсенна, которые постепенно вытеснили ЛКМ из многих областей, однако он продолжает использоваться в простых встроенных системах и учебных целях.

Определение и формула

Линейный конгруэнтный метод задаётся рекуррентным соотношением:

\[ X_{n+1} = (a \cdot X_n + c) \mod m \]

где:

• \(X_n\) — текущее значение последовательности (целое число);
• \(X_{n+1}\) — следующее значение последовательности;
• \(a\) — множитель (целое число, \(a > 0\));
• \(c\) — приращение (целое число, \(c \geq 0\));
• \(m\) — модуль (целое число, \(m > 0\)).

Начальное значение \(X_0\) называется начальным числом (seed). Последовательность \(\{X_n\}\) является периодической, и её максимальный период не может превышать \(m\). Для достижения максимального периода (\(m\)) необходимо, чтобы выполнялись следующие условия (теорема Халла — Добелла):

1. \(c\) и \(m\) взаимно просты (НОД(c, m) = 1).
2. \(a - 1\) делится на все простые делители \(m\).
3. Если \(m\) делится на 4, то \(a - 1\) также делится на 4.

Если \(c = 0\), генератор называется мультипликативным конгруэнтным методом (МКМ). В этом случае максимальный период равен \(m - 1\) при условии, что \(a\) является первообразным корнем по модулю \(m\).

Классификация

По типу модуля

1. Степенной модуль (\(m = 2^k\)): наиболее распространён в компьютерных реализациях, так как операция взятия по модулю степени двойки выполняется аппаратно через битовое И (AND). Пример: \(m = 2^{31}\).
2. Простой модуль (\(m\) — простое число): обеспечивает максимальный период \(m - 1\) для мультипликативных генераторов. Пример: \(m = 2^{31} - 1\) (простое число Мерсенна).
3. Составной модуль: редко используется из-за сложности анализа.

По наличию приращения

1. Смешанный ЛКМ (\(c \neq 0\)): классическая форма с полным периодом \(m\).
2. Мультипликативный ЛКМ (\(c = 0\)): проще в реализации, но период ограничен \(m - 1\).

Характеристики и параметры

Выбор параметров

Качество генерации напрямую зависит от выбора \(a\), \(c\) и \(m\). На практике используются следующие известные наборы параметров:

• RANDU (IBM, 1960-е): \(a = 65539\), \(c = 0\), \(m = 2^{31}\). Имел серьёзные корреляции и был признан неудовлетворительным.
• Minimal Standard (Парк и Миллер, 1988): \(a = 16807\), \(c = 0\), \(m = 2^{31} - 1\). Рекомендован для простых приложений.
• Borland C/C++ (rand): \(a = 22695477\), \(c = 1\), \(m = 2^{32}\).
• glibc (rand): \(a = 1103515245\), \(c = 12345\), \(m = 2^{31}\).

Период

Период ЛКМ — это длина последовательности до её повторения. Для смешанного ЛКМ с оптимальными параметрами период равен \(m\). Для мультипликативного — \(m - 1\). На практике период может быть недостаточным для современных задач (например, моделирование требует последовательностей длиной \(10^9\) и более), что ограничивает применение ЛКМ.

Корреляция

Последовательности ЛКМ обладают корреляцией между последовательными значениями, особенно при малом \(m\). Это проявляется в том, что точки \((X_n, X_{n+1})\) в двумерном пространстве ложатся на гиперплоскости (так называемый «эффект решётки»). Для \(m = 2^{31}\) количество таких плоскостей может быть равно \(\sqrt[3]{m} \approx 1625\), что делает генератор предсказуемым.

Применение

Историческое

• Метод Монте-Карло: в 1950-х — 1970-х годах ЛКМ использовался для моделирования физических и экономических процессов.
• Компьютерные игры: ранние игры (например, «Rogue», 1980) использовали ЛКМ для генерации уровней и случайных событий.
• Статистические пакеты: программы SPSS, SAS и R (до версии 3.6.0) использовали ЛКМ в качестве стандартного генератора.

Современное

• Встроенные системы: микроконтроллеры с ограниченными ресурсами (например, Arduino) часто используют ЛКМ из-за простоты реализации.
• Учебные цели: ЛКМ изучается в курсах программирования и численных методов как базовый пример генератора псевдослучайных чисел.
• Не криптографические приложения: генерация паролей (не для защиты), тестирование программного обеспечения, симуляция трафика.

Ограничения

• Непригодность для криптографии: последовательность ЛКМ легко предсказуема при известных параметрах. Даже без знания \(a\) и \(c\) можно восстановить их по нескольким последовательным значениям.
• Неравномерность распределения: при малом \(m\) или плохом выборе параметров распределение может отклоняться от равномерного.
• Корреляция: для задач, требующих высокой степени случайности (например, научное моделирование), ЛКМ недостаточен.

Критика

Критика линейного конгруэнтного метода сосредоточена на его предсказуемости и низком качестве случайности. В 1968 году Джордж Марсалья в своей работе «Random Numbers Fall Mainly in the Planes» показал, что последовательности ЛКМ образуют решётчатую структуру в многомерном пространстве, что делает их непригодными для многих статистических тестов. Позднее, в 1990-х годах, были разработаны тесты Diehard (Марсалья) и TestU01, которые ЛКМ часто не проходит.

В 1999 году японский математик Макото Мацумото создал вихрь Мерсенна (Mersenne Twister), который превзошёл ЛКМ по всем показателям, включая период (2^19937 - 1) и качество распределения. С тех пор ЛКМ считается устаревшим для серьёзных приложений, хотя и продолжает использоваться в простых системах.

Интересные факты

• В 1970-х годах в операционной системе UNIX использовался ЛКМ с параметрами \(a = 1103515245\), \(c = 12345\), \(m = 2^{31}\), который до сих пор применяется в библиотеке glibc для функции rand().
• В 1990-х годах было обнаружено, что генератор RANDU, использовавшийся в IBM System/360, имел настолько плохую корреляцию, что все точки в трёхмерном пространстве лежали на 15 плоскостях.
• Линейный конгруэнтный метод является частным случаем линейного рекуррентного генератора (LFSR), который используется в криптографии, но с другими математическими свойствами.

Источники

• Лемер, Д. Г. (1949). «Mathematical Methods in Large-Scale Computing Units». Annals of the Computation Laboratory of Harvard University.
• Парк, С. К., Миллер, К. В. (1988). «Random Number Generators: Good Ones Are Hard to Find». Communications of the ACM.
• Марсалья, Дж. (1968). «Random Numbers Fall Mainly in the Planes». Proceedings of the National Academy of Sciences.
• Мацумото, М., Нисимура, Т. (1998). «Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator». ACM Transactions on Modeling and Computer Simulation.
• Кнут, Д. Э. (1997). Искусство программирования, том 2: Получисленные алгоритмы.