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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Линейный конгруэнтный метод — один из методов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.

Описание[править | править вики-текст]

Линейный конгруэнтный метод был предложен Д.Г. Лемером (англ. Derrick Henry Lehmer) в 1949 году.[1] Суть метода заключается в вычислении последовательности случайных чисел X_{n}, полагая

X_{n+1} = (a X_n + c)~~\bmod~~m,

где m – модуль (0 \leqslant m), a – множитель (0 \leqslant a < m), c – приращение (0 \leqslant c < m), X_{0} – начальное значение (0 \leqslant X_{0} < m).

Эта последовательность называется линейной конгруэнтной последовательностью. Например, для m = 10, X_{0} = a = c = 7 получим последовательность 7, 6, 9, 0, 7, 6, 9, 0, \dots [2]

Свойства[править | править вики-текст]

Линейная конгруэнтная последовательность, определенная числами m, a, c и X_{0} периодична с периодом, не превышающим m. При этом длина периода равна m тогда и только тогда, когда[3]:

  1. Числа c и m взаимно простые;
  2. b = a - 1 кратно p для каждого простого p, являющегося делителем m;
  3. b кратно 4, если m кратно 4.

Наличие этого свойства для случая m = 2^e, где e — число битов в машинном слове, было доказано М. Гринбергом (англ. M. Greenberg).[4] Наличие этого свойства для общего случая и достаточность условий была доказано Т. Е. Халлом (англ. T. E. Hull) и А. Р. Добеллом (англ. A. R. Dobell).[5]

Метод генерации линейной конгруэнтной последовательности при c = 0 называют мультипликативным конгруэнтным методом, а при c \neq 0смешанным конгруэнтным методом. При c = 0 генерируемые числа будут иметь меньший период, чем при c \neq 0, но при определенных условиях можно получить период длинной m - 1, если m – простое число.Тот факт, что условие c \neq 0 может приводить к появлению более длинных периодов, был установлен В. Е. Томсоном (англ. W. T. Thomson) и независимо от него А. Ротенбергом (англ. A. Rotenberg).[2] Чтобы гарантировать максимальность цикла повторения последовательности при c = 0, необходимо в качестве значения параметра m выбирать простое число. Самым известным генератором подобного рода является так называемый минимальный стандартный генератор случайных чисел, предложенный Стивеном Парком (англ. Stephen Park) и Кейтом Миллером (англ. Keith Miller) в 1988 году. Для него a = 16807, а m = 2147483647.[6][7]

Наиболее часто практикуемым методом генерации последовательностей псевдослучайных чисел является смешанный конгруэнтный метод.

Линейный конгруэнтный метод с постоянными коэффициентами допускает обобщение на случаи, когда коэффициенты а и с являются переменными.  Линейный конгруэнтный метод с переменными коэффициентами задается уравнением:  X_{n} = ( a_{n-1} X_{n-1} + c_{n-1})\mod m , где X - е-битовая переменная.

Из линейного конгруэнтного метода с переменными коэффициентами следуют его наиболее популярные разновидности:

Квадратичный конгруэнтный метод

X_{n} = ( a X_{n-1}^2 + b X_{n-1} + d )\mod m

Кубический конгруэнтный метод

X_{n} = ( a X_{n-1}^3 + b X_{n-1}^2  + c X_{n-1} + d )\mod  2^e

Регулярный рандомизационный метод с коэффициентами, зависящими от предыдущих элементов последовательности

 X_{n} = ( A_{n-1} X_{n-1} + C_{n-1})\mod m ,

где A_{n-1}= 4X_{n-3} + a , C_{n-1}= 4X_{n-2} + c. Характерной особенностью регулярного рандомизационного метода является наличие зависящего от начальных условий переходного нелинейного участка, после прохождения которого последовательность, благодаря саморегуляции, достигает максимального периода m и далее всюду, в границах каждого из последующих периодов ведет себя стационарно и бесповторно.[8]

Часто используемые параметры[править | править вики-текст]

При выборе числа m необходимо учитывать следующие условия:

1) число m должно быть довольно большим, так как период не может иметь больше m элементов;

2) значение числа m должно быть таким, чтобы ( a X_{n} + c)\mod m вычислялось быстро.

На практике при реализации метода исходя из указанных условий чаще всего выбирают m = 2^e, где e — число битов в машинном слове. При этом стоит учитывать, что младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Подобная ситуация не возникает, когда m = w \pm 1, где w – длина машинного слова. В таком случае младшие разряды X_{n} ведут себя так же случайно, как и старшие.[2] Выбор множителя a и приращения c в основном обусловлен необходимостью выполнения условия достижения периода максимальной длины.

Возможность использования в криптографии[править | править вики-текст]

Хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким. Генераторы на основе линейного конгруэнтного метода являются предсказуемыми, поэтому их нельзя использовать в криптографии. Впервые генераторы на основе линейного конгруэнтного метода были взломаны Джимом Ридсом (Jim Reeds), а затем Джоан Бояр (Joan Boyar). Ей удалось также вскрыть квадратические и кубические генераторы. Другие исследователи расширили идеи Бояр, разработав способы вскрытия любого полиномиального генератора. Таким образом, была доказана бесполезность генераторов на основе конгруэнтных методов для криптографии. Однако, генераторы на основе линейного конгруэнтного метода сохраняют свою полезность для некриптографических приложений, например, для моделирования. Они эффективны и в большинстве используемых эмпирических тестах демонстрируют хорошие статистические характеристики.[9]

Примечания[править | править вики-текст]

  1. D. H. Lehmer, Mathematical methods in large-scale computing units, Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 1949, Harvard University Press, Cambridge, Mass., 1951, pp. 141–146. MR 0044899 (13,495f)[1]
  2. 1 2 3 Дональд Кнут. Том 2. Получисленные методы // Искусство программирования. Указ. соч. — С. 21—37.
  3. Кнут Д. Э., Искусство программирования. Том 2. Получисленные методы - Вильямс. 2001. с.21-37
  4. M. Greenberger, Method in randomness, Comm. ACM 8 (1965), 177-179.[2]
  5. T.E. Hull and A.R. Dobell "Random Number Generators",SIAM Review 4-3(1962),230-254 [3]
  6. "Бакнелл Д.М. Фундаментальные алгоритмы и структуры данных в Delphi. Библиотека программиста. 2002 год. журнал Delphi Informant Magazine. Глава 6.
  7. Stephen K. Park and Keith W. Miller (1988). Random Number Generators: Good Ones Are Hard To Find. Communications of the ACM 31 (10): 1192–1201[4]
  8. Кулаков И.А. Линейные конгруэнтные и рандомизационные генераторы. Москва. 2012[5]
  9. 1 2 Брюс Шнайер. Глава 16. // Прикладная криптография.Триумф.2002. Указ. соч. — С. 275.[6]

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]