Инверсивный конгруэнтный генератор

Инверсивные конгруэнтные генераторы — это тип нелинейного конгруэнтного генератора псевдослучайных чисел , который использует модульное мультипликативное обратное (если оно существует) для генерации следующего числа в последовательности. Стандартная формула инверсивного конгруэнтного генератора по модулю некоторого простого числа q :

$x_{0}={\text{seed}},$

$x_{i+1}={\begin{cases}(ax_{i}^{-1}+c){\bmod {q}}&{\text{if }}x_{i}\neq 0,\\c&{\text{if }}x_{i}=0.\end{cases}}$

Такой генератор символически обозначается как ICG( q , a , c , seed ) и называется ICG с параметрами q , a , c и начальным семенем .

Период

Последовательность $(x_{n})_{n\geq 0}$ должен иметь $x_{i}=x_{j}$ после конечного числа шагов и поскольку следующий элемент зависит только от своего прямого предшественника, также $x_{i+1}=x_{j+1}$ и т. д. Максимально возможный период для модуля q равен самому q , т. е. последовательность включает в себя все значения от 0 до q - 1 перед повторением.

Достаточным условием того, чтобы последовательность имела максимально возможный период, является выбор a и c так, чтобы полином $f(x)=x^{2}-cx-a\in \mathbb {F} _{q}[x]$ (полиномиальное кольцо над $\mathbb {F} _{q}$) примитивен . Это не обязательное условие; существуют варианты q , a и c, для которых $f(x)$ не является примитивной, но последовательность, тем не менее, имеет период q . Любой полином, примитивный или нет, который приводит к последовательности максимального периода, называется инверсивным полиномом максимального периода (IMP). Чжоу описывает алгоритм выбора параметров a и c для получения таких полиномов.

Эйхенауэр-Херрманн, Лен, Гроте и Нидеррайтер показали, что инверсивные конгруэнтные генераторы обладают хорошими свойствами однородности, особенно в отношении структуры решетки и последовательных корреляций.

Пример

ICG(5, 2, 3, 1) дает последовательность 1, 0, 3, 2, 4, 1, 0, 3, 4, 2, 1, 0,...

В этом примере $f(x)=x^{2}-3x-2$ является неприводимым в $\mathbb {F} _{5}[x]$, поскольку ни одно из 0, 1, 2, 3 или 4 не является корнем. Также можно проверить, что x является примитивным элементом $\mathbb {F} _{5}[x]/(f)$ и, следовательно, f примитивно.

Составной инверсный генератор

Конструкция составного инверсивного генератора (CIG) основана на объединении двух или более инверсивных конгруэнтных генераторов в соответствии с методом, описанным ниже.

Позволять $p_{1},\dots ,p_{r}$ — различные простые целые числа, каждое из которых $p_{j}\geq 5$. Для каждого индекса j , 1 ≤ j ≤ r , пусть $(x_{n})_{n\geq 0}$ быть последовательностью элементов $\mathbb {F} _{p_{j}}$ периодический с длиной периода $p_{j}$. Другими словами, $\{x_{n}^{(j)}\mid 0\leq n\leq p_{j}\}\in \mathbb {F} _{p_{j}}$.

Для каждого индекса j , 1 ⩽ j ⩽ r, мы рассматриваем $T_{j}=T/p_{j}$, где $T=p_{1}\cdots p_{r}$ длина периода следующей последовательности $(x_{n})_{n\geq 0}$.

Последовательность $(x_{n})_{n\geq 0}$ составных псевдослучайных чисел определяется как сумма

$x_{n}=\left(T_{1}x_{n}^{(1)}+T_{2}x_{n}^{(2)}+\dots +T_{r}x_{n}^{(r)}\right){\bmod {T}}$.

Составной подход позволяет объединять инверсивные конгруэнтные генераторы при условии, что они имеют полный период, в системы параллельной генерации.

Преимущества ЦИГ

CIG принимаются для практических целей по ряду причин.

Во-первых, полученные таким образом двоичные последовательности не содержат нежелательных статистических отклонений. Инверсивные последовательности, тщательно проверенные с помощью различных статистических тестов, остаются стабильными при изменении параметра.

Во-вторых, существует устойчивый и простой способ выбора параметров, основанный на алгоритме Чжоу. что гарантирует максимальную продолжительность периода.

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

Существует алгоритм что позволяет создавать составные генераторы с предсказуемой длиной периода, предсказуемым линейным уровнем сложности, с отличными статистическими свойствами создаваемых битовых потоков.

Процедура проектирования этой сложной структуры начинается с определения конечного поля из p элементов и заканчивается выбором параметров a и c для каждого инверсного конгруэнтного генератора, являющегося компонентом составного генератора. Это означает, что каждый генератор связан с фиксированным полиномом IMP. Такого условия достаточно для максимального периода каждого инверсивного конгруэнтного генератора. и, наконец, для максимального периода составного генератора. Построение полиномов IMP является наиболее эффективным подходом к поиску параметров инверсного конгруэнтного генератора с максимальной длиной периода.

Несоответствие и его границы

Свойства равнораспределения и статистической независимости сгенерированных последовательностей, которые очень важны для их использования в стохастическом моделировании , могут быть проанализированы на основе несоответствия - кортежей s последовательных псевдослучайных чисел с $s=1$ и $s=2$ соответственно.

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

Определение

Для N произвольных точек ${\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}\in [0,1)$ несоответствие определяется $D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})={\rm {sup}}_{J}|F_{N}(J)-V(J)|$,где верхняя грань распространена на все J подинтервалы $[0,1)^{s}$, $F_{N}(J)$ является $N^{-1}$ умноженное на количество очков среди ${\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}$ попадание в J и ⁠ $V(J)$⁠ обозначает s- объём J. мерный

До сих пор у нас были последовательности целых чисел от 0 до ⁠. $T-1$⁠ , чтобы иметь последовательности $[0,1)^{s}$, можно разделить последовательность целых чисел на ее период T .

Из этого определения можно сказать, что если последовательность ${\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1}$ совершенно случайно, то оно хорошо распределено на интервале $J=[0,1)^{s}$ затем $V(J)=1$ и все точки находятся в J, поэтому $F_{N}(J)=N/N=1$ следовательно $D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=0$ но вместо этого, если последовательность сосредоточена близко к одной точке, то подинтервал J очень мал $V(j)\approx 0$ и $F_{N}(j)\approx N/N\approx 1$ так $D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})=1$Тогда мы имеем из лучшего и худшего случая:

$0\leq D_{N}({\mathbf {t} }_{1},\dots ,{\mathbf {t} }_{N-1})\leq 1$.

Обозначения

Необходимы некоторые дополнительные обозначения. Для целых чисел $k\geq 1$ и $q\geq 2$ позволять $C_{k}(q)$ — множество ненулевых точек решетки $(h_{1},\dots ,h_{k})\in Z^{k}$ с $-q/2<h_{j}<q/2$ для $1\leq j\leq k$.

Определять

$r(h,q)={\begin{cases}q\sin(\pi |h|/q)&{\text{for }}h\in C_{1}(q)\\1&{\text{for }}h=0\end{cases}}$

и

$r(\mathbf {h} ,q)=\prod _{j=1}^{k}r(h_{j},q)$

для ${\mathbf {h} }=(h_{1},\dots ,h_{k})\in C_{k}(q)$. Серьезно $t$ аббревиатура $e(t)={\rm {exp}}(2\pi \cdot it)$ используется, и $u\cdot v$ обозначает стандартный внутренний продукт $u,v$ в $R^{k}$.

Верхняя граница

Позволять $N\geq 1$ и $q\geq 2$ быть целыми числами. Позволять ${\mathbf {t} }_{n}=y_{n}/q\in [0,1)^{k}$ с $y_{n}\in \{0,1,\dots ,q-1\}^{k}$ для $0\leq n<N$.

Тогда расхождение точек ${\mathbf {t} }_{0},\dots ,{\mathbf {t} }_{N-1}$ удовлетворяет

$D_{N}(\mathbf {t} _{0},\mathbf {t} _{1},\dots ,\mathbf {t} _{N-1})$ ≤ ${\frac {k}{q}}$ + ${\frac {1}{N}}$ $\sum _{h\in \mathbb {C} _{k}(q)}$${\frac {1}{r(\mathbf {h} ,q)}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}$

Нижняя граница

Несоответствие $N$ произвольные точки $\mathbf {t} _{1},\dots ,\mathbf {t} _{N-1}\in [0,1)^{k}$ удовлетворяет

$D_{N}(\mathbf {t} _{0},\mathbf {t} _{1},\dots ,\mathbf {t} _{N-1})\geq {\frac {\pi }{2N((\pi +1)^{l}-1)\prod _{j=1}^{k}{\rm {max}}(1,h_{j})}}{\Bigg |}\sum _{n=0}^{N-1}e(\mathbf {h} \cdot \mathbf {t} _{n}){\Bigg |}$

для любой ненулевой точки решетки ${\mathbf {h} }=(h_{1},\dots ,h_{k})\in Z^{k}$, где $l$ обозначает количество ненулевых координат ${\mathbf {h} }$.

Эти две теоремы показывают, что CIG не идеален, поскольку расхождение строго больше положительного значения, но также CIG не является худшим генератором, поскольку расхождение меньше значения меньше 1.

Существуют также теоремы, ограничивающие среднее значение невязки для составных инверсивных генераторов, а также теоремы, которые принимают такие значения, что невязка ограничена некоторой величиной, зависящей от параметров. Более подробную информацию смотрите в оригинальной статье.

См. также

• Генератор псевдослучайных чисел
• Список генераторов случайных чисел
• Линейный конгруэнтный генератор
• Обобщенные инверсивные конгруэнтные псевдослучайные числа
• Псевдослучайная функция Наора-Рейнгольда

Внешние ссылки

• Инверсивные генераторы в Зальцбургском университете .