Уильям Томас Тат (англ. William Thomas Tutte; 14 мая 1917 — 2 мая 2002) — британский, позднее канадский криптограф и математик. Во время Второй Мировой Войны внес значительный вклад в расшифровку шифра Лоренца, главной немецкой шифровальной системы, использовавшейся для секретных коммуникаций главнокомандующими Вермахта. Кроме того, известен своими достижениями в математике.
Начало жизни и образование
Уильям Тат родился 14 мая 1917 года в городе Ньюмаркет в Саффолке, в семье садовника. Получил степень бакалавра по специальности химия в Тринити-колледж (Кембридж). В аспирантуре продолжил изучать физическую химию, но перевелся на математику в конце 1940. В 1941 получил степень Магистра Наук.
Вторая Мировая Война
Вскоре после начала Второй Мировой Войны учитель Тата, Партик Дафф, посоветовал его для работы в Центре правительственной связи в Блетчли Парк. После интервью Уильям был послан на учебные курсы в Лондон, а после присоединился к научно-исследовательской части в Блетчли Парке. Сначала он работал над шифровальной машиной Хагелина, использовавшейся Итальянским военно-морским флотом. Это была роторная шифровальная машина, доступная в промышленных масштабах, так что механизмы кодирования были известны, и дешифрование сообщений требовало только определения настроек машины.
Анализ шифра Лоренца
31 августа 1941 года германским оператором было послано сообщение в 4500 знаков. Сообщение было получено с ошибками, после чего было передано повторно с небольшими изменениями, но тем же самым ключом. Это позволило Джону Тильтману, ветерану Блетчли-парка, сделать вывод о том, что это был шифр Вернама, и получить текст двух сообщений и ключ. После безрезультатных попыток криптоаналитиков взломать код машины Танни, имеющаяся информация была передана Тату для дальнейшей работы. Тат начал расшифровку с использования метода Касиски, заключающегося в поиске групп символов, которые повторяются в зашифрованном тексте. С помощью него он установил, что длина ключевого слова равна сорока одному символу. Эту компоненту ключа Тат назвал χ {\displaystyle \chi } 1 (хи1). Однако, было ясно, что устройство ключа сложнее, то есть существовала и другая компонента, которую он назвал ψ {\displaystyle \psi } 1 (пси1). Таким образом, машина состояла из ψ {\displaystyle \psi } и χ {\displaystyle \chi } дисков, генерирующих каждые пять бит символа. Тат выяснил, что ψ {\displaystyle \psi } и χ {\displaystyle \chi } компоненты ключа объединялись функцией XOR. То есть для каждого символа ключ K можно было представить следующим образом:
После того, как Тат сделал вывод о ψ {\displaystyle \psi } -компоненте, другие исследователи присоединились к изучению структуры машины. В течение следующих двух месяцев Татт и другие члены исследовательской группы Блетчли-парка восстанавливали логическую структуры шифровальной машины.
Карьера
Тат защитил докторскую диссертацию по математике в Кэмбридже в 1948 году под руководством Шона Вайли, также работавшем над Танни в Блетчли Парке. В том же году, будучи приглашенным Гарольдом Коксетером, он получил работу в Университете Торонто. В 1962 он перешел в Университет Ватерлоо в Ватерлоо, Онтарио, где проработал до конца своей академической карьеры. Официально Уильям Тат вышел на пенсию в 1985 году, но продолжал активную деятельность как заслуженный профессор. Он принимал участие в основании Факультета комбинаторики и оптимизации в Университете Ватерлоо. Его математическая карьера была сконцентрирована на комбинаторике, в особенности на теории графов и изучении матроидов. Он являлся главным редактором Журнала теории Комбинаторики и работал в редакционных коллегиях некоторых других математических журналах. В теории графов Тат работал над такими проблемами, как структуры циклов, максимальный размер паросочетаний, факторизация графов, гамильтоновы и негамильтоновы графы. Первые основные достижения в теории матроидов были сделаны Татом в его диссертации в Кэмбридже в 1948 году. Кроме того, Тат активно разрабатывал методы и теоремы построения различных видов графов.
