Теория
Линейный конгруэнтный генератор (LCG) — самый старый и простой ГПСЧ: следующее число вычисляется по формуле \(x_{n+1} = (a \cdot x_n + c) \bmod m\), где \(a\) — множитель, \(c\) — приращение, \(m\) — модуль. При правильных параметрах последовательность проходит весь диапазон \(0 \ldots m-1\) и лишь затем повторяется — это называется полным периодом.
Условия полного периода даёт теорема Халла–Добела: \(c\) и \(m\) взаимно просты, \(a-1\) делится на все простые делители \(m\) и на 4, если \(m\) делится на 4. Нарушение любого условия сокращает период — знаменитый RANDU, созданный в IBM в 1960-х, выдавал значения, лежащие на 15 плоскостях в трёхмерном пространстве, что породило поговорку «random numbers fall mainly in the planes».
Важно: LCG линеен и предсказуем: по нескольким выходам параметры восстанавливаются (см. калькулятор «Восстановление параметров LCG»). Для секретов он непригоден.
Пример с решением
- Условие. Генератор MINSTD (\(a = 48271\), \(c = 0\), \(m = 2^{31}-1\)) с зерном 1: найдите первые два числа.
- Формула. \(x_{n+1} = (a \cdot x_n + c) \bmod m\).
- Подстановка. \(x_1 = (48271 \cdot 1 + 0) \bmod 2147483647\).
- Вычисление. \(x_1 = 48271\), затем \(x_2 = 48271^2 \bmod 2147483647 = 182605794\).
- Ответ. 48271, 182605794 — те же значения выдаёт калькулятор с пресетом MINSTD и зерном 1.
Главное
- Формула: \(x_{n+1} = (a \cdot x_n + c) \bmod m\).
- Полный период — при выполнении условий Халла–Добела.
- RANDU — хрестоматийный пример неудачных параметров.