2015-10-22
1146
Статья на Хабре - http://habrahabr.ru/post/151187/
5.1 Псевдослуча́йная после́довательность (ПСП) — последовательность чисел, которая была вычислена по некоторому определённому арифметическому правилу, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи.
Хотя псевдослучайная последовательность в этом смысле часто, как может показаться, лишена закономерностей, однако, любой псевдослучайный генератор с конечным числом внутренних состояний повторится после очень длинной последовательности чисел. Это может быть доказано с помощью принципа Дирихле.
5.1 Линейная конгруэнтная последовательность
Линейный конгруэнтный метод — один из алгоритмов генерации псевдослучайных чисел. Применяется в простых случаях и не обладает криптографической стойкостью. Входит в стандартные библиотеки различных компиляторов.
Описание
Линейный конгруэнтный метод заключается в вычислении членов линейной рекуррентной последовательности по модулю некоторого натурального числа m, задаваемой следующей формулой:
|
|
|
где a и c — некоторые целочисленные коэффициенты. Получаемая последовательность зависит от выбора стартового числа 
и при разных его значениях получаются различные последовательности случайных чисел. В то же время, многие свойства этой последовательности определяются выбором коэффициентов в формуле и не зависят от выбора стартового числа.
Свойства
Последовательность чисел, порождаемая линейным конгруэнтным методом, периодична с периодом, не превышающим m. При этом длина периода в точности равна m тогда и только тогда, когда:[1]
- НОД(c,m) = 1 (то есть, c и m взаимно просты);
- a-1 кратно p для всех простых делителей p числа m;
- a-1 кратно 4, если m кратно 4.
Статистические свойства получаемой последовательности случайных чисел полностью определяются выбором коэффициентов a и c. Для этих констант выписаны[кем?] условия, гарантирующие удовлетворительное качество получаемых случайных чисел.
