Rtf template

3.4 Примеры генераторов псевдослучайных последовательностей
3.4.1 Алгоритм середины квадрата 
Исторически одним из первых ГПСП был предложенный в 1946 г. Дж. фон 
Нейманом алгоритм «середины квадрата», состоящий из следующих шагов: 
1.
Выбирается 
n
-разрядное начальное случайное рациональное десятичное 
число 
x
i
(его источником может быть ГСП). 
2.
На каждом следующем шаге вычисляется квадрат 
y
i
этого числа 
(2
n
-разрядное число). 
3.
В качестве очередного случайного n-разрядного числа 
x
i+1
выбираются 
n
средних разрядов квадрата предыдущего числа 
y
i
. 
Однако полученные таким способом числа оказываются связанными между 
собой. Кроме того, последовательность этих чисел имеет малый период. 
3.4.2 Линейные конгруэнтные генераторы 
Целое число 
a
конгруэнтно целому числу 
b
по модулю 
n
, если разность (
a
−
b
) 
делится на 
n
без остатка [7, 9, 23]. При этом остатки от деления на 
n
как 
a
, так и 
b
равны. Конгруэнтность чисел записывается с помощью соотношения 
a
≡
b
(mod 
n
). 
(3.1) 
В генераторах такого типа формирование ПСП выполняется с помощью 
следующего рекуррентного алгоритма: 
x
i
+1
=(
ax
i
+
b
) mod 
n
, 
(3.2) 

---

30 
т.е. очередной элемент ПСП получается применением операции деления по 
модулю 
n
к линейно преобразованному предыдущему элементу ПСП 
x
i
. 
Параметрами линейного конгруэнтного генератора (ЛКГ) являются: 

модуль 
n
; 

множитель (мультипликатор) 
a
; 

приращение (инкремент) 
b
; 

начальное значение (
seed
) 
x
0
. 
Параметры 
a
, 
b
, 
x
0
– целые числа из отрезка [0,
n
]. От их значений 
существенно зависит качество выходной ПСП. При неудачных сочетаниях 
параметров можно получить последовательность с малым периодом. 
Известно [1], что выходные последовательности ЛКГ имеют так 
называемую «решетчатую» структуру, т.е. являются легко предсказуемыми и не 
могут применяться в криптографичесих целях. 
Доказано [1], что определяемая формулой (3.1) линейная конгруэнтная 
последовательность имеет максимальную длину периода 
n
тогда и только тогда, 
когда: 

b
и 
m
являются взаимно простыми числами; 

число (
a
-1) кратно некоторому простому делителю 
n
; 

число (
a
-1) кратно 4, если число 
n
кратно 4. 
Следует заметить, что выполнение указанных условий обеспечивает 
максимальный период ПСП, но не гарантирует ее качество. 
Для 
отбрасывания 
ЛКГ, 
порождающих 
заведомо 
неслучайные 
последовательности, используют понятие потенциала 
s
линейной конгруэнтной 
последовательности с максимальным периодом – наименьшего целого числа, 
такого, что (
a
-1)
s
=0 mod 
n
[7]. При 
s
={1; 2} последующие элементы выходной 
ПСП линейно зависят от предыдущих. Такие последовательности лишены 
необходимых свойств ПСП. В случае 
s
={3; 4} последовательность более похожа 
на ПСП, но любой ее элемент по-прежнему существенно зависит от соседних с 
ним. Считается, что начиная с 
s
=5 последовательности ЛКГ могут иметь 
достаточную степень случайности (что требует подтверждения с помощью 
различных статистических тестов, т.к. большое значение потенциала – это только 
необходимое, но не достаточное условие случайности ПСП). 
В [1, 4, 9] приводятся наборы параметров для построения ЛКГ 
максимального периода. 
Если инкремент 
b
=0, формула (3.2) приобретает вид 
x
i
+1
=
ax
i
mod 
n
. 
(3.3) 

---

31 
Частным случаем такого ЛКГ является генератор Парка-Миллера, 
параметры которого 
a
, 
b
, 
n
соответственно равны 75, 0 и 2
31
-1=2147483647.
Развитием линейного конгруэнтного генератора являются полиномиальные 
генераторы (квадратичный, кубический, произвольной степени). Для таких 
генераторов в формуле (3.2) линейное выражение заменяется полиномом нужной 
степени, и, соответственно, увеличивается количество параметров. 
Линейные конгруэнтные генераторы имеют простой алгоритм и высокую 
скорость работы. Они неприменимы для задач криптографии, но могут 
использоваться в различных приложениях, не требующих криптостойкости ПСП 
(моделирование, лотереи, компьютерные и азартные игры, индустрия 
развлечений).