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

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

Принцип работы

Работа LCG основана на рекуррентной формуле:

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

где:

• \(X_n\) — текущее значение (начальное значение \(X_0\) называется зерном или seed);
• \(a\) — множитель (multiplier);
• \(c\) — приращение (increment);
• \(m\) — модуль (modulus);
• \(X_{n+1}\) — следующее значение последовательности.

Все операции выполняются в целочисленной арифметике. Результатом является последовательность целых чисел в диапазоне от 0 до \(m-1\). Для получения дробных чисел в интервале (0, 1) результат обычно делят на \(m\).

Параметры и их влияние

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

Модуль \(m\)

Модуль определяет максимальный период последовательности. Теоретически максимальный период равен \(m\) (при правильном выборе параметров). На практике \(m\) часто выбирают равным степени двойки (\(2^k\)), так как это упрощает вычисление остатка от деления в двоичной арифметике (например, \(m = 2^{31}\) или \(2^{32}\)). Однако такой выбор может приводить к корреляции младших битов.

Множитель \(a\) и приращение \(c\)

Для достижения максимального периода (равного \(m\)) необходимо выполнение трёх условий (теорема Халла — Добелла):

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

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

История

Идея линейных конгруэнтных последовательностей была предложена американским математиком Дерриком Лемером (Derrick Henry Lehmer) в 1949 году. В 1951 году Джон фон Нейман (John von Neumann) использовал подобный метод в программе для компьютера ENIAC, хотя его «метод середины квадрата» был менее надёжным.

В 1960-х годах LCG стал стандартным генератором в системах IBM (например, RANDU — один из самых известных и неудачных примеров). В 1970-х годах Дональд Кнут (Donald Knuth) в своей книге «Искусство программирования» подробно проанализировал LCG и предложил наборы параметров, ставших классическими (например, \(a = 6364136223846793005\), \(c = 1442695040888963407\), \(m = 2^{64}\) — для 64-битных систем).

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

LCG можно классифицировать по значению приращения:

• Полный LCG (mixed LCG) — \(c \neq 0\). Позволяет достичь периода \(m\).
• Мультипликативный LCG (multiplicative LCG) — \(c = 0\). Период обычно равен \(m - 1\) при простом \(m\).
• Аддитивный LCG — \(a = 1\). В этом случае последовательность представляет собой просто арифметическую прогрессию по модулю \(m\), что даёт тривиальный результат.

Примеры реализаций

Классический генератор из библиотеки C (rand)

В ранних версиях стандартной библиотеки языка C (например, в UNIX System V) использовался LCG с параметрами:

• \(a = 1103515245\)
• \(c = 12345\)
• \(m = 2^{31}\)

Этот генератор давал период \(2^{31}\) и был широко распространён, но его младшие биты имели сильную корреляцию.

Генератор MINSTD (Park–Miller)

В 1988 году Стивен Парк (Stephen Park) и Кит Миллер (Keith Miller) предложили простой мультипликативный LCG:

• \(a = 16807\)
• \(c = 0\)
• \(m = 2^{31} - 1\) (простое число Мерсенна)

Этот генератор имеет период \(2^{31} - 2\) и долгое время считался эталоном для не криптографических приложений.

Генератор в Java (java.util.Random)

В языке Java (начиная с ранних версий) используется LCG с параметрами:

• \(a = 25214903917\)
• \(c = 11\)
• \(m = 2^{48}\)

Период составляет \(2^{48}\), но для получения 32-битного числа используются только старшие биты, что улучшает статистические свойства.

Достоинства и недостатки

Достоинства

• Простота реализации: требуется всего несколько строк кода.
• Высокая скорость: одна операция умножения, сложения и взятия модуля.
• Малый объём памяти: требуется хранить только текущее состояние (одно целое число).

Недостатки

• Предсказуемость: зная несколько последовательных значений (или даже одно значение при известных параметрах), можно восстановить всё состояние генератора. Это делает LCG абсолютно непригодным для криптографии.
• Корреляция: особенно сильно проявляется в младших битах. Например, последовательность младших битов может иметь период 2, 4 или 8, а не \(m\).
• Короткий период: для современных задач период \(2^{32}\) или \(2^{48}\) может быть недостаточным.
• Плохая равномерность в многомерном пространстве: точки, сгенерированные LCG, часто ложатся на гиперплоскости (эффект Марсальи).

Применение

Несмотря на недостатки, LCG до сих пор применяется в некоторых областях:

• Встроенные системы с ограниченными ресурсами (микроконтроллеры, FPGA).
• Неответственные симуляции (например, генерация тестовых данных, случайные фоны в играх).
• Образовательные цели — как простой пример псевдослучайного генератора.
• Быстрые хеш-функции (например, в некоторых реализациях хеш-таблиц).

Для криптографических приложений (генерация ключей, паролей, токенов) LCG категорически не рекомендуется. Вместо него используются криптостойкие генераторы, такие как ChaCha20, AES-CTR или алгоритмы на основе аппаратных источников энтропии.

Критика и альтернативы

Основная критика LCG связана с его предсказуемостью и плохими статистическими свойствами. В 1990-х годах Джордж Марсалья (George Marsaglia) разработал набор тестов «Diehard», которые большинство LCG не проходили. В качестве альтернатив были предложены:

• Вихрь Мерсенна (Mersenne Twister) — имеет огромный период (\(2^{19937} - 1\)) и хорошие статистические свойства, но не криптостоек.
• Генераторы на основе регистров сдвига с линейной обратной связью (LFSR) — быстрее LCG в аппаратной реализации.
• Генераторы на основе алгоритмов шифрования (AES, ChaCha20) — обеспечивают криптографическую стойкость.

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

• Самый известный «провальный» LCG — RANDU (IBM System/360, 1960-е). Его параметры (\(a = 65539\), \(c = 0\), \(m = 2^{31}\)) приводили к тому, что все сгенерированные точки ложились на 15 плоскостей в трёхмерном пространстве, что делало его непригодным для моделирования.
• В 1999 году в стандарте POSIX (Single UNIX Specification) было рекомендовано заменить LCG в функции rand() на более качественный генератор, но многие реализации сохранили старый алгоритм для обратной совместимости.
• В языке C++ (стандарт C++11) введены новые генераторы (например, std::mt19937), которые не используют LCG, но старые реализации std::rand() всё ещё могут быть основаны на нём.

Источники

1. Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd ed.). Addison-Wesley.
2. Park, S. K., & Miller, K. W. (1988). «Random Number Generators: Good Ones Are Hard to Find». Communications of the ACM, 31(10), 1192–1201.
3. Marsaglia, G. (1968). «Random Numbers Fall Mainly in the Planes». Proceedings of the National Academy of Sciences, 61(1), 25–28.
4. Lehmer, D. H. (1951). «Mathematical Methods in Large-Scale Computing Units». Proceedings of the Second Symposium on Large-Scale Digital Calculating Machinery, 141–146.
5. ISO/IEC 9899:1999 (C99 standard) — описание функции rand().
6. «Linear Congruential Generator» — статья в Encyclopedia of Cryptography and Security (2011).