| | | | | | | | | | | | | | | | | | | | | | | | | | | Г | е | н | е | р | а | т | о | р | ы | | с | л | у | ч | а | й | н | ы | х | | ч | и | с | е | л | | | | | | | | | | | | | | | | | | | | | | | | | | |
| 31.5.97 | |
| Алгоритм 1. |
| Линейный конгруэнтный генератор (Лемер, | 1948 | ) |
| Пусть m, a, c, x0 - целые числа, причем m>x0, m>a, m>c и x0>=0, a>=0, c>=0. |
| Тогда псевдослучайное число из последовательности (xi) получается из |
| предшествующего числа ему числа xi-1 как xi = (axi-1 + c) mod m |
| |
| При соответствующем выборе m, a, c и x0 алгоритм 1 выдает последовательность |
| случайных чисел. При c = 0 получается мультипликативный конгруэнтный |
| генератор. |
| |
| Теорема 1. |
| (Кармайкл, | 1910 | ) |
| Мультипликативный конгруэнтный генератор имеет период m-1 при выполнении |
| следующих условий: |
| a) m - простое число; |
| б) a - первообразный корень из m, т.е. a^m = 1 mod m и для любого n < m a^n <> |
| 1 mod m. |
| |
| для 32-битных целых чисел в качестве m можно взять m = 2^31 - 1 = 2147483647 |
| |
| Алгоритм 2. |
| Генератор на базе сдвигового регистра с обратной связью (Таусворт, 1965) |
| Пусть ci (i=1,...,n) - множество целых чисел, имеющих значения 0 или 1, cn = |
| 1. Тогда последовательность псевдослучайных чисел x = (xk) генерируется с |
| помощью линейного рекуррентного соотношения |
| xk = (c1xk-1 + c2xk-2 + ... + cnxk-n) mod 2 |
| |
| Для периода равного 2^n - 1, необходимо и достаточно, чтобы полином |
| f(x) = 1 + c1x + c2x^2 + ... + x^n |
| являлся примитивным полиномом по модулю 2 над полем GF(2). Практически весь |
| список примитивных полиномов над GF(2) ограничивается трехчленами вида |
| f(x) = x^p + x^q + 1, |
| где p - показатель Мерсена (2^p - 1 является простым числом) и p > q > 0. |
| Широко применяется полиномы при p = 250, q = 108 и p = 532, q = 37 |
| |
| |