Генераторы псевдослучайных чисел. Линейный конгруэнтный генератор

Примером генератора псевдослучайных чисел (ПСЧ) является линейный конгруэнтный датчик ПСЧ:

Т_i+1 = (A*T_i + C) mod M, (1)

где M – модуль генератора, А и С – неотрицательные константы, меньшие модуля M, Т₀ – начальное значение генератора. Величины А, С, Т₀ образуют ключ генератора ПСЧ. Значение M обычно выбирается достаточно большим.

Такой датчик ПСЧ генерирует псевдослучайные числа с максимальным периодом повторения M, зависящим от значений А и С, при выполнении условий следующего утверждения.

Утверждение. Длина периода последовательности T_i, определяемой формулой (1), равна М в том и только том случае, если

1) С и М взаимно просты;

2) B = A – 1 кратно p для любого простого p – делителя M;

3) если M кратно 4, то и B кратно 4.

Для получения последовательности, принимающей значения из отрезка [0,1], нормируем последовательность T_i по формуле

R_i = T_i /M. (2)

Для оценки равномерности распределения последовательности R на отрезке [0,1] построим гистограмму. Для этого отрезок [0,1] разбиваем на t (например, t=8) равных частей и подсчитываем количество ПСЧ, попавших в каждый отрезок. В MathCAD используем функцию hist (t, R), которая возвращает вектор значений – количество ПСЧ, попавших в j -тый интервал.

Рисунок 1 – Гистограмма распределения последовательности из 64 ПСЧ на отрезке [0,1].

Контрольные вопросы

1. Дайте определение псевдослучайной последовательности.

2. Для какой цели применяют последовательности ПСЧ.

3. Опишите известные генераторы ПСЧ.

4. Какими свойствами должны обладать генераторы ПСЧ для использования их в криптографии.

5. Как оценить равномерность и случайность последовательности ПСЧ.

6. Какие методы применяют для улучшения качеств последовательности ПСЧ.