Уильям Томас Татт OC FRS FRSC ( / t ʌ t / ; 14 мая 1917 - 2 мая 2002) был английским и канадским взломщиком кодов и математиком. Во время Второй мировой войны он сделал блестящий и фундаментальный прогресс в криптоанализе шифра Лоренца , основной шифровальной системы нацистской Германии , которая использовалась для сверхсекретной связи внутри верховного командования Вермахта . Высокоуровневый стратегический характер разведывательной информации, полученной в результате решающего прорыва Тутте, в частности, в массовой расшифровке зашифрованных Лоренцем сообщений, внес большой и, возможно, даже решающий вклад в разгром нацистской Германии. [2] [3] Он также имел ряд значительных математических достижений, в том числе фундаментальные работы в области теории графов и теории матроидов . [4] [5]
Исследования Тутте в области теории графов оказались чрезвычайно важными. В то время, когда теория графов была еще примитивным предметом, Тутте начал изучение матроидов и развил их в теорию, расширив работу, которую Хасслер Уитни впервые разработал примерно в середине 1930-х годов. [6] Несмотря на то, что вклад Тутте в теорию графов оказал влияние на современную теорию графов, и многие из его теорем использовались для дальнейшего развития в этой области, большая часть его терминологии не соответствовала их обычному использованию, и поэтому его терминология сегодня не используется теоретиками графов. [7] «Тутте продвинул теорию графов от предмета с одним текстом ( Д. Кенига ) к ее нынешнему чрезвычайно активному состоянию». [7]
Тутт родился в Ньюмаркете в Саффолке. Он был младшим сыном Уильяма Джона Тутта (1873–1944), садовника поместья, и Энни ( урожденная Ньюэлл; 1881–1956), экономки. Оба родителя работали в конюшнях Fitzroy House, где родился Тутт. [5] Семья провела некоторое время в Бакингемшире, графстве Дарем и Йоркшире, прежде чем вернуться в Ньюмаркет, где Татт посещал начальную школу англиканской церкви Чивли [8] в соседней деревне Чивли. [4] В 1927 году, когда ему было десять лет, Тутте выиграл стипендию для обучения в средней школе для мальчиков Кембриджа и округа . Он занял свое место там в 1928 году.
В 1935 году он выиграл стипендию для изучения естественных наук в Тринити-колледже в Кембридже , где он специализировался на химии и окончил его с отличием в 1938 году. [4] Он продолжил изучать физическую химию в качестве аспиранта, но перевелся на математику в конец 1940 года. [4] Будучи студентом, он (вместе с тремя своими друзьями) стал одним из первых, кто решил задачу о возведении в квадрат квадрата , и первым, кто решил задачу без квадрата подпрямоугольника. Вместе эти четверо создали псевдоним Бланш Декарт , под которым Тутте время от времени публиковался в течение многих лет. [9]
Вскоре после начала Второй мировой войны наставник Тутта, Патрик Дафф, предложил ему работу в военной школе в Государственной школе кодирования и шифрования в Блетчли-Парке (BP). Его опросили и отправили на курс обучения в Лондон, а затем он отправился в Блетчли-Парк, где он поступил на работу в исследовательский отдел. Сначала он работал над шифром Хагелина , который использовался ВМС Италии. Это была коммерчески доступная роторная шифровальная машина, поэтому механика шифрования была известна, а для расшифровки сообщений требовалось только выяснить, как настроена машина. [11]
Летом 1941 года Тутте перевели для работы над проектом под названием «Фиш». По данным разведки, немцы называли системы беспроводной телетайпной передачи «Sägefisch» («рыба-пила»). Это побудило британцев использовать код Fish для немецкой системы шифрования телетайпа. Прозвище Tunny (тунец) использовалось для первой ссылки, не использующей азбуку Морзе, и впоследствии оно использовалось для машин Lorenz SZ и трафика, который они шифровали. [12]
В телеграфии использовался 5-битный Международный телеграфный алфавит № 2 (ITA2). О механизме шифрования ничего не было известно, кроме того, что сообщениям предшествовал 12-буквенный индикатор , что подразумевало 12-колесную роторную шифровальную машину. Поэтому первым шагом должна была стать диагностика машины путем установления логической структуры и, следовательно, функционирования машины. Тутте сыграл ключевую роль в достижении этого, и только незадолго до победы союзников в Европе в 1945 году Блетчли-Парк приобрел шифровальную машину Танни Лоренца. [13] Прорывы Тутте в конечном итоге привели к массовой расшифровке зашифрованных Танни сообщений между немецким верховным командованием (ОКВ) в Берлине и командованием их армий по всей оккупированной Европе и способствовали – возможно, решающему – поражению Германии. [2] [3]
31 августа 1941 года две версии одного и того же сообщения были отправлены с использованием одинаковых ключей, что составляло « глубину ». Это позволило Джону Тилтману , ветерану Блетчли-Парка и чрезвычайно одарённому криптоаналитику, сделать вывод, что это был шифр Вернама , использующий функцию «исключающее ИЛИ» (XOR) (обозначаемую «⊕»), и извлечь два сообщения и, следовательно, получить скрывающий ключ. . После безрезультатного периода, в течение которого криптоаналитики исследовательского отдела пытались выяснить, как работает машина Танни, этот и некоторые другие ключи были переданы Тутте, которого попросили «посмотреть, что вы можете из них сделать». [14]
На курсе обучения Тутте обучили экзаменационной технике Касиски, когда ключ записывают на квадратной бумаге, начиная новую строку после определенного количества символов, которое, как подозревалось, соответствует частоте повторения ключа. [15] Если бы это число было правильным, столбцы матрицы показали бы больше повторений последовательностей символов, чем просто случайность. Тутте знал, что индикаторы Танни использовали 25 букв (исключая J) для 11 позиций и только 23 буквы для остальных. Поэтому он опробовал технику Касиски на первом импульсе ключевых символов, используя повторение 25 × 23 = 575. Он не наблюдал большого количества повторений столбцов за этот период, но наблюдал явление по диагонали. Поэтому он попробовал еще раз с 574, и в столбцах появились повторы. Признав, что простыми делителями этого числа являются 2, 7 и 41, он попробовал еще раз с периодом 41 и «получил прямоугольник из точек и крестиков, изобилующий повторениями». [16]
Однако было ясно, что первый импульс ключа был более сложным, чем тот, который производился одним колесом из 41 ключевого импульса. Тутте назвал этот компонент ключа ( хи 1 ). Он полагал, что существует еще один компонент, который был подвергнут XOR с этим, который не всегда менялся с каждым новым символом, и что это был продукт колеса, которое он назвал ( psi 1 ). То же самое относится и к каждому из пяти импульсов ( и ). Таким образом, для одного символа весь ключ K состоял из двух компонентов:
В Блетчли-парке меточные импульсы обозначались символом x , а пространственные импульсы - символом • . [nb 1] Например, буква «H» будет кодироваться как ••x•x . [17] Вывод Тутте компонентов хи и пси стал возможным благодаря тому факту, что за точками с большей вероятностью следовали точки, а за крестиками с большей вероятностью следовали крестики. Это было результатом слабости немецкой настройки ключей, которую они позже устранили. Как только Тутте совершил этот прорыв, остальная часть исследовательского отдела присоединилась к изучению других импульсов, и было установлено, что все пять колес ци продвигались вперед с каждым новым персонажем и что все пять пси- колесо двигались вместе под контролем двух му или «моторные» колеса. В течение следующих двух месяцев Тутте и другие члены исследовательского отдела разработали полную логическую структуру машины с ее набором колес с кулачками, которые могли находиться в положении (поднятом), добавляющем x к потоку ключевых символов. или в альтернативной позиции, добавленной в • . [18]
Диагностика функционирования машины Танни таким способом была поистине выдающимся криптоаналитическим достижением, которое, в связи с назначением Тутте в кавалеры Ордена Канады , было описано как «один из величайших интеллектуальных подвигов Второй мировой войны». [5]
Для расшифровки сообщения Танни требовалось знание не только логического функционирования машины, но и начальных положений каждого ротора для конкретного сообщения. Велся поиск процесса, который мог бы манипулировать зашифрованным текстом или ключом для создания частотного распределения символов, отклоняющегося от единообразия, которого стремился достичь процесс шифрования. Во время командирования в исследовательский отдел в июле 1942 года Алан Тьюринг обнаружил, что комбинация XOR значений последовательных символов в потоке зашифрованного текста и ключа подчеркивает любые отклонения от равномерного распределения. Результирующий поток (обозначаемый греческой буквой «дельта» Δ ) был назван разностью , поскольку исключающее ИЛИ — это то же самое, что вычитание по модулю 2.
Причина, по которой это открыло путь к Танни, заключалась в том, что, хотя распределение частот символов в зашифрованном тексте нельзя было отличить от случайного потока, то же самое нельзя было сказать и о версии зашифрованного текста, из которой был взят элемент ключа chi . удаленный. Это было так, потому что там, где открытый текст содержал повторяющийся символ и пси- колеса не двигались дальше, разностным пси- символом ( ) был нулевой символ (' / ' в Блетчли-парке). При выполнении операции XOR с любым символом этот символ не имеет никакого эффекта. Повторяющиеся символы в открытом тексте встречались чаще как из-за особенностей немецкого языка (EE, TT, LL и SS относительно распространены) [19] , так и потому, что телеграфисты часто повторяли символы сдвига цифр и букв. [20]
Процитируем Общий отчет о Танни:
Тьюрингери ввел принцип, согласно которому ключ, отличающийся от одного, который теперь называется ΔΚ , может дать информацию, которую невозможно получить с помощью обычного ключа. Этот принцип Δ должен был стать фундаментальной основой почти всех статистических методов разрушения и установки колес. [10]
Тутте воспользовался этим усилением неравномерности разностных значений [nb 2] и к ноябрю 1942 года разработал способ обнаружения начальных точек колеса машины Танни, который стал известен как «Статистический метод». [21] Суть этого метода заключалась в том, чтобы найти начальные настройки компонента хи ключа, перепробовав все позиции его сочетания с зашифрованным текстом и отыскав доказательства неравномерности, отражающие характеристики исходного открытого текста. . [22] Потому что любые повторяющиеся символы в открытом тексте всегда будут генерировать • , и аналогичным образом будут генерировать • всякий раз, когда пси- колеса не двигаются, и примерно в половине случаев, когда они это делают – в целом около 70%.
Помимо применения разности к полным 5-битным символам кода ITA2, Тутте применил ее к отдельным импульсам (битам). [nb 3] Необходимо было установить текущие настройки кулачка колеса ци , чтобы можно было сгенерировать соответствующую последовательность символов колес ци . Было совершенно невозможно сгенерировать 22 миллиона символов из всех пяти колес ци , поэтому изначально было ограничено 41 × 31 = 1271 из первых двух. После объяснения своих выводов Максу Ньюману Ньюману было поручено разработать автоматизированный подход к сравнению зашифрованного текста и ключа для поиска отклонений от случайности. Первую машину назвали Хит Робинсон , но гораздо более быстрый компьютер Colossus , разработанный Томми Флауэрсом и использующий алгоритмы, написанные Туттом и его коллегами, вскоре взял на себя задачу взлома кодов. [23] [24] [25]
В конце 1945 года Тутте возобновил учебу в Кембридже , теперь уже в качестве аспиранта по математике. Он опубликовал несколько работ, начатых ранее: одна из них — теперь известная статья, в которой описывается, какие графы имеют идеальное паросочетание, а другая — в которой строится негамильтонов граф.
Тутт получил докторскую степень по математике в Кембридже в 1948 году под руководством Шона Уайли , который также работал в Блетчли-Парке на острове Танни. Его диссертация «Алгебраическая теория графов» считалась новаторской и касалась темы, позже известной как теория матроидов. [26]
В том же году по приглашению Гарольда Скотта Макдональда Коксетера он принял должность в Университете Торонто . В 1962 году он переехал в Университет Ватерлоо в Ватерлоо , Онтарио, где оставался до конца своей академической карьеры. Он официально вышел на пенсию в 1985 году, но оставался почетным профессором. Тутте сыграл важную роль в создании кафедры комбинаторики и оптимизации в Университете Ватерлоо.
Его математическая карьера была сосредоточена на комбинаторике , особенно теории графов , которую он, как считается, помог создать в ее современной форме, и теории матроидов , в которую он внес глубокий вклад; один коллега описал его как «ведущего математика в области комбинаторики за три десятилетия». Он был главным редактором журнала комбинаторной теории до ухода на пенсию из Ватерлоо в 1985 году. [26] Он также входил в редакционные коллегии нескольких других математических исследовательских журналов.
Работа Тутте в теории графов включает структуру пространств циклов и пространств разрезов , размер максимальных паросочетаний и существование k -факторов в графах, а также гамильтоновы и негамильтоновы графы. [26] Он опроверг гипотезу Тейта о гамильтоновости многогранных графов , используя конструкцию, известную как фрагмент Тутте . В окончательном доказательстве теоремы о четырех цветах использовались его более ранние работы. Полином-граф, который он назвал «дихроматом», стал известным и влиятельным под названием полином Тутте и служит прототипом комбинаторных инвариантов, универсальных для всех инвариантов, удовлетворяющих заданному закону редукции.
Первые крупные достижения в теории матроидов были сделаны Тутте в его Кембриджской докторской диссертации 1948 года, которая легла в основу важной серии статей, опубликованных в течение следующих двух десятилетий. Работы Тутте в области теории графов и теории матроидов оказали глубокое влияние на развитие как содержания, так и направления этих двух областей. [7] В теории матроидов он открыл весьма сложную теорему о гомотопии и основал исследования цепных групп и регулярных матроидов , в отношении которых он доказал глубокие результаты.
Кроме того, Тутте разработал алгоритм определения того, является ли данный бинарный матроид графическим . Алгоритм использует тот факт, что планарный граф — это просто граф, чей матроид схемы, двойственный матройду связи , является графическим. [27]
Тутте написал статью под названием « Как нарисовать граф» , в которой доказал, что любая грань в 3-связном графе заключена в периферийный цикл . Используя этот факт, Тутте разработал альтернативное доказательство, чтобы показать, что каждый граф Куратовского непланарен, показав, что каждый из K 5 и K 3,3 имеет три различных периферийных цикла с общим ребром. Помимо использования периферийных циклов для доказательства непланарности графов Куратовского, Тутте доказал, что каждый простой трехсвязный граф можно нарисовать со всеми выпуклыми гранями, и разработал алгоритм, который строит рисунок плоскости путем решения линейной системы. Полученный рисунок известен как вложение Tutte . Алгоритм Тутте использует барицентрические отображения периферийных цепей простого трехсвязного графа. [28]
Результаты, опубликованные в этой статье, оказались очень важными, поскольку алгоритмы, разработанные Тутте, стали популярными методами рисования планарных графов. Одна из причин популярности встраивания Тутте заключается в том, что необходимые вычисления, которые производятся его алгоритмами, просты и гарантируют взаимно однозначное соответствие графа и его встраивания на евклидову плоскость , что важно при параметризации. трехмерная сетка на плоскости при геометрическом моделировании. «Теорема Тутте является основой для решения других задач компьютерной графики, таких как морфинг ». [29]
Тутте в основном отвечал за разработку теории перечисления плоских графов, которая имеет тесную связь с хроматическими и дихроматическими полиномами. В этой работе использовались некоторые весьма инновационные методы его собственного изобретения, требующие значительной манипулятивной ловкости при работе с степенными рядами (коэффициенты которых учитывают соответствующие виды графиков) и функциями, возникающими как их суммы, а также геометрической ловкостью при извлечении этих степенных рядов из графика. -теоретическая ситуация. [30]
Тутте резюмировал свою работу в Selected Papers of WT Tutte , 1979, и в известной мне теории графов , 1998. [26]
Работа Тутте во время Второй мировой войны, а затем в комбинаторике принесла ему различные должности, почести и награды:
Тутте работал библиотекарем Королевского астрономического общества Канады в 1959–1960 годах, и в его честь был назван астероид 14989 Тутте (1997 UB7). [35]
Из-за работы Татта в Блетчли-Парке Канадское учреждение безопасности связи назвало в его честь в 2011 году внутреннюю организацию, целью которой является продвижение исследований в области криптологии, Институт математики и вычислений Татта (TIMC). [36]
В сентябре 2014 года Тутте отпраздновали в его родном городе Ньюмаркет, Англия, открытием скульптуры после того, как местная газета начала кампанию в честь его памяти. [37]
Блетчли-парк в Милтон-Кинсе отметил работу Тутта выставкой «Билл Татт: математик + взломщик кодов» с мая 2017 по 2019 год, которой 14 мая 2017 года предшествовали лекции о его жизни и работе во время симпозиума, посвященного столетию Билла Татта. [38] [39]
Помимо карьерных преимуществ от работы в новом Университете Ватерлоо , Биллу и его жене Доротее понравилась более сельская обстановка округа Ватерлоо . Они купили дом в соседней деревне Вест-Монтроуз, Онтарио , где любили пешие прогулки, проводили время в саду на берегу Гранд-Ривер и позволяли другим наслаждаться прекрасными пейзажами их собственности.
У них также были обширные знания обо всех птицах в их саду. Доротея, заядлая гончарша, также увлекалась пешими походами, а Билл организовывал походы. Даже ближе к концу своей жизни Билл по-прежнему был заядлым пешеходом. [7] [40] После смерти жены в 1994 году он вернулся в Ньюмаркет (Саффолк), но затем вернулся в Ватерлоо в 2000 году, где умер два года спустя. [41] Он похоронен на объединенном кладбище Вест-Монтроуз. [26]
