Алгоритмы генерации псевдослучайных последовательностей.

Классификация существующих алгоритмов генерации псевдослучайных последовательностей представлена на рис. Выделяются три основных подхода к построению алгоритмов генерации:

1). Прямые методы построения элементарных рекуррентных последовательностей:

.

2). Методы «улучшения элементарных последовательностей», заключающиеся в специальных функциональных преобразованиях этих последовательностей для уменьшения отклонения их статистических свойств от свойств РРСП.

3). Комбинирование алгоритмов генерации, построенных с помощью первого или второго подхода.

Линейные и мультипликативные конгруэнтные генераторы. Линейным конгруэнтным генератором (ЛКГ) с параметрами ( ) называется программный генератор РРСП, порождающий псевдослучайную последовательность , , с помощью рекуррентного соотношения

                                                        (3.2.1)

Параметры этого генератора (3.2.1) имеют следующий смысл:

 - начальное или стартовое значение;

 - не нулевой множитель;

 - приращение;

 - модуль, равный мощности алфавита .

Если приращение , то генератор ( ) называется мультипликативным конгруэнтным генератором (МКГ), а если , то смешанным конгруэнтным генератором (СКГ).

«Слабость» ЛКГ и МКГ заключается в том, что если рассматривать последовательные биграммы , то точки , на плоскости  будут лежать на прямых из семейства . Для устранения этого недостатка нелинейные конгруэнтные генераторы, среди которых известны: квадратичный конгруэнтный генератор; Генератор Эйхенауэра-Лена с обращением; конгруэнтный генератор, использующий умножение с переносом.

Квадратичный конгруэнтный генератор. Этот алгоритм генерации псевдослучайной последовательности  определяется квадратичным рекуррентным соотношением

,                                            ( )

где – параметры генератора. Выбор этих параметров осуществляется на основе следующих двух свойств последовательности ( ).

Свойство . Квадратичная конгруэнтная последовательность ( ) имеет наибольший период , тогда и только тогда, когда выполнены следующие условия:

1). – взаимно простые числа;

2). – кратны , где – любой нечётный простой делитель ;

3). – чётное число, причем

4). Если кратно 9, то либо , либо  и .

Свойство . Если , то наибольший период тогда и только тогда, когда – нечётно, – чётно, – нечётное число, удовлетворяющее соотношению

.

Генератор Эйхенауэра-Лена с обращением. Псевдослучайная нелинейная конгруэнтная последовательность Эйхенауэра-Лена с обращением определяется следующим нелинейным рекуррентным соотношением :

                                                 (

где – обратный к  элемент по модулю , т.е.  - параметры генератора.

Конгруэнтный генератор, использующий умножение с переносом. В этом случае нелинейная псевдослучайная последовательность определяется рекуррентным соотношением:

                                                         (

Где в отличие от ( ), «приращение»  изменяется во времени и зависит от указанных аргументов нелинейно:

                                                                     ( )

Параметрами нелинейного конгруэнтного генератора ( ), ( ) является .

Рекуррентны в конечном поле. Обращение мультикапликативной конгруэнтной последовательности является линейная рекуррентная последовательность порядка над конечным полем  ( - простое число):

                            ( )

где  – коэффициенты рекуррентны, а  – начальные значения рекуррентны.

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

                                                   ( )

являлся примитивным многочленом по модулю , т.е. многочлен ( ) имел корень *, являющийся первообразным элементом поля . При таком выборе параметров достигается максимально возможный период  псевдослучайной последовательности ( ).

Генераторы Фибоначчи. Общий вид рекуррентного соотношения, определяющего генератор Фибоначчи задаётся уравнением

,                                          ( )

где  – параметры генератора, . В случае  или  - целые числа .