logo search
Коды и шифры

Глава 8

8.1 (Рекурренты четвертой степени)

(i) Если положить U0 = U1 = U2 = U3 = 1, то рекуррента

Un = U(n-1) + U(n-4)

порождает последовательность

1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, ...

которая повторяется через 15 шагов, но не ранее.

(ii) При тех же начальных значениях рекуррента

Un = U(n-1) + U(n-2) + U(n-3) + U(n-4)

порождает последовательность

1, 1, 1, 1, 0, 1, 1, 1, 1, ...

которая повторяется всего лишь после пяти шагов.

8.2 (Появление цикла при получении последовательности случайных чисел методом срединных квадратов)

Начиная со значения X=7789, получаем последовательность, которая вырождается в цикл длины 4:

6685, 6892, 4996, 9600, 1600, 5600, 3600, 9600, ... .

8.3 (Длины циклов линейных конгруэнтных генераторов)

  1. Линейный конгруэнтный генератор Un = 3U(n-1) + 7 (mod 19) при начальном значении Un = 1 дает последовательность

10, 18, 4, 19, 7, 9, 15, 14, 11, 2, 13, 8, 12, 5, 3, 16, 17, 1, ...

Длина цикла равна 18 и является максимальной. Число 6 не может встретиться, поскольку оно дает цикл длины 1.

(2) Линейный конгруэнтный генератор Un = 4U(n-1) + 7 (mod 19) при начальном значении Un = 1 дает последовательность

11, 13, 2, 15, 10, 9, 5, 8, 1, ...

Длина цикла равна 9 и не является максимальной. Никакая рекуррента с множителем 4 не дает максимального периода, если модуль равен 19.