31-08-2023
Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.
Содержание |
Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:
где a и c — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства этой последовательности определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа.
Последовательность чисел, порождаемая линейным конгруэнтным методом, периодична с периодом, не превышающим m. При этом длина периода в точности равна m тогда и только тогда, когда:[1]
Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором коэффициентов a и c. Для этих констант выписаны[кем?] условия, гарантирующие удовлетворительное качество получаемых случайных чисел.
При реализации выгодно выбирать , где e — число битов в машинном слове, поскольку это позволяет избавиться от относительно медленной операции приведения по модулю.
Младшие двоичные разряды сгенерированных таким образом случайных чисел демонстрируют поведение, далёкое от случайного, поэтому рекомендуется использовать только старшие разряды. Кроме того, при использовании этого генератора для выбора точек в 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.
Если криптоаналитик знает об использовании линейного конгруэнтного метода с известными параметрами, то известной становится вся последовательность чисел. В то же время, даже если криптоаналитик знает только лишь об использовании линейного конгруэнтного метода, то информация о небольшой части последовательности достаточна для выявления параметров метода и всех последующих элементов последовательности. В частности, если криптоаналитику известны значения , то они удовлетворяют системе уравнений:
из которой можно получить значения параметров а, с и m.
Поэтому, хотя линейный конгруэнтный метод порождает статистически хорошую псевдослучайную последовательность чисел, он не является криптографически стойким.
Линейный конгруэнтный метод.