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

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

${ displaystyle x_ {0} =}$ семя
${ Displaystyle х_ {я + 1} эквив (ах_ {я} ^ {- 1} + с) mod q}$	если ${ displaystyle x_ {i} neq 0}$
${ displaystyle x_ {я + 1} = c}$	если ${ displaystyle x_ {i} = 0}$

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

Период

Последовательность ${ Displaystyle (х_ {п}) _ {п geq 0}}$ должны быть ${ displaystyle x_ {i} = x_ {j}}$ после конечного числа шагов и поскольку следующий элемент зависит только от своего прямого предшественника, ${ Displaystyle х_ {я + 1} = х_ {j + 1}}$ и т.д. Максимальная длина, которую период Т для функции по модулю q может быть Т=q. Если многочлен ${ Displaystyle е (х) = х ^ {2} -cx-a in mathbb {F} _ {q} [x]}$ (кольцо полиномов над ${ displaystyle mathbb {F} _ {q}}$) является примитивный, то последовательность будет иметь максимальную длину. Такие многочлены называются инверсивными многочленами максимального периода (IMP). Достаточным условием максимального периода последовательности является правильный выбор параметров а и c согласно алгоритм описан в.^[1]Эйхенауэр-Херрманн, Лен, Гроте и Niederreiter показали, что инверсивные конгруэнтные генераторы обладают хорошими свойствами однородности, в частности, в отношении структуры решетки и последовательных корреляций.

Пример

ICG (5,2,3,1) дает последовательность: (1,0,3,2,4,1, .....) (как в ${ displaystyle in mathbb {F} _ {5}}$, 1 и 4 являются собственными обратными, 2 - обратными 3 и наоборот). ${ Displaystyle е (х) = х ^ {2} -3x-2}$ неприводимо в ${ displaystyle mathbb {F} _ {5} [x]}$ поскольку ни 0,1,2,3, ни 4 не являются корнями, и поэтому период равен q=5.Чтобы показать, что ж примитивно следует показать, что Икс это примитивный элемент из ${ Displaystyle mathbb {F} _ {5} [x] / (f)}$.

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

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

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

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

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

${ displaystyle x_ {n} = T_ {1} x_ {n} ^ {(1)} + T_ {2} x_ {n} ^ {(2)} + dots + T_ {r} x_ {n} ^ {(г)} mod T}$.

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

Пример

Позволять ${ displaystyle p_ {1} = 5}$ и ${ displaystyle p_ {2} = 7 (r = 2)}$. Для упрощения возьмите ${ displaystyle (x_ {n} ^ {(1)}) _ {n geq 0} = (0,1,2,3,4, точки)}$ и ${ displaystyle (x_ {n} ^ {(2)}) _ {n geq 0} = (0,1,2,3,4,5,6, точки)}$. Мы вычисляем для каждого 1≤ j≤ 35, ${ displaystyle x_ {j} = 7x_ {j} ^ {(1)} + 5x_ {j} ^ {(2)} mod 35}$тогда ${ displaystyle (x_ {n}) _ {n geq 0} = (0,12,24,1,13,25,2,14,26,3,15,27,4,16,28,5, 17,29,6,18,30,7,19,31,8,20,32,9,21,33,10,22,34,11,23)}$(мы должны сделать 35 различных сумм, чтобы получить 0 + 0, и мы снова начинаем ту же последовательность, период равен ${ Displaystyle 5 раз 7 = 35 ,}$Этот метод позволяет получить очень длительный период и проводить модульные операции с относительно небольшими модулями.

Преимущества CIG

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

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

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

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

Есть алгоритм ^[7] что позволяет разрабатывать составные генераторы с предсказуемой длиной периода, предсказуемым уровнем линейной сложности, с превосходными статистическими свойствами создаваемых битовых потоков.

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

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

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

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

Определение

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

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

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

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

Обозначения

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

Определять

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

и

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

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

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

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

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

${ Displaystyle D_ {N} ( mathbf {t} _ {0}, mathbf {t} _ {1}, dots, mathbf {t} _ {N-1})}$ ≤ ${ displaystyle { frac {k} {q}}}$ + ${ displaystyle { frac {1} {N}}}$ ${ Displaystyle сумма _ {ч ин mathbb {C} _ {k} (q)}}$${ displaystyle { frac {1} {r ( mathbf {h}, q)}} { Bigg |} sum _ {n = 0} ^ {N-1} e ( mathbf {h} cdot mathbf {t} _ {n}) { Bigg |}}$

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

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

${ displaystyle 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 |}}$

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

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

Существуют также теоремы, которые ограничивают среднее значение расхождения для составных инверсионных генераторов, а также теоремы, которые принимают такие значения, что расхождение ограничено некоторым значением в зависимости от параметров. Подробнее см. Исходный документ.^[9]

Смотрите также

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

Рекомендации

внешняя ссылка

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