Один из существенных недостатков генератора является то, что он недостаточно быстр, что не позволяет использовать его во многих областях. Например, при вычислениях в реальном времени, а также при потоковом шифровании.
Главное достоинство генератора - алгоритм выдает действительно хорошую последовательность псевдослучайных чисел с большим периодом (при соответствующем выборе исходных параметров), что позволяет использовать его для криптографических целей при генерации ключей для шифрования. лемер эйченауэр конгруэнтный квадратичный
Инверсный конгруэнтный метод был предложен Эйченауэром и Лехном в 1986 году [4] как замена линейному конгруэнтному методу, не обладающему решётчатой структурой [5].
Данный метод состоит в вычислении последовательности случайных чисел xn в кольце вычетов по модулю натурального числа n.
Основным отличием от линейного метода является использование при генерации последовательности числа, обратного к предыдущему элементу, вместо самого предыдущего элемента.
Параметрами генератора являются [6]:
seed - соль,
a - множитель (0 ? a < n),
b - приращение (0 ? b < n).
В случае простого n значение членов последовательности задается в виде (1.7) и (1.8):
x0 = seed, (1.7)
xi+1 (a + b) mod n. (1.8)
Параметры подбираются таким образом, чтобы (1.9) и (1.10):
(seed, n) = 1; (1.9)
(a, n) = 1. (1.10)
Последовательность, формируемая инверсным конгруэнтным генератором, определенным числами a, b и n, имеет максимальный период, равный n + 1, когда многочлен f(x) = x2 - cx - a обладает следующими свойствами:
1. xp+1 mod f(x) равняется отличной от нуля константе;
2. x(p+1)/q mod f(x) имеет степень 1 для каждого простого q, делящего значение p + 1.
Значение p + 1 является исключительно теоретическим, так как получается в предположении, что 0-1 = ? и ?-1 = 0. На практике обычно полагают 0-1 = 0, в этом случае максимальный период равен p.
В качестве примера рассмотрим инверсный конгруэнтный генератор с параметрами n = 5, a = 2, b = 3, seed = 1. Он генерирует последовательность {1,0,3,2,4,1, …} в кольце F5, где числа 1 и 4, а также 2 и 3 обратны друг другу. В данном примере многочлен f(x) = x2 - 3x - 2 неприводимом в F5[x] и числа 0,1,2,3,4 не являются его корнями, благодаря чему период максимален и равен n = 5.
В инверсных конгруэнтных генераторах отсутствует «решетчатая» структура.
Список литературы
1 Дональд Э. Кнут. Искусство программирования. -- 3-е изд. -- М.: Вильямс, 2000. -- Т. 2. Получисленные алгоритмы. -- 832 с.
2 Л. Бараш Алгоритм AKS проверки чисел на простоту и поиск констант генераторов псевдослучайных чисел // Безопасность информационных технологий. -- 2005. -- № 2. -- с. 27-38.
3 Stephen K. Park and Keith W. Miller Random Number Generators: Good Ones Are Hard To Find. -- 1988. -- № 2. -- с. 1192-1201.
4 Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi.Библиотека программиста. // Delphi Informant Magazine. -- 2002.
5 Дональд Кнут. Том 2. Получисленные методы // Искусство программирования. Указ. соч. -- с. 21--37.
6 M. Greenberger, Method in randomness, Comm. ACM 8 -- 1965 -- с. 177--179.
7 T.E. Hull and A.R. Dobell «Random Number Generators», SIAM Review 4-3 -- 1962 -- с. 230-254.