Нил Стивенсон - Криптономикон [litres]

Разница между вырожденным и невырожденным случаем заключена в свойствах использованных чисел. Комбинация ( n = 20, l = 101) принципиально отличается от комбинации ( n = 20, l = 100). Главная разница в том, что 20 и 101 — «взаимно простые», т. е. у них нет общих делителей. Это означает, что их наименьшее общее кратное, их НОК — большое число и равняется собственно l х n , т. е. 20 х 101 = 2020. А вот НОК ста и двадцати — всего 100. У велосипеда с l = 101 длинный период — он проходит через множество различных состояний, прежде чем вернуться к исходному, а у велосипеда с l = 100 — короткий, всего из нескольких состояний.

Предположим, что велосипед Тьюринга — шифромашина, основанная на алфавитной замене, т. е. заменяет каждую из двадцати шести букв английского алфавита какой-то другой буквой. А открытого текста может стать Т шифртекста, В — F, С — М и так дальше до Z. Сам по себе такой шифр до смешного прост, взломать его — детская забава. Однако предположим, что схема замены меняется от буквы к букве. Первая буква открытого текста шифруется с помощью одного алфавита замены, вторая — с помощью другого, третья — с помощью третьего и так далее. Это называется полиалфавитный шифр.

Предположим, что велосипед Тьюринга генерирует свой алфавит для каждого из состояний. Тогда состоянию ( Q = 0, С = 0) будет соответствовать, например, такой алфавит замены:

а состоянию ( Q = 180, С = 15) — такой:

Никакие две буквы не будут зашифрованы одним и тем же алфавитом замены, пока велосипед не вернется в исходное состояние ( Q = 0, С = 0) и цикл не пойдет с начала. То есть это периодическая полиалфавитная система. Теперь, если период у машины короткий, она часто повторяет саму себя и в качестве шифровальной системы тоже годится исключительно для детской забавы. Чем длиннее период (чем больше взаимно простых чисел в него встроено), тем реже используется один и тот же алфавит замены и тем выше устойчивость шифра.

Трехдисковая «Энигма» — система именно такого типа (то есть периодическая полиалфавитная). Ее барабаны подобно приводу в велосипеде Тьюринга заключают в себе циклы в циклах. Ее период равен 17 576, то есть алфавит замены, которым зашифрована первая буква сообщения, не повторится до 17 577-й буквы. Однако в «Акуле» немцы добавили четвертый барабан, увеличив период до 456 976. В начале каждого сообщения диски ставятся в различные, случайным образом выбранные исходные положения. Поскольку ни в одном немецком сообщении нет 450 000 знаков, «Энигма» никогда не повторяет один и тот же алфавит замены в пределах отдельного сообщения. Вот почему немцы считают ее неуязвимой.

Над головами пролетает звено транспортных самолетов, направляясь, по всей видимости, к аэропорту в Бедфорде. Самолеты издают странно музыкальный диатонический гул, словно волынки, играющие две мелодии разом. Это напоминает Лоуренсу об еще одном феномене, связанном с велосипедным колесом и шифрмашиной «Энигма».

— Ты знаешь, почему самолеты так гудят? — спрашивает он.

— Нет, если задуматься. — Тьюринг снова сдвигает противогаз на лоб. Челюсть у него немного отвисла, глаза смотрят в разные стороны. Уотерхауз его зацепил.

— Я заметил в Перл-Харборе. У самолета — звездообразный двигатель, — говорит Лоуренс. — Соответственно, в нем должно быть нечетное число цилиндров.

— Как одно из другого следует?

— Если число будет четным, цилиндры окажутся один напротив другого, развернутые на сто восемьдесят градусов, а это не работает механически.

— Почему?

— Не помню. Не работает, и все.

Алан поднимает брови. Он явно не убежден.

— Это как-то связано с кривошипами, — защищается Уотерхауз.

— Не уверен, что соглашусь.

— Просто допусти. Считай это граничным условием, — говорит Уотерхауз. Однако Алан уже ушел в свои мысли — наверное, изобретает звездообразный двигатель с четным числом цилиндров.

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

Алан снова садится на велосипед. Некоторое время они едут молча. Собственно, они и до этого не столько разговаривали, сколько подкидывали друг другу идеи и давали время подумать. Это очень производительный способ общения; он устраняет значительную часть избыточности, на которую жаловался Алан в случае Рузвельта и Черчилля.

Уотерхауз думает о вложенных циклах. Он уже решил, что человеческое общество действует по этому самому принципу [27] У него нет никаких определенных фактов на этот счет, просто идейка кажется занятной. , и теперь пытается понять, похоже оно на велосипед Тьюринга (некоторое время работает безотказно, потом внезапно цепь сваливается, отсюда — мировая война), как «Энигма» (долго непонятно скрипит, потом вращающиеся диски выстраиваются, как в игровом автомате, и наступает всеобщее счастье, или, если предпочитаете, Апокалипсис), или просто как самолетный мотор (крутится себе и крутится, ничего особенно не происходит, кроме шума).

— Смотри, сзади! Вон там! — Алан резко тормозит. Это просто шутка, чтобы Лоуренсу пришлось сделать крутой поворот на узкой дороге.

Они прислоняют велосипеды к дереву и снимают с багажников оборудование: сухие батареи, макетные платы, палки, саперный инструмент, мотки провода.

— Я скоро в Америку, работать над проблемой шифрования голоса в лабораториях компании «Белл», — говорит Алан.

Лоуренс невесело смеется.

— Мы с тобой как те корабли у Лонгфелло, которые встретились в ночи, помигали сигнальными огнями и снова разошлись.

— Мы пассажиры на этих кораблях, — поправляет Алан. — Это не случайность. Ты здесь именно потому, что я уезжаю. До сих пор всю работу подразделения 2701 тянул я.

— Теперь это подразделение 2702, — говорит Лоуренс.

Алан расстроен.

— Заметил, значит.

— Очень неосторожно с твоей стороны, Алан.

— Наоборот! — говорит Алан. — Что подумает Руди, если заметит, что во всей армии союзников нет ни одного подразделения, номер которого был бы произведением двух простых чисел?

— Ну, это зависит от того, насколько часто такие числа встречаются и сколько других чисел не использовано, — говорит Лоуренс и начинает решать первую часть задачи. — Опять риманова дзета-функция. Везде она вылезает.

— Вот это по мне! — говорит Алан. — Разумный, деловой подход. Не то что у них.