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

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

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

Содержание

1. Описание
2. Свойства
3. Часто используемые параметры
4. Возможность использования в криптографии
5. См. также
6. Примечания
7. Литература
8. Ссылки

Описание

Линейный конгруэнтный метод был предложен Д. Г. Лемером на проходившем в 1949 году симпозиуме и опубликован в 1951 году в трудах симпозиума. Суть метода заключается в вычислении последовательности случайных чисел (X_n), полагая:

[ X_{n+1} = (aX_n + c) \mod m ]

где:

• (m) — модуль (натуральное число, относительно которого вычисляет остаток от деления; (m \geq 2)),
• (a) — множитель ((0 \leq a < m)),
• (c) — приращение ((0 \leq c < m)),
• (X_0) — начальное значение ((0 \leq X_0 < m)).

Эта последовательность называется линейной конгруэнтной последовательностью. Например, для (m=10), (X_0=a=c=7) получим последовательность (7, 6, 9, 0, 7, 6, 9, 0, \ldots).

Свойства

Линейная конгруэнтная последовательность, определенная числами (m), (a), (c) и (X_0), периодична с периодом, не превышающим (m). При этом длина периода равна (m) тогда и только тогда, когда:

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

Метод генерации линейной конгруэнтной последовательности при (c=0) называют мультипликативным конгруэнтным методом, а при (c \neq 0) — смешанным конгруэнтным методом.

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

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

1. Число (m) должно быть довольно большим, так как период не может иметь больше (m) элементов.
2. Значение числа (m) должно быть таким, чтобы ((aX_n + c) \mod m) вычислялось быстро.

На практике при реализации метода чаще всего выбирают (m=2^e), где (e) — число битов в машинном слове.

Таблица хороших констант для линейных конгруэнтных генераторов

Source	m	Множитель a	Слагаемое c	Используемые биты
Numerical Recipes	(2^{32})	1664525	1013904223
Borland C/C++	(2^{32})	22695477	1	bits 30..16 in rand(), 30..0 in lrand()
glibc (used by GCC)	(2^{31})	1103515245	12345	bits 30..0
...	...	...	...	...

Возможность использования в криптографии

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

См. также

• Генератор псевдослучайных чисел
• Инверсный конгруэнтный метод

Примечания

[1] D. H. Lehmer, Mathematical methods in large-scale computing units, 1949.

Литература

Дональд Э. Кнут. Глава 3. Случайные числа // Искусство программирования = The Art of Computer Programming. — 3-е изд. — М.: Вильямс, 2000.