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

В большинстве языков программирования именно этот метод используется в стандартной функции получения случайных чисел. Впервые этот метод был предложен Лехмером в 1949 году. Выбирается 4 числа:

1. Модуль m (m>0);

2. Множитель a (0<=a<m);

3. Приращение c (0<=c<m);

4. Начальное значение X₀ (0<= X₀<m)

Последовательность получается с использование следующей рекуррентной формулы: X_n+1=(a* X_n+c) mod m.

Этот метод даёт действительно хорошие псевдослучайные числа, но, если взять числа m, a, c произвольно, то результат нас скорее всего разочарует.

Очевидно, что эта последовательность не совсем подходит под определение случайной. Тем не менее, этот провал позволил нам сделать два важных вывода:

1) Числа m,a,c, X₀ не должны быть случайными;

2) Линейный конгруэнтный метод даёт нам повторяющиеся последовательности.

На самом деле любая функция, отображающая конечное множество X в X, будет давать циклически повторяемый значения. Т.о. наша задача состоит в том, чтобы максимально удлинить уникальную часть последовательности (кстати, очевидно, что длина уникальной части не может быть больше m).

Не вдаваясь в подробности доказательств, скажем, что период последовательности будет равен m только при выполнении следующих трех условий:

1) Числа c и m взаимно простые;

2) a-1 кратно p для каждого простого p, являющегося делителем m;

3) Если m кратно 4, то и a-1 должно быть кратно 4.

В завершении рассказа о линейном конгруэнтном методе надо сказать, что последовательности, получаемые с его помощью, хоть и являются в достаточном смысле случайными, тем не менее не являются криптографически стойкими. Т.к. зная 4 подряд идущих числа, криптоаналитик может составить систему уравнений, из которых можно найти a,c,m.