Конгруэнтные генераторы
Линейные конгруэнтные генераторы
Пусть x0, a, c Є Vn — случайно фиксированные элементы. Обычно говорят, что последовательность x1, x2, … Є Vn создается линейным конгруэнтным генератором с параметрами (xn, a, c, N), если такая последовательность удовлетворяет рекуррентному соотношению:
- xi+1 = (axt + c) mod N, t = 0,1,2,…; (формула №1)
Характеристика x0 Є Vn называют начальным параметров, a ≠ 0 — множителем, с — приращением, N — сила алфавита за модулем. Если c = 0, то (формула №1) определяет мультипликативный конгруэнтный генератор, а если c ≠ 0 — смешанный конгруэнтный генератор. Нужно отметить, что Д. Лемер предложил мультипликативный конгруэнтный генератор в 1948 году, а У. Томсон смешанный конгруэнтный генератор в 1958 году.
Теорема 1.
Для любых K ≥ 1, t ≥ 0 общий показатель конгруэнтной последовательности (формула №1) удовлетворяет соотношению xi+k:
- (xi +kc) mod N, если a = 1
- (akxi + (ak-1)/(a-1)×c) mod N, если a > 1
- Формула №2
при этом будет такой номер 0 ≤ T ≤ N — 1, что последовательность (формула №1), начиная с этого номера T, зацикливается с периодом 1 ≤ U ≤ N, таким, что T + U ≤ N:
- x0, x1, …, xT, …, xT+U-1 — различный
- xT+U = xT, t ≥ T
- Формула №3
Доказательство
Соотношение (формула №2) получается К-кратным рекурсивной реализации соотношение (формула 1) с учетом известного равенства:
- 1+ a + a2 + … + ak-1 = (ak-1)/(a-1)
Факт зацикливания последовательности {xt} вытекает из вида рекуррентного соотношения (формула 1). Действительно, множество разрешимых значение xt, не может иметь других элементов, кроме элементов множества {0, 1, …, N — 1} силы N. Однако, если для некоторого наименьшего значения индекса t` совпали компоненты последовательности xt` = xt«, где t« — t` = U, то такое соотношение сохранится и для следующих значений индексов:
- xt = xt+u, t = t` + 1, t` + 2, …
Из (формула №2) видно, что при a = 1 нецелесообразно реализовывать для имитации РРСП.
Следствие теоремы 1
Для любого k ≥ 1 при a > 1 подпоследовательность [x0, xk,x2k, x3k…] взятая из конгруэнтной последовательности (формула 1) удалением всех членов с номерами, не кратными k, является линейной смешанной конгруэнтной последовательностью с параметрами (x0,a¬,c¬,N), где a¬ = ak mod N, c¬ = (ak-1)/(a-1) mod N.
Доказательство
Исследуемую подпоследовательность обозначим xi = xik, i = 0,2,.. Тогда (формула №2) будет иметь вид:
- x¬i+1 = (a¬x¬i + c¬) mod N, i = 0,1,2,..
Что и видно, согласно (формула 1), конгруэнтную последовательность с новыми параметрами.
Следствие 2
Для общего члена линейной смешанной конгруэнтной последовательности (формула 1) при a > 1:
- xk = ((akx0) + (ak-1)/(a-1) × C) mod N, k = 1,2..
- Формула №4
Доказательство
Полагая в (формула 2) t = 0, получаем (формула 4).
Следствие 3
Максимальное возможный период конгруэнтной последовательности (формула 4) не превышает силы текущего алфавита Umax ≤ N.
Доказательство
Из теоремы 1, U ≤ N — T, где 0 ≤ T ≤ N — 1. Поэтому Umax ≤ N.
Одной из главных задач при создании конгруэнтного генератора является поиск значений x0,a,c для которых период достигает максимально разрешимого значение Tmax. Тонкости программного использования такого генератора (формула 1) приводит к трём самым реализуемым вариантам задания модуля N:
- N = 2q, где q + 1: число двоичных разрядов ЭВМ, нужных для целочисленной арифметики
- N = 10q, q ≥ 1
- N — простое число
Теорема 2
Для линейной конгруэнтной последовательности (формула 1) максимальное значение периода Umax = N достигается, когда выполнены следующие условия:
- c и N — взаимно простые числа
- число b = a — 1 кратно P для любого числа P, являющегося делителем N
- число b кратно 4, если N кратно 4
Теорема 3
Если с = 0, то максимально возможный период мультипликативной конгруэнтной последовательности равен Umax = λ(N) и достигается, если x0 и N — взаимно простые числа и а — первообразный элемент по модулю N (aλ(N))
Следствие 4
Если N = 2q, q ≥ 4, то максимальное значение периода Umax = 2q-2 = N/4 достигается, если x0 ≥ 1 — нечётное число и a (mod8) Є {3,5}.
Теорема 4
Если c = 0, N = 10q, q ≥ 5 и x0 не кратно двум или пяти, то максимально разрешимое значение периода Umax = 5 × 10q-2 = N/20 достигается тогда, когда вычет a (mod 200) принимает одно из следующих 32 магических значений:
- 3, 11, 13, 19, 21, 27, 29, 37, 53, 59, 61, 67, 69, 77, 83, 91, 109, 117, 123, 131, 133, 139, 141, 147, 163, 171, 173, 179, 181, 187, 189, 197
Теорема 5
Если c = 0, x0 и N — простое число, то максимально разрешимое значение периода Umax = N — 1 достигается, если a (mod N) ne; 0 и :
- a(N-1)/pj — 1 ≠ 0 (mod N), j = 1, s‾1
где p1… ps — простые числа, определяющие каноническое разложение числа N — 1: N — 1 = p1m1…, а m1.. — некоторые натуральные числа.
К примеру.
N = 25 — 1 = 31, N — 1 = 2 × 3 × 5, так что s = 3, p1 = 2, p2 = 3, p3 = 5. Согласно теореме 5, получаем следующие ограничения на выбор множителя a:
- a ≠ 0 (mod 31), a15 — 1 ≠ 0 (mod 31)
- a10 — 1 ≠ 0 (mod 31), a6 — 1 ≠ (mod 31)
Нужно отметить, что в мультипликативных конгруэнтных генераторах РРСП для ПК Pentium часто используют модуль N = 231 — 1 = 2147483647. При этом рекомендуемыми значениями множителя а являются следующие числа:
- 16807, 630360016, 1078318381, 1203248318, 397204094, 2027812808, 13232572445, 764261123, 112718
При этом достигается максимальное значение периода Umax = N — 1 ~ 2.14 * 109.
Линейные конгруэнтные генераторы псевдослучайных последовательностей имеют слабость, которая может быть взята в основу криптоатак. Если смотреть последовательность биграммы (z1, z2): z1 = xt, z2 = xt+1, то в силу (формула 1) на плоскости R2 точки (z1,z2) будут лежать на прямых семейства:
- z2 = az1 + c — kN, k Є {0,1,2..}
Если бы {xt} являлась РРСП, то точки z1,z2 были бы распределены равномерно. На рис.1 видна диаграмма рассеяния для простого смешанного конгруэнтного генератора (для 64 последовательных значений).
- xt+1 = (9xt + 13) (mod 64), x0 = 0
- z2 = 9z1 + 13 — 64k, k Є {0,1..,9}
Рисунок — 1, Диаграмма рассеяния для М = 64
На рис.2 показано диаграмма рассеяния для генератора 500 значения:
- xt+1 = (16807xt + 13) (mod (231 — 1)), x0 = 0
Рисунок 2, Диаграмма рассеяния для M = 231 — 1
Для скрытия этих недостатков реализуют нелинейные конгруэнтные генераторы.
Нелинейные конгруэнтные генераторы
Квадратичный конгруэнтный метод
- zt+1 = (dx2t + axt + c) mod N, t = 0,1,2…
Характеристики (x0, a, c, d, N) Є V4N × N квадратичной конгруэнтной последовательности (следствие 5) реализует максимально возможный период Umax, определяются теоремой 6.
Теорема 6
Квадратичная конгруэнтная последовательность (следствия 5) имеет самый больший период Umax = N тогда, когда реализованы следующие 4 условия:
- c и N — взаимно простые числа
- d и a — кратные Р, где Р — любой нечётные простой делитель для N
- d — чётное число, причём d = a — 1 (mod 4), если N кратно 4, и d = a-1 (mod 2), если N кратно двум
- если N кратно девяти, то либо d (mod 9) = 0, либо d (mod 0) = 1 и cd(mod9) = 6
Следствие 5
Если N = 2q, q ≥ 2, то самый больший период Umax = 2q для квадратичной конгруэнтной последовательности, достигается тогда, когда C нечётно, d чётно, а a — нечётное число:
- a = ( d + 1) mod 4
Квадратный метод Ковэю
- xt+1 = (xt(xt+1))mod2q, t = 0,1,2..
Где модуль N = 2q, q ≥ 2, а начальное значение x0 выбирается так, что x0 (mod 4) = 2. Максимальное значение периода Umax = 2q-2 = N/4. Для повышения компьютерного быстродействия этого нелинейного генератора целесообразно выбирать q равным числу двоичных разрядов, нужных для записи целого числа в ЭВМ (к примеру q = 31)
Метод середины квадрата
- xt+1 = (xt2(mod 23q) — xt2(mod 2q))/2q, t = 0,1,2..
где q, x0 — параметры этого нелинейного генератора псевдослучайной последовательности. Начальное значение x0 ≠ 1 выбирается среди натуральных чисел, не превосходящих числа 22q — 1, так, чтобы x20 (mod 2q) ≠ 0. Этот метод первым предложил Джоном фон Нейманом в 1946 году.