William Thomas Tutte OC FRS FRSC ( / t ʌ t / ; 14 мая 1917 – 2 мая 2002) был английским и канадским дешифровальщиком и математиком. Во время Второй мировой войны он сделал блестящий и фундаментальный шаг вперед в криптоанализе шифра Лоренца , основной нацистской немецкой шифровальной системы, которая использовалась для сверхсекретных сообщений в Верховном командовании Вермахта . Высокоуровневый, стратегический характер разведданных, полученных в результате решающего прорыва Тутта, в частности, в массовой расшифровке сообщений, зашифрованных Лоренцом, внес большой, а возможно, даже решающий вклад в разгром нацистской Германии. [2] [3] Он также имел ряд значительных математических достижений, включая фундаментальную работу в области теории графов и теории матроидов . [4] [5]
Исследования Тутта в области теории графов оказались чрезвычайно важными. В то время, когда теория графов была еще примитивным предметом, Тутт начал изучать матроиды и развил их в теорию, расширив работу, которую Хасслер Уитни впервые разработал около середины 1930-х годов. [6] Несмотря на то, что вклад Тутта в теорию графов оказал влияние на современную теорию графов, и многие из его теорем использовались для дальнейшего продвижения вперед в этой области, большая часть его терминологии не согласовывалась с их общепринятым использованием, и поэтому его терминология не используется теоретиками графов сегодня. [7] «Тутт продвинул теорию графов от предмета с одним текстом ( D. Kőnig ) к ее нынешнему чрезвычайно активному состоянию». [7]
Тутт родился в Ньюмаркете в Саффолке. Он был младшим сыном Уильяма Джона Тутта (1873–1944), садовника поместья, и Энни ( урожденной Ньюэлл; 1881–1956), экономки. Оба родителя работали в конюшнях Fitzroy House, где родился Тутт. [5] Семья провела некоторое время в Бакингемшире, графстве Дарем и Йоркшире, прежде чем вернуться в Ньюмаркет, где Тутт посещал начальную школу Cheveley Church of England [8] в соседней деревне Чивли. [4] В 1927 году, когда ему было десять лет, Тутт выиграл стипендию в Кембриджской и окружной средней школе для мальчиков . Он занял там свое место в 1928 году.
В 1935 году он выиграл стипендию на изучение естественных наук в Тринити-колледже в Кембридже , где он специализировался на химии и окончил его с отличием в 1938 году. [4] Он продолжил изучать физическую химию в качестве аспиранта, но перевелся на математику в конце 1940 года. [4] Будучи студентом, он (вместе с тремя своими друзьями) стал одним из первых, кто решил задачу возведения квадрата в квадрат , и первым, кто решил задачу без квадратного подпрямоугольника. Вместе они вчетвером создали псевдоним Бланш Декарт , под которым Тутт время от времени публиковался в течение многих лет. [9]
Вскоре после начала Второй мировой войны наставник Тутте, Патрик Дафф, предложил ему поработать на военные нужды в правительственной школе кодов и шифров в Блетчли-парке (БП). Он был допрошен и отправлен на учебный курс в Лондон, прежде чем отправиться в Блетчли-парк, где он присоединился к Исследовательскому отделу. Сначала он работал над шифром Хагелина , который использовался итальянским флотом. Это была роторная шифровальная машина, которая была доступна в продаже, поэтому механика шифрования была известна, и для расшифровки сообщений требовалось только разобраться, как была настроена машина. [11]
Летом 1941 года Тутте перевели на работу над проектом под названием Fish. Разведывательная информация показала, что немцы называли беспроводные системы телетайпной передачи «Sägefisch» («рыба-пила»). Это привело к тому, что британцы использовали код Fish для немецкой системы шифра телетайпа. Прозвище Tunny (тунец) использовалось для первой не-Морзе-связи, и впоследствии оно использовалось для машин Lorenz SZ и трафика, который они шифровали. [12]
Телеграфия использовала 5-битный Международный телеграфный алфавит № 2 (ITA2). Ничего не было известно о механизме шифрования, кроме того, что сообщениям предшествовал 12-буквенный индикатор , что подразумевало шифровальную машину с 12-колесным ротором. Поэтому первым шагом должна была стать диагностика машины путем установления логической структуры и, следовательно, функционирования машины. Тутт сыграл решающую роль в достижении этого, и только незадолго до победы союзников в Европе в 1945 году в Блетчли-Парке была приобретена шифровальная машина Тунни-Лоренца. [13] Прорывы Тутта в конечном итоге привели к массовой расшифровке сообщений, зашифрованных Тунни, между немецким Верховным командованием (OKW) в Берлине и их армейскими командованиями по всей оккупированной Европе и способствовали — возможно, решающим образом — поражению Германии. [2] [3]
31 августа 1941 года были отправлены две версии одного и того же сообщения с использованием идентичных ключей, что составило « глубину ». Это позволило Джону Тилтману , ветерану Блетчли-парка и необыкновенно одаренному криптоаналитику, сделать вывод, что это был шифр Вернама , который использует функцию «исключающее ИЛИ» (XOR) (обозначенную «⊕»), и извлечь два сообщения и, таким образом, получить скрывающий ключ. После бесплодного периода, в течение которого криптоаналитики Исследовательского отдела пытались выяснить, как работает машина Танни, этот и некоторые другие ключи были переданы Тутте, которого попросили «посмотреть, что можно из этого сделать». [14]
На своем учебном курсе Тутте обучили технике экзамена Касиски , при которой ключ выписывается на клетчатой бумаге, начиная новую строку после определенного количества символов, которое, как предполагалось, является частотой повторения ключа. [15] Если это число было верным, столбцы матрицы покажут больше повторений последовательностей символов, чем просто случайность. Тутте знал, что индикаторы Танни используют 25 букв (исключая J) для 11 позиций, но только 23 буквы для остальных. Поэтому он попробовал технику Касиски на первом импульсе ключевых символов, используя повторение 25 × 23 = 575. Он не наблюдал большого количества повторений столбцов с этим периодом, но он наблюдал явление по диагонали. Поэтому он попробовал еще раз с 574, что показало повторы в столбцах. Осознав, что простыми множителями этого числа являются 2, 7 и 41, он попробовал еще раз с периодом 41 и «получил прямоугольник из точек и крестиков, который был переполнен повторениями» [16] .
Однако было ясно, что первый импульс ключа был сложнее, чем тот, который производился одним колесом из 41 ключевого импульса. Тутте назвал этот компонент ключа ( chi 1 ). Он предположил, что был еще один компонент, который был объединен с этим, и который не всегда менялся с каждым новым символом, и что это был продукт колеса, которое он назвал ( psi 1 ). То же самое применялось к каждому из пяти импульсов ( и ). Таким образом, для одного символа весь ключ K состоял из двух компонентов:
В Блетчли-парке импульсы знаков обозначались как x , а импульсы пространства как • . [nb 1] Например, буква «H» кодировалась как ••x•x . [17] Вывод Туттом компонентов хи и пси стал возможным благодаря тому факту, что за точками с большей вероятностью следовали точки, а за крестами с большей вероятностью следовали кресты. Это было следствием слабости немецкой настройки ключа, которую они позже устранили. После того, как Тутте совершил этот прорыв, остальная часть Исследовательского отдела присоединилась к изучению других импульсов, и было установлено, что все пять колес хи продвигались с каждым новым символом, и что все пять колес пси двигались вместе под управлением двух мю или «моторных» колес. В течение следующих двух месяцев Тутте и другие члены Исследовательского отдела разработали полную логическую структуру машины с ее набором колес, несущих кулачки, которые могли находиться либо в положении (поднятом), которое добавляло x к потоку ключевых символов, либо в альтернативном положении, которое добавляло • . [18]
Диагностика функционирования машины Тунни таким способом была поистине выдающимся криптоаналитическим достижением, которое в почетной грамоте за присвоение Тутту звания офицера Ордена Канады было описано как «один из величайших интеллектуальных подвигов Второй мировой войны» [5] .
Для расшифровки сообщения Tunny требовалось знание не только логического функционирования машины, но и начальных позиций каждого ротора для конкретного сообщения. Велся поиск процесса, который бы манипулировал шифротекстом или ключом, чтобы создать распределение частот символов, которое отклонялось бы от однородности, которую стремился достичь процесс шифрования. Во время командировки в Исследовательский отдел в июле 1942 года Алан Тьюринг выяснил, что комбинация XOR значений последовательных символов в потоке шифротекста и ключа подчеркивает любые отклонения от равномерного распределения. Результирующий поток (символизируемый греческой буквой «дельта» Δ ) был назван разностью , потому что XOR — это то же самое, что и вычитание по модулю 2.
Причина, по которой это дало путь в Tunny, заключалась в том, что хотя распределение частот символов в зашифрованном тексте нельзя было отличить от случайного потока, то же самое не было верно для версии зашифрованного текста, из которой был удален элемент хи ключа. Это было так, потому что, когда открытый текст содержал повторяющийся символ, а пси- колеса не двигались дальше, разностный пси- символ ( ) был бы нулевым символом (' / ' в Блетчли-парке). При выполнении операции XOR с любым символом этот символ не имел никакого эффекта. Повторяющиеся символы в открытом тексте встречались чаще как из-за особенностей немецкого языка (EE, TT, LL и SS относительно распространены), [19] , так и потому, что телеграфисты часто повторяли символы сдвига цифр и букв. [20]
Процитируем Общий отчет о тунце:
Тьюрингери ввел принцип, согласно которому ключевое различие в единице, теперь называемое ΔΚ , может дать информацию, недоступную для обычного ключа. Этот Δ- принцип должен был стать фундаментальной основой почти всех статистических методов ломки и настройки колеса. [10]
Тутт использовал это усиление неоднородности в разностных значениях [nb 2] и к ноябрю 1942 года разработал способ обнаружения начальных точек колес машины Тунни, который стал известен как «Статистический метод». [21] Суть этого метода заключалась в нахождении начальных настроек компонента хи ключа путем исчерпывающего перебора всех позиций его комбинации с зашифрованным текстом и поиска свидетельств неоднородности, которые отражали бы характеристики исходного открытого текста. [22] Поскольку любые повторяющиеся символы в открытом тексте всегда будут генерировать • , и аналогичным образом будут генерировать • всякий раз, когда пси- колеса не будут двигаться дальше, и примерно в половине случаев, когда они будут двигаться – около 70% в целом.
Помимо применения дифференцирования ко всем 5-битным символам кода ITA2, Тутт применил его к отдельным импульсам (битам). [nb 3] Необходимо было установить текущие настройки кулачка хи -колеса, чтобы сгенерировать соответствующую последовательность символов хи -колес. Было совершенно непрактично генерировать 22 миллиона символов из всех пяти хи -колес, поэтому изначально было ограничено 41 × 31 = 1271 из первых двух. После объяснения своих выводов Максу Ньюману , Ньюману было поручено разработать автоматизированный подход к сравнению шифротекста и ключа для поиска отклонений от случайности. Первая машина была названа Хит Робинсон , но гораздо более быстрый компьютер Колосс , разработанный Томми Флауэрсом и использующий алгоритмы, написанные Туттом и его коллегами, вскоре взял на себя взлом кодов. [23] [24] [25]
В конце 1945 года Тутте возобновил учебу в Кембридже , теперь уже в качестве аспиранта по математике. Он опубликовал несколько работ, начатых ранее, одну из ныне известных статей, которая характеризует, какие графы имеют идеальное паросочетание, и другую, которая строит негамильтонов граф.
Тутт получил докторскую степень по математике в Кембридже в 1948 году под руководством Шона Уайли , который также работал в Блетчли-Парке над Tunny. Его диссертация «Алгебраическая теория графов» считалась новаторской и была посвящена предмету, позже известному как теория матроидов. [26]
В том же году, приглашенный Гарольдом Скоттом Макдональдом Коксетером , он принял должность в Университете Торонто . В 1962 году он переехал в Университет Ватерлоо в Ватерлоо , Онтарио, где и оставался до конца своей академической карьеры. Он официально вышел на пенсию в 1985 году, но продолжал работать в качестве почетного профессора. Тутте сыграл важную роль в создании кафедры комбинаторики и оптимизации в Университете Ватерлоо.
Его математическая карьера была сосредоточена на комбинаторике , особенно теории графов , которую он, как считается, помог создать в ее современной форме, и теории матроидов , в которую он внес значительный вклад; один коллега описал его как «ведущего математика в комбинаторике на протяжении трех десятилетий». Он был главным редактором журнала Journal of Combinatorial Theory до ухода на пенсию из Ватерлоо в 1985 году. [26] Он также входил в редколлегии нескольких других математических исследовательских журналов.
Работа Тутта по теории графов включает структуру пространств циклов и пространств разрезов , размер максимальных паросочетаний и существование k -факторов в графах, а также гамильтоновы и негамильтоновы графы. [26] Он опроверг гипотезу Тейта о гамильтоновости полиэдральных графов , используя конструкцию, известную как фрагмент Тутта . Окончательное доказательство теоремы о четырех цветах использовало его более раннюю работу. Графовый полином, который он назвал «дихроматом», стал известным и влиятельным под названием полинома Тутта и служит прототипом комбинаторных инвариантов, которые универсальны для всех инвариантов, удовлетворяющих указанному закону редукции.
Первые крупные достижения в теории матроидов были достигнуты Таттом в его докторской диссертации в Кембридже в 1948 году, которая легла в основу важной серии статей, опубликованных в течение следующих двух десятилетий. Работы Татта в теории графов и теории матроидов оказали глубокое влияние на развитие как содержания, так и направления этих двух областей. [7] В теории матроидов он открыл весьма сложную теорему о гомотопии и основал исследования цепных групп и регулярных матроидов , в отношении которых он доказал глубокие результаты.
Кроме того, Татте разработал алгоритм для определения, является ли заданный бинарный матроид графическим матроидом . Алгоритм использует тот факт, что планарный граф — это просто граф, чей матроид-цепь, двойственный его матроиду-связи , является графическим. [27]
Тутт написал статью под названием « Как нарисовать граф» , в которой доказал, что любая грань в 3-связном графе заключена в периферийный цикл . Используя этот факт, Тутт разработал альтернативное доказательство того, что каждый граф Куратовского непланарен, показав, что K 5 и K 3,3 имеют по три различных периферийных цикла с общим ребром. В дополнение к использованию периферийных циклов для доказательства того, что графы Куратовского непланарны, Тутт доказал, что каждый простой 3-связный граф можно нарисовать так, чтобы все его грани были выпуклыми, и разработал алгоритм, который строит плоский рисунок, решая линейную систему. Полученный рисунок известен как вложение Тутта . Алгоритм Тутта использует барицентрические отображения периферийных контуров простого 3-связного графа. [28]
Результаты, опубликованные в этой статье, оказались очень значимыми, поскольку алгоритмы, разработанные Тутте, стали популярными методами рисования планарных графов. Одна из причин, по которой вложение Тутте популярно, заключается в том, что необходимые вычисления, выполняемые его алгоритмами, просты и гарантируют однозначное соответствие графа и его вложения на евклидовой плоскости , что важно при параметризации трехмерной сетки на плоскости в геометрическом моделировании. «Теорема Тутте является основой для решений других задач компьютерной графики, таких как морфинг ». [29]
Тутт в основном отвечал за разработку теории перечисления планарных графов, которая тесно связана с хроматическими и дихроматическими многочленами. Эта работа включала некоторые весьма инновационные методы его собственного изобретения, требующие значительной манипулятивной ловкости в обращении со степенными рядами (коэффициенты которых подсчитывают соответствующие виды графов) и функциями, возникающими как их суммы, а также геометрической ловкости в извлечении этих степенных рядов из теоретико-графовой ситуации. [30]
Татте обобщил свою работу в « Избранных работах У. Т. Татте» (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] Он похоронен на кладбище West Montrose United Cemetery. [26]
