Инверсный конгруэнтный метод

Инверсный конгруэнтный метод является примером нелинейного генератора. На каждом шаге алгоритма, состояние вычисляется как линейная функция от обратного (по модулю) к текущему. Общая формула имеет вид $$x_{i+1} = \left\lbrace\begin{align} ax_i^{-1}+c \mod p, && x_i\neq 0\\ c \mod p, && x_i = 0\\ \end{align}\right.,$$ $p$ – простое.

Максимальный период такого генератора составляет $p$, и эта длина периода достигается тогда и только тогда, когда полином $$f(z) = z^2 - cz - a$$ является примитивным в поле $GF(p)$, то есть может быть представлен как $$f(x) = (x-\alpha)(x-\alpha^p),$$ где $\alpha$ – некий примитивный элемент $GF(p^2)$, и тогда $$c = \alpha + \alpha^p \mod p$$ $$a = - \alpha^{p+1} \mod p$$

Значительным преимуществом этого метода является отсутствие линейных корреляций между идущими подряд числами. Как следствие, отсутствует характерная для ЛКГ “решетчатая” структура. Это, конечно, не отменяет наличия других корреляций.

Метод умножения с переносом

Метод умножения с переносом является специальным случаем мультипликативного генератора (генератора Лемера), позволяющим эффективно использовать в качестве модуля $p$ числа, большие, чем позволяет архитектура платформы (т.е. больше машинного слова).

Общая формула имеет вид $$x_n = (ax_{n-r}+c_{n-1}) \mod b,$$ где $$c_{n} = \left\lfloor \frac{a x_{n-r}+c_{n-1}}{b} \right\rfloor$$ называется переносом, $a$ – множитель, $b$ – база. В качестве состояния хранятся $r$ значений $x_{n-r}, \ldots, x_{n-1}$ и значение $c_{n-1}$.

Пусть $p = ab^{r}-1$ и состояние представляет из себя большое $b$-ичное целое число, где старший разряд равен $c_{n-1}$, младший – $x_{n-r}$. Тогда операцию преобразования состояния можно представить как последовательность следующих операций:

1. Вычесть $x_{n-r}$. Это обнуляет младший разряд.
2. Прибавить $a x_{n-r} b^r$. Это добавляет к состоянию один новый разряд $c_n$, а второй по старшинству разряд (соответствующий b^r) равен $x_n$.
3. Разделить состояние на $b$ (что эквивалентно смещению вправо на 1 $b$-ичный разряд).

Первые два пункта по сути прибавляют к состоянию $x_{n-r}(ab^r - 1) = x_{n-r} p$. Третий пункт соответствует умножению на $b^{-1} \mod p$.

Таким образом, генератор умножения с переносом эквивалентен генератору Лемера с модулем $p = ab^{r}-1$ b множителем $a' = b^{-1} \mod p$.

Периодом генератора является порядок элемента $b$ в мультипликативной группе по модулю $p$. Понятно, что для максимизации периода имеет смысл выбирать простое $p$. В то же время, этого недостаточно. Распространённым методом является выбор в качестве $p$ “безопасного простого”, т.е. $p=2q+1$, где $q$ так же простое. По малой теореме Ферма, порядок любого элемента есть делитель $p-1$, и тогда период есть делитель $2q$, то есть, исключая $b=p-1$ (единственный элемент с порядком 2, если p простое), $\lambda=q = (p-1)/2 = ab^r/2 − 1$.

Собственно, это же рассуждение даёт нам теоретически возможное максимальное значение периода, если $p$ не является “безопасным простым”.