Глава 8

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

(i) Если положить U₀ = U₁ = U₂ = U₃ = 1, то рекуррента

U_n = 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) При тех же начальных значениях рекуррента

U_n = 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. Линейный конгруэнтный генератор U_n = 3U_(n-1) + 7 (mod 19) при начальном значении U_n = 1 дает последовательность

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

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

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

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

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

Глава 9

9.1 ("мини-Энигма")

По шифрованным парам одинаковых знаков можно построить цепочки

0239, 1648, 55 и 77.

Имея первый столбец и используя "диагональное свойство" таблицы зашифрования для R1, восстановим ее полностью. Результат показан в таблице Р.7.

Таблица Р.7

	Угловые установки
	1	2	3	4	5	6	7	8	9	10
0	0	3	1	8	5	2	9	1	4	7
1	8	1	4	2	9	6	3	0	2	5
2	6	9	2	5	3	0	7	4	1	3
3	4	7	0	3	6	4	1	8	5	2
4	3	5	8	1	4	7	5	2	9	6
5	7	4	6	9	2	5	8	6	3	0
6	1	8	5	7	0	3	6	9	7	4
7	5	2	9	6	8	1	4	7	0	8
8	9	6	3	0	7	9	2	5	8	1
9	2	0	7	4	1	8	0	3	6	9

Из цепочек длины 1 немедленно следует, что (5,7) образуют пару. Цепочки длины 4 можно выровнять восемью способами (записав одну из них в обратном порядке). В действительности нам бы пришлось перебрать каждый из этих способов. Здесь же мы сразу рассмотрим правильное выравнивание, а именно:

1á8á4á6

9á0á2á3

Таблица Р.8

Пара	Угловая установка 1	Пара	Угловая установка 2
(5,7)	(7,5)	(5,7)	(4,2)
(1,9)	(8,2)	(1,0)	(1,3)
(8,0)	(9,0)	(8,2)	(6,9)
(4,2)	(3,6)	(4,3)	(5,7)
(6,3)	(1,4)	(6,9)	(8,0)

Если теперь зашифровать вертикальные и диагональные пары в угловых положениях 1 и 2, то получится таблица Р.8. Два набора из пяти пар, приведенные в правых столбцах для этих двух случаев, оказываются полны противоречий. Поэтому мы отвергаем гипотезу о том, что колесо R1 при зашифровании индикаторов находилось в 1-м угловом положении. Если же теперь зашифровать те же пары в угловых положениях 3 и 4, то получаем таблицу Р.9, и пары, приведенные в ней, полностью согласуются друг с другом. Любая другая комбинация выравниваний цепочек и угловой установки колеса R1 приводит к противоречиям. Поэтому мы заключаем, что колесо R1 в начале процесса шифрования индикаторов на базовых угловых установках находилось в 3-м угловом положении. Если это так, то парами составного отражателя являются (0,5), (1,3), (2,8), (4,7) и (6,9).

Таблица Р.9

Пара	Угловая установка 3	Пара	Угловая установка 4
(5,7)	(6,9)	(5,7)	(9,6)
(1,9)	(4,7)	(1,0)	(2,8)
(8,0)	(3,1)	(8,2)	(0,5)
(4,2)	(8,2)	(4,3)	(1,3)
(6,3)	(5,0)	(6,9)	(7,4)