Уильям Томас Татт ( англ. William Thomas Tutte ; 14 мая 1917 ( 1917-05-14 ) — 2 мая 2002 ) — британский, позднее канадский криптограф и математик .

Во время Второй мировой войны внёс значительный вклад в расшифровку шифра Лоренца , главной немецкой шифровальной системы, использовавшейся для секретных коммуникаций главнокомандующими вермахта . Кроме того, получил ряд важных результатов в теории графов .

Биография

Родился в Ньюмаркете в Саффолке в семье садовника. Степень бакалавра по специальности химия получил в Тринити-колледж (Кембридж) . В аспирантуре продолжил изучать физическую химию, но перевелся на математику в конце 1940. В 1941 получил степень Магистра Наук .

Вскоре после начала Второй мировой войны учитель Татта — Партик Дафф — рекомендовал ученика для работы в Центре правительственной связи в Блетчли-парке . После интервью Татт был послан на учебные курсы в Лондон, а после присоединился к научно-исследовательской части в Блетчли-парке. Вначале работал над шифровальной машиной Хагелина , использовавшейся Итальянским военно-морским флотом. Это была роторная шифровальная машина, доступная в промышленных масштабах, так что механизмы кодирования были известны, и дешифрование сообщений требовало только определения настроек машины . Наиболее известная работа в Блетчли-парке — анализ шифра Лоренца .

В 1948 году в Кембридже защитил докторскую диссертацию под руководством Шона Вайли, также работавшем над Танни в Блетчли-парке. В том же году, будучи приглашённым Гарольдом Коксетером , получил работу в Университете Торонто и переехал в Канаду. В 1962 году перешёл в Университет Уотерлу ( Онтарио ), поселился в с женой предместье . В Уотерлу проработал до конца академической карьеры в 1985 году, но и после этого продолжал активную деятельность в ранге заслуженного профессора, принимал участие в основании факультета комбинаторики и оптимизации в Университете Уотерлу.

После смерти жены в 1994 году вернулся жить в родной Ньюмаркет, но после опять вернулся в Уотерлу в 2000 году, где умер два года спустя , похоронен на кладбище Уэст-Монтроуза .

Анализ шифра Лоренца

31 августа 1941 года германским оператором было послано сообщение в 4500 знаков. Сообщение было получено с ошибками, после чего было передано повторно с небольшими изменениями, но тем же самым ключом. Это позволило Джону Тильтману, ветерану Блетчли-парка, сделать вывод о том, что это был шифр Вернама , и получить текст двух сообщений и ключ. После безрезультатных попыток криптоаналитиков взломать код машины Танни , имеющаяся информация была передана Татту для дальнейшей работы . Начал расшифровку с использования метода Касиски , заключающегося в поиске групп символов, которые повторяются в зашифрованном тексте. С помощью него он установил, что длина ключевого слова равна сорока одному символу . Эту компоненту ключа Татт назвал ${\displaystyle \chi }$ ₁ ( хи ₁ ). Однако, было ясно, что устройство ключа сложнее, то есть существовала и другая компонента, которую он назвал ${\displaystyle \psi }$ ₁ ( пси ₁ ). Таким образом, машина состояла из ${\displaystyle \psi }$ и ${\displaystyle \chi }$ дисков, генерирующих каждые пять бит символа. Татт выяснил, что ${\displaystyle \psi }$ и ${\displaystyle \chi }$ компоненты ключа объединялись функцией XOR . То есть для каждого символа ключ K можно было представить следующим образом:

K = ${\displaystyle \chi }$ ⊕ ${\displaystyle \psi }$

После того, как Татт сделал вывод о ${\displaystyle \psi }$ -компоненте, другие исследователи присоединились к изучению структуры машины. В течение следующих двух месяцев Татт и другие члены исследовательской группы Блетчли-парка восстанавливали логическую структуры шифровальной машины .

Математическая карьера

Ранние математические труды, выполненные совместно с сокурсниками по Тринити-колледжу, опубликованы под коллективным псевдонимом Бланш Декарт .

Наиболее значительные результаты получил в комбинаторике , теории графов (структуры циклов , максимальный размер паросочетаний , факторизация графов , гамильтоновы и негамильтоновы графы, задачи построения) и теории матроидов (работы в Кембридже 1948 года).

Являлся главным редактором Journal of Combinatorial Theory, работал в редакционных коллегиях ряда математических журналов.

Признание и память

Среди наград и почётных званий, полученных за работы в течение Второй мировой войны и его последующие математические труды:

• 1958 — член Королевского общества Канады ;
• 1971 — премия Джефри — Уильямса Канадского математического общества;
• 1975 — медаль Генри Маршалла Тори королевского общества Канады;
• 1987 — член Лондонского королевского общества ;
• 1998 — назначенный почётный директор ;
• 2001 — офицер ордена Канады ;
• 2001 — CRM-Fields-PIMS prize .

Также работал библиотекарем в Королевском астрономическом обществе Канады в 1959—1960 годах, и в его честь был назван астероид .

В 2011 году в благодарность за работу Татта в Блетчли-парке Центр безопасности коммуникаций Канады назвал в его честь Институт математики и вычислений .

В сентябре 2014 в Ньюмаркете — родном городе Татта — была поставлена скульптура в его честь.

Книги

• Tutte, W. T. (1966), Connectivity in graphs , Mathematical expositions, vol. 15, Toronto, Ontario: University of Toronto Press, Zbl
• Tutte, W. T. (1966), Introduction to the theory of matroids , Santa Monica, Calif.: RAND Corporation report R-446-PR . Also Tutte, W. T. (1971), Introduction to the theory of matroids , Modern analytic and computational methods in science and mathematics, vol. 37, N. Y. : American Elsevier Publishing Company, ISBN 978-0-444-00096-5 , Zbl
• Tutte, W. T., ed. (1969), Recent progress in combinatorics. Proceedings of the third Waterloo conference on combinatorics, May 1968 , N. Y. - L. : Academic Press, pp. xiv+347, ISBN 978-0-12-705150-5 , Zbl
• Tutte, W. T. (1979), McCarthy, D.; Stanton, R. G. (eds.), Selected papers of W.T. Tutte, Vols. I, II. , Winnipeg, Manitoba: , St. Pierre, Manitoba, Canada, pp. xxi+879, Zbl
  • Volume I: ISBN 978-0-9690778-1-7
  • Volume II: ISBN 978-0-9690778-2-4
• Tutte, W. T. (1984), Graph theory , Encyclopedia of mathematics and its applications, vol. 21, Menlo Park, California: Addison-Wesley Publishing Company, ISBN 978-0-201-13520-6 , Zbl Reprinted by Cambridge University Press 2001, ISBN 978-0-521-79489-3
  • У. Татт. Теория графов. — М. : Мир, 1988.
• Tutte, W. T. (1998), Graph theory as I have known it , Oxford lecture series in mathematics and its applications, vol. 11, Oxf. : Clarendon Press, ISBN 978-0-19-850251-7 , Zbl Reprinted 2012, ISBN 978-0-19-966055-1

Примечания

Литература

• Jack Copeland. Colossus : The Secrets of Bletchley Park's Codebreaking Computers. — Oxf. : Oxford University Press , 2006. — 287 с. — ISBN 978-0-19-284055-4 .
• Ralph Eskrine, Michael Smith. The Bletchley Park Codebreakers. — Biteback Publishing Ltd, 2011. — ISBN 978-1-84954-078-0 .
• . . — Scarecrow Press, 2010. — ISBN 9780810873773 .
• J. O'Connor, E.F. Robertson. . — University of St Andrews, 2003.
• Mark Ward. // BBC News .