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

Инверсный конгруэнтный метод является примером нелинейного генератора. На каждом шаге алгоритма, состояние вычисляется как линейная функция от обратного (по модулю) к текущему. Общая формула имеет вид \[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\) не является “безопасным простым”.