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

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

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

Содержание

Описание

Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:

X_{k+1} = (a X_k + c)~~\bmod~~m,

где a и c — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа X_{0} и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства этой последовательности определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа.

Свойства

Последовательность чисел, порождаемая линейным конгруэнтным методом, периодична с периодом, не превышающим m. При этом длина периода в точности равна m тогда и только тогда, когда:[1]

  1. НОД(c,m) = 1 (то есть, c и m взаимно просты);
  2. a-1 кратно p для всех простых делителей p числа m;
  3. a-1 кратно 4, если m кратно 4.

Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором коэффициентов a и c. Для этих констант выписаны[кем?] условия, гарантирующие удовлетворительное качество получаемых случайных чисел.

Часто используемые параметры

При реализации выгодно выбирать m = 2^e, где e — число битов в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.

Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в d-мерном пространстве, точки ложатся не более, чем на m^{1/d} гиперплоскостей, что ограничивает применение генератора в методе Монте-Карло.

В таблице ниже приведены наиболее часто используемые параметры линейных конгруэнтных генераторов, в частности, в стандартных библиотеках различных компиляторов (функция rand()).

Source m a c выдаваемые биты результата в rand() / Random(L)
Numerical Recipes (англ.) 232 1664525 1013904223
MMIX by Donald Knuth 264 6364136223846793005 1442695040888963407
Borland C/C++ 232 22695477 1 биты 30..16 в rand(), 30..0 в lrand()
GNU Compiler Collection 232 69069 5 биты 30..16
ANSI C: Open Watcom, Digital Mars, Metrowerks, IBM VisualAge C/C++ 232 1103515245 12345 биты 30..16
Borland Delphi, Virtual Pascal 232 134775813 1 биты 63..32 числа (seed * L)
Microsoft Visual/Quick C/C++ 232 214013 2531011 биты 30..16
Apple CarbonLib 231 - 1 16807 0 см. Метод Лемера (англ.)

Криптоанализ

Особенностью линейного конгруэнтного метода является то, что если сомножитель и модуль соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от случайной последовательности элементов множества { 0, 1, 2, …, m-1 }. Однако, все элементы этой последовательности однозначно определяются четырьмя параметрами: X0, a, c, m.

Если криптоаналитик знает об использовании линейного конгруэнтного метода с известными параметрами, то известной становится вся последовательность чисел. В то же время, даже если криптоаналитик знает только лишь об использовании линейного конгруэнтного метода, то информация о небольшой части последовательности достаточна для выявления параметров метода и всех последующих элементов последовательности. В частности, если криптоаналитику известны значения  {X_0}, {X_1}, {X_2}, {X_3} , то они удовлетворяют системе уравнений:

\begin{cases} X_{1} = (a\cdot X_{0} + c )~ \bmod~ m\\ X_{2} = (a\cdot X_{1} + c )~ \bmod~ m\\ X_{3} = (a\cdot X_{2} + c )~ \bmod~ m\end{cases}

из которой можно получить значения параметров а, с и m.

Поэтому, хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким.

Примечания

  1. Дональд Кнут, Искусство программирования (Том 2. Получисленные алгоритмы)

Ссылки


Wikimedia Foundation. 2010.

Смотреть что такое "Линейный конгруэнтный метод" в других словарях:

  • Метод Фибоначчи с запаздываниями — (Lagged Fibonacci generator) один из методов генерации псевдослучайных чисел. Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делают невозможным их использование в статистических алгоритмах, требующих… …   Википедия

  • Датчик случайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия

  • Криптостойкий генератор псевдослучайных чисел — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия

  • Псевдослучайное число — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия

  • Псевдослучайные числа — Генератор псевдослучайных чисел (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, генерирующий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному).… …   Википедия

  • Генератор псевдослучайных чисел — (ГПСЧ, англ. Pseudorandom number generator, PRNG)  алгоритм, порождающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются заданному распределению (обычно равномерному). Современная информатика… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

  • Генератор Макларена — Марсальи генератор псевдослучайных чисел, который основан на комбинации двух конгруэнтных генераторов и вспомогательной матрице, с помощью которой происходит перемешивание двух последовательностей, полученных от двух генераторов. Генератор был… …   Википедия

  • Кольцевой хэш — (англ. rolling hash)  хэш функция, обрабатывающая вход в рамках некоторого окна. Получение значения хэш функции для сдвинутого окна (window ) в таких функциях является дешевой операцией. Для пересчета значения требуется знать лишь… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»