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

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

Описание

Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

$X_{k+1} = (a X_k + c)~~\bmod~~m,$

где a и c — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа $X_{0}$ и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства этой последовательности определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа.

Свойства

Последовательность чисел, порождаемая линейным конгруэнтным методом, периодична с периодом, не превышающим m. При этом длина периода в точности равна m тогда и только тогда, когда:^[1]

1. НОД(c,m) = 1 (то есть, c и m взаимно просты);
2. a-1 кратно p для всех простых делителей p числа m;
3. a-1 кратно 4, если m кратно 4.

Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором коэффициентов a и c. Для этих констант выписаны^[кем?] условия, гарантирующие удовлетворительное качество получаемых случайных чисел.

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

При реализации выгодно выбирать $m = 2^e$, где e — число битов в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в d-мерном пространстве, точки ложатся не более, чем на $m^{1/d}$ гиперплоскостей, что ограничивает применение генератора в методе Монте-Карло.

В таблице ниже приведены наиболее часто используемые параметры линейных конгруэнтных генераторов, в частности, в стандартных библиотеках различных компиляторов (функция rand()).

Source	m	a	c	выдаваемые биты результата в rand() / Random(L)
Numerical Recipes (англ.)	232	1664525	1013904223
MMIX by Donald Knuth	264	6364136223846793005	1442695040888963407
Borland C/C++	232	22695477	1	биты 30..16 в rand(), 30..0 в lrand()
GNU Compiler Collection	232	69069	5	биты 30..16
ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++	232	1103515245	12345	биты 30..16
Borland Delphi, Virtual Pascal	232	134775813	1	биты 63..32 числа (seed * L)
Microsoft Visual/Quick C/C++	232	214013	2531011	биты 30..16
Apple CarbonLib	231 - 1	16807	0	см. Метод Лемера (англ.)

Криптоанализ

Особенностью линейного конгруэнтного метода является то, что если сомножитель и модуль соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от случайной последовательности элементов множества { 0, 1, 2, …, m-1 }. Однако, все элементы этой последовательности однозначно определяются четырьмя параметрами: X₀, a, c, m.

Если криптоаналитик знает об использовании линейного конгруэнтного метода с известными параметрами, то известной становится вся последовательность чисел. В то же время, даже если криптоаналитик знает только лишь об использовании линейного конгруэнтного метода, то информация о небольшой части последовательности достаточна для выявления параметров метода и всех последующих элементов последовательности. В частности, если криптоаналитику известны значения ${X_0}, {X_1}, {X_2}, {X_3}$, то они удовлетворяют системе уравнений:

$\begin{cases} X_{1} = (a\cdot X_{0} + c )~ \bmod~ m\\ X_{2} = (a\cdot X_{1} + c )~ \bmod~ m\\ X_{3} = (a\cdot X_{2} + c )~ \bmod~ m\end{cases}$

из которой можно получить значения параметров а, с и m.

Поэтому, хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким.

Примечания

1. ↑ Дональд Кнут, Искусство программирования (Том 2. Получисленные алгоритмы)

Ссылки

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