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

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

 

Т_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. Какие методы применяют для улучшения качеств последовательности ПСЧ.