Аддитивный генератор. 
Криптографические методы защиты информации

Аддитивный генератор оперируют с элементами кольца Z2″ вычетов по модулю 2″. Выходная последовательность образуется по правилу:

где Хо, Х,…, X_m_i — начальные знаки выхода, ао, си,…, а_т_i — заданный набор целых чисел.

Если числа aj е {0,1} и выбраны так, что многочлен.

является примитивным, то это гарантирует для последовательности младших разрядов, а значит, и для всей последовательности {Xj} период не меньше 2^m — 1.

Линейный конгруэнтный генератор

Последовательность Xj, j — 0,1,… над кольцом Z" вычетов по модулю п вырабатывается по закону.

где Хо ~ начальное значение, a, b € Z_n — заданные параметры генератора.

Упражнение 6.4.1. Доказать, что ш — период данной последовательности — не превосходит п.

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

Теорема 6.14. Последовательностъ (6.12) имеет максимальный период uj = п в том и только том случае, если:

• 1. НОД (Ь, п) = 1,
• 2. Для любого простого делителя р числа п выполнено р (а — 1), т.е. а — 1 кратно р.^[1]

Упражнение 6.4.2. Доказать, что при условии НОД (b, п) = d > 1 период и < п. Указание: докажите, что любой элемент последовательности будет кратен числу d.

Упражнение 6.4.3. Пусть НОД (b, п) = 1, п = 0 (modp), а также (а — 1) ф 0 (modp), где р — простое. Доказать, что период ш < п. Указание: докажите, что число различных остатков от деления на р элементов выходной последовательности будет меньше р.

Упражнение 6.4.4. Пусть выполнены условия 1) и 2) теоремы 6.14. Пусть п = 0 (mod 4), (а — 1) ф 0 (mod 4). Доказать, что период и < п. Указание: докажите, что число различных остатков от деления на 4 элементов выходной последовательности будет меньше четырех.

• [1] Если п = 0 (mod 4), то, а — 1 = 0 (mod 4).