Войти
Уильям Томас Татт OC FRS FRSC (; 14 мая 1917 - 2 мая 2002) был канадским взломщиком кодов британского происхождения и математиком. Во время Второй мировой войны он совершил блестящий и фундаментальный прогресс в криптоанализе шифра Лоренца, главной нацистской немецкой системы, которая использовалась для топ-шифрования. секретные коммуникации внутри вермахта верховного командования. Высокоуровневый, стратегический характер разведданных, полученных в результате решающего прорыва Тутте, в частности, в массовом расшифровке зашифрованных Лоренцем сообщений, внес большой, а возможно, даже решающий вклад в поражение нацистской Германии. У него также был ряд значительных математических достижений, в том числе фундаментальная работа в областях теории графов и теории матроидов.
Исследования Тутте в области теории графов оказались чрезвычайно важными. В то время, когда теория графов была еще примитивным предметом, Тутте начал изучение матроидов и развил их в теорию, расширив работу, которую Хасслер Уитни впервые разработал примерно в середине 1930-е годы. Несмотря на то, что вклад Тутте в теорию графов оказал влияние на современную теорию графов, и многие из его теорем использовались для дальнейшего продвижения в этой области, большая часть его терминологии не соответствовала их традиционному использованию, и поэтому его терминология не используется в теоретики графов сегодня. «Тутте продвинул теорию графов от предмета с одним текстом (Д. Кёнига ) к его нынешнему чрезвычайно активному состоянию».
Тутте родился в Ньюмаркете в Саффолке. Он был младшим сыном Уильяма Джона Татта (1873–1944), садовника поместья, и Энни (урожденная Ньюэлл; 1881–1956), домработницы. Оба родителя работали в конюшнях Fitzroy House, где родился Тутте. Семья провела некоторое время в Бакингемшире, графстве Дарем и Йоркшире, прежде чем вернуться в Ньюмаркет, где Татт посещал начальную школу англиканской церкви Чивли в соседней деревне Чивли. В 1927 году, когда ему было десять лет, Тутте получил стипендию для обучения в средней школе для мальчиков Кембриджа и округа. Он занял свое место там в 1928 году.
В 1935 году он получил стипендию для изучения естественных наук в Тринити-колледже в Кембридже, где он специализировался на химии и получил высшее образование. с отличием в 1938 году. Он продолжал изучать физическую химию в аспирантуре, но перешел в математику в конце 1940 года. Будучи студентом, он (вместе с тремя своими друзьями) стал одним из первая решила задачу возведения квадрата в квадрат и первая решила задачу без квадрата подпрямоугольника. Вместе эти четверо создали псевдоним Бланш Декарт, под которым Тутте время от времени публиковались в течение многих лет.
Машины Lorenz SZ имели по 12 колес на каждой. другое количество кулачков (или «штифтов»). | Номер колеса | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Название колеса BP |  1 | 2 | 3 | 4 | 5 |  37 | 61 |  1 | 2 | 3 | 4 | 5 |
| Количество кулачков (штифтов) | 43 | 47 | 51 | 53 | 59 | 37 | 61 | 41 | 31 | 29 | 26 | 23 |
Вскоре после начала Второй мировой войны наставник Тутте, Патрик Дафф, предложил ему военную работу в Правительственном кодексе и Школа Сайфера в Блетчли-Парк (БП). Он был проинтервьюирован и отправлен на учебный курс в Лондоне, прежде чем отправиться в Блетчли-парк, где он присоединился к исследовательскому отделу. Сначала он работал над шифром Хагелина, который использовался итальянским флотом. Это была машина с роторным шифрованием , которая была коммерчески доступной, поэтому механика шифрования была известна, и для расшифровки сообщений требовалось только выяснить, как эта машина была настроена.
Летом 1941 года Тутте перевели работать над проектом под названием Fish. Согласно разведывательной информации, немцы называли беспроводные системы передачи телетайпов "Sägefisch" (рыба-пила). Это привело к тому, что британцы использовали код Fish для немецкой системы шифрования телетайпа. Прозвище Tunny (tunafish) использовалось для первого канала, отличного от Морзе, и впоследствии оно использовалось для машин Lorenz SZ и трафика, который они зашифровали.
Telegraphy использовала 5-bit Международный телеграфный алфавит № 2 (ITA2). Ничего не было известно о механизме шифрования, кроме того, что сообщениям предшествовал 12-буквенный индикатор, который подразумевал шифровальную машину с ротором с 12 колесами. Поэтому первым шагом должна была быть диагностика машины путем установления логической структуры и, следовательно, функционирования машины. Тутт сыграл ключевую роль в достижении этого, и только незадолго до победы союзников в Европе в 1945 году Блетчли-Парк приобрел машину с шифром Тунни Лоренца. Прорывы Тутте привели в конечном итоге к массовому расшифровке зашифрованных Тунни сообщений между немецким верховным командованием (OKW) в Берлине и их армейскими командованиями по всей оккупированной Европе и способствовали - возможно, в решающей степени - поражению Германии
.31 августа 1941 года были отправлены две версии одного и того же сообщения с использованием идентичных ключей, которые составляли «глубину ». Это позволило Джону Тилтману, ветерану Блетчли-Парка и замечательно одаренному криптоаналитику, сделать вывод, что это был шифр Вернама, который использует функцию Исключающее ИЛИ (XOR) (обозначено символами на "⊕"), и чтобы извлечь два сообщения и, следовательно, получить скрывающий ключ. После бесплодного периода, в течение которого криптоаналитики из Исследовательского отдела пытались выяснить, как работает машина Тунни, этот и некоторые другие ключи были переданы Тутте, которого попросили «посмотреть, что вы можете с ними сделать».
Машина Lorenz SZ42 со снятыми крышками. Блетчли-Парк музей На учебном курсе Тутте был обучен экзамену Касиски техника написания ключа на квадратной бумаге, начиная новую строку после определенного количества знаков это подозревалось в частоте повторения ключа. Если бы это число было правильным, столбцы матрицы показывали бы больше повторений последовательностей символов, чем только случайности. Тутте было известно, что индикаторы Тунни использовали 25 букв (исключая J) для 11 позиций и только 23 буквы для остальных. Поэтому он попробовал технику Касиски на первом импульсе ключевых персонажей, используя повторение 25 × 23 = 575. Он не наблюдал большого количества повторений столбца с этим периодом, но он наблюдал явление по диагонали. Поэтому он попытался снова с 574, который обнаружил повторы в столбцах. Признавая, что простые множители этого числа равны 2, 7 и 41, он попробовал еще раз с периодом 41 и «получил прямоугольник из точек и крестиков, изобилующий повторениями».
Однако было ясно, что первый импульс ключа был более сложным, чем импульс, произведенный одним колесом из 41 импульса ключа. Тутте назвал этот компонент ключа
⊕ В Блетчли-парке отметьте импульсы были обозначены x, а космические импульсы - • . Например, буква «H» будет закодирована как •• x • x . Выведение Тутте компонентов ци и пси стало возможным благодаря тому факту, что за точками с большей вероятностью, чем без точек, следовали точки, а за крестиками с большей вероятностью, чем без них. Это было продуктом слабости немецкой ключевой системы, которую они позже устранили. Как только Тутте совершил этот прорыв, остальная часть Исследовательского отдела присоединилась к изучению других импульсов, и было установлено, что все пять колес ци продвигались с каждым новым персонажем и что все пять колес пси перемещались вместе под контролем двух му или "моторные" колеса. В течение следующих двух месяцев Тутте и другие члены Исследовательского отдела разработали полную логическую структуру машины с ее набором кулачков подшипников колес, которые могли находиться в положении (поднятом), увеличивающем x к потоку ключевых персонажей, или в альтернативной позиции, добавленной в •.
. Диагностика функционирования машины Тунни таким образом была поистине замечательным криптоаналитическим достижением, которое в цитате за введение Тутте в должность офицера Орден Канады был описан как «один из величайших интеллектуальных достижений Второй мировой войны».
Для расшифровки сообщения Тунни требовалось знание не только логики. функционирование машины, а также начальные позиции каждого ротора для конкретного сообщения. Был начат поиск процесса, который мог бы манипулировать шифротекстом или ключом для получения частотного распределения символов, которое отклонялось бы от единообразия, на которое стремился процесс шифрования. Во время прикомандирования к исследовательскому отделу в июле 1942 г. Алан Тьюринг выяснил, что комбинация XOR значений последовательных символов в потоке зашифрованного текста и ключа подчеркивает любые отклонения от единообразного распределения. Результирующий поток (обозначенный греческой буквой «дельта» Δ ) был назван разницей, потому что XOR совпадает с вычитанием по модулю 2.
Причина, по которой это открыло путь в Tunny, заключалась в том, что, хотя частотное распределение символов в зашифрованном тексте нельзя было отличить от случайного потока, то же самое не было верно для версии зашифрованного текста, из которой chi элемент ключа был удален. Это было так, потому что там, где открытый текст содержал повторяющийся символ, а пси-колеса не двигались дальше, символ разницы пси (Δ
Процитируем Общий отчет о Тунни:
Тьюрингери ввел принцип, согласно которому разница ключей в единице, теперь называемая ΔΚ, может давать информацию, недоступную для обычного ключа. Этот принцип Δ должен был стать фундаментальной основой почти всех статистических методов поломки и настройки колес.
Тутте использовал это усиление неоднородности в разностных значениях и к ноябрю 1942 года создал способ обнаружения начальных точек колеса машины Тунни, которая стала известна как «Статистический метод». Суть этого метода заключалась в том, чтобы найти начальные настройки компонента ци ключа путем исчерпывающего перебора всех позиций его комбинации с зашифрованным текстом и поиска свидетельств неоднородности, отражающих характеристики исходного открытого текста. Поскольку любые повторяющиеся символы в открытом тексте всегда будут генерировать •, и аналогично ∆
Помимо применения дифференцирования к полным 5-битным символам кода ITA2, Тутте применил его к отдельным импульсам (битам). Необходимо было установить текущие настройки кулачка колеса ци, чтобы можно было сгенерировать соответствующую последовательность символов колес ци. Было совершенно невозможно сгенерировать 22 миллиона символов из всех пяти колес чи, поэтому изначально было ограничено 41 × 31 = 1271 из первых двух. После объяснения своих выводов Максу Ньюману, Ньюман получил задание разработать автоматизированный подход к сравнению зашифрованного текста и ключа для поиска отклонений от случайности. Первая машина была названа Хит Робинсон, но гораздо более быстрый компьютер Colossus, разработанный Томми Флауэрс и использующий алгоритмы, написанные Тутте и его коллегами, вскоре взял верх. для взлома кодов.
Тютт получил докторскую степень по математике в Кембридже в 1948 году под руководством Шона Уайли, который имел также работал в Блетчли-парке на Тунни. В конце 1945 года Тутте возобновил учебу в Кембридже, теперь уже будучи аспирантом по математике. Он опубликовал некоторую работу, начатую ранее: одну - теперь уже известную, в которой описывается, какие графы имеют идеальное соответствие, а другую - строит негамильтонов граф. Он продолжил работу над новаторской докторской диссертацией «Алгебраическая теория графов» по предмету, позже известному как теория матроидов.
В том же году по приглашению Гарольда Скотта Макдональда Кокстера, он принял должность в Университете Торонто. В 1962 году он перешел в Университет Ватерлоо в Ватерлоо, Онтарио, где оставался до конца своей академической карьеры. Официально он вышел на пенсию в 1985 году, но оставался почетным профессором. Тутте сыграл важную роль в создании кафедры комбинаторики и оптимизации в Университете Ватерлоо.
Его математическая карьера была сосредоточена на комбинаторике, особенно теории графов, которую он, как считается, помогал создать в ее современной форме, и теории матроидов, в которую он внес большой вклад; один коллега описал его как «ведущего математика в области комбинаторики за три десятилетия». Он был главным редактором Journal of Combinatorial Theory до выхода на пенсию из Ватерлоо в 1985 году. Он также работал в редакционных советах нескольких других математических исследовательских журналов.
Работа Тутте по теории графов включает структуру циклов и разрезов, размером максимальное совпадение и наличие k-факторов в графах, а также гамильтоновых и негамильтоновых графов. Он опроверг гипотезу Тейта о гамильтоничности многогранных графов, используя конструкцию, известную как фрагмент Тутте. В конечном доказательстве теоремы о четырех цветах использовались его более ранние работы. Графовый полином, который он назвал «дихроматом», стал известным и влиятельным под названием полином Тутте и служит прототипом комбинаторных инвариантов, универсальных для всех инвариантов, удовлетворяющих заданному закону редукции.
Первые крупные успехи в теории матроидов были сделаны Тутте в его Кембриджской докторской диссертации 1948 года, которая легла в основу важной серии статей, опубликованных в течение следующих двух десятилетий. Работа Тутте по теории графов и теории матроидов оказала глубокое влияние на развитие как содержания, так и направления этих двух областей. В теории матроидов он открыл очень сложную теорему о гомотопии и основал исследования цепных групп и регулярных матроидов, в которых он доказал глубокие результаты.
Вдобавок Тутте разработал алгоритм для определения того, является ли данный двоичный матроид графическим матроидом . Алгоритм использует тот факт, что планарный граф - это просто граф, матроид схемы которого, двойник его связующего-матроида, является графическим.
Тутте написал статью под названием How to Нарисуйте График, на котором он доказал, что любая грань в 3-связном графе заключена в периферийный цикл. Используя этот факт, Тутте разработал альтернативное доказательство, чтобы показать, что каждый граф Куратовского не является плоским, показав, что K 5 и K 3,3 каждый имеет три различных периферийных цикла с общим край. В дополнение к использованию периферийных циклов для доказательства того, что графы Куратовского не являются планарными, Тутте доказал, что любой простой трехсвязный граф может быть нарисован со всеми его выпуклыми гранями, и разработал алгоритм, который строит чертеж плоскости, решая линейную систему. Полученный рисунок известен как вложение Тутте. Алгоритм Тутте использует барицентрические отображения периферийных схем простого 3-связного графа.
Результаты, опубликованные в этой статье, оказались очень важными, потому что алгоритмы, которые стали популярными методы рисования плоских графиков. Одна из причин популярности вложения Тутте состоит в том, что необходимые вычисления, выполняемые его алгоритмами, просты и гарантируют взаимно однозначное соответствие графа и его вложения в евклидову плоскость, что важно при параметризации трехмерной сетки на плоскости в геометрическом моделировании. «Теорема Тутте является основой для решений других задач компьютерной графики, таких как морфинг."
Тутте в основном отвечал за разработку теории перечисления плоских графов, которая имеет тесные связи с хроматическими и дихроматические многочлены.Эта работа включала в себя несколько весьма инновационных методов его собственного изобретения, требующих значительной манипулятивной ловкости при работе с степенными рядами (коэффициенты которых учитывают соответствующие виды графиков) и функциями, возникающими как их суммы, а также геометрической ловкости при извлечении этих степенных рядов. из теоретико-графовой ситуации.
Тутте резюмировал свою работу в Избранных статьях У. Т. Тутта, 1979 г., и в теории графов, как я ее знал, 1998 г.
Работа Тутте во время Второй мировой войны, а затем и в области комбинаторики принесла ему различные должности, награды и награды:
Тутт работал библиотекарем в Королевское астрономическое общество Канады в 1959–1960 гг., А астероид 14989 Tutte (1997 UB7) был назван его именем.
Из-за работы Тутте в Блетчли-Парке Управление безопасности связи в Канаде назвало Институт математики и вычислений (TIMC) внутренней организацией, нацеленной на продвижение исследований в области криптологии. в 2011 году.
В сентябре 2014 года Тутте чествовали в своем родном городе Ньюмаркет, Англия, открытием скульптуры после того, как местная газета начала кампанию в его память.
В Блетчли-парке в Милтон-Кейнсе работа Тутта была отмечена выставкой «Билл Татт: математик + взломщик кодов» с мая 2017 года по 2019 год, которой предшествовали лекции о его жизни и работе 14 мая 2017 года во время симпозиума, посвященного столетию Билла Татта.
Помимо карьерных преимуществ работы в новом Университете Ватерлоо, более сельская местность округа Ватерлоо понравилась Биллу и его жене Доротее. Они купили дом в соседней деревне Уэст-Монтроуз, Онтарио, где им нравилось ходить в походы, проводить время в своем саду на Гранд-Ривер и позволять другим наслаждаться красивыми пейзажами своей собственности.
Они также хорошо знали всех птиц в своем саду. Доротея, заядлая гончар, также была заядлым путешественником, и Билл организовывал походы. Даже ближе к концу своей жизни Билл все еще был заядлым путешественником. После того, как его жена умерла в 1994 году, он вернулся в Ньюмаркет (Суффолк), но затем вернулся в Ватерлоо в 2000 году, где и умер два года спустя. Он похоронен на кладбище West Montrose United.
