Rtf template

3.4.3 Аддитивные
генераторы псевдослучайных последовательностей
Дальнейшее развитие идеи ЛКГ состоит в связывании очередного элемента 
выходной ПСП не с одним, а с двумя предыдущими элементами. 
Наиболее известным примером последовательности, в которой очередной 
элемент зависит от двух предшествующих, является последовательность 
Фибоначчи. Аддитивный генератор Фибоначчи использует формулу 
x
i
+1
=(
x
i
+
x
i
-1
) mod 
n
. 
(3.4) 
Период такого генератора, как правило, больше, чем у ЛКГ с тем же 
значением модуля 
n
. Тем не менее, качество полученных таким образом ПСП 
оказывается недостаточным для использования их в тех случаях, когда требуется 
высокая степень случайности. 
Для преодоления недостатков генератора Фибоначчи был предложен его 
вариант со следующей формулой общего члена последовательности: 
x
i
+1
=(
x
i
-
j
+
x
i
-
k
) mod 
n
, 
(3.5) 
Входящие в индексы формулы (3.5) значения 
k
и 
j
, для которых должно 
выполняться условие 
k
>
j

1, называются запаздываниями, а соответствующий 
генератор называется генератором Фибоначчи с запаздыванием. Для его 
максимально возможного периода существует оценка [7], обычно формулируемая 
в виде следующей теоремы: 
Если многочлен 
x
j
+
x
k
+1 является примитивным многочленом над конечным 
полем (полем Галуа) второго порядка 
GF
(2) (см. раздел 1), то период 
соответствующего генератором Фибоначчи с запаздыванием равен числу 
2
log
2
n
-1
(2
k
-1). 

---

32 
Один из генераторов этого семейства (Дж.Ж. Митчел, Д.Ф. Мур) 
определяется формулой 
x
i
=(
x
i
-24
+
x
i
-55
) mod 
n
, 
i

55, 
где 
n
– четное число, 
x
0
,…, 
x
54
– произвольные целые числа. 
Известен мультипликативный вариант генератора Фибоначчи (Дж. 
Марсалья), для которого в формуле (3.5) вместо сложения используется операция 
умножения. Максимально возможный период такого генератора, реализуемый при 
уже приводившихся условиях на 
j
и 
k
, равен 
2
log
2
n
-3
(2
k
-1). 
Применимые на практике величины запаздываний приводятся, например, в 
[1, 9]. Следует иметь в виду, что с ростом этих величин при программной 
реализации генератора увеличивается потребность в памяти, что снижает 
эффективность алгоритма. 
Помимо этого, при тестировании выходной последовательности 
мультипликативного генератора Фибоначчи (как и ЛКГ) проявляется ее 
решетчатая структура [4]. 
Такую же особенность структуры сохраняют последовательности, 
сгенерированные с помощью более сложно организованного алгоритма, в котором 
очередной элемент зависит от произвольного количества предшествующих 
элементов: 
x
i
=(
a
1
x
i
-1
+…+
a
k
-1
x
i
-
k
+1
+
a
k
) mod 
n
. 
(3.6) 
В некоторых условиях коэффициенты линейной комбинации в правой части 
формулы (3.6) могут быть определены таким образом, чтобы период 
последовательности был максимально возможным. Способ нахождения 
коэффициентов реализуется средствами теории конечных полей и представляет 
собой сложную математическую задачу. 
Аддитивные генераторы имеют высокую производительность, но не 
являются криптостойкими. Они используются как вспомогательные блоки в 
составе стойких ГПСП. Также они служат основой некоторых криптоалгоритмов 
(Fish, Pike, Mush) [9].