Татт, Уильям Томас

В Википедии есть статьи о других людях с такой фамилией, см. Татт; Татт, Уильям.

Уильям Томас Татт
англ. William Thomas Tutte
Дата рождения	14 мая 1917(1917-05-14)[1]
Место рождения	Ньюмаркет, Западный Суффолк^[вд], Суффолк, Англия, Великобритания
Дата смерти	2 мая 2002(2002-05-02)[1] (84 года)
Место смерти	Уотерлу, Уотерлу^[вд], Онтарио, Канада[1]
Страна	Великобритания  Канада[2]
Род деятельности	математик, преподаватель университета, криптолог
Научная сфера	комбинаторика[3], теория графов[3], криптография[3] и Фиш^[вд]
Место работы	Университет Торонто[1] Университет Уотерлу[1] Блетчли-парк[1]
Альма-матер	Тринити-колледж Кембриджского университета (1939)[1] Кембриджский университет (1948)[4][1] Cambridgeshire High School for Boys^[вд] (1935)[1]
Научный руководитель	Шон Вайли^[вд]
Известен как	криптоаналитик шифра Лоренца
Награды и премии	Член Королевского общества Канады; Член Лондонского королевского общества

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

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

Биография

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Книги

• Tutte, W. T. (1966), Connectivity in graphs, Mathematical expositions, vol. 15, Toronto, Ontario: University of Toronto Press, Zbl 0146.45603
• 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 0231.05027
• 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 0192.33101
• Tutte, W. T. (1979), McCarthy, D.; Stanton, R. G. (eds.), Selected papers of W.T. Tutte, Vols. I, II., Winnipeg, Manitoba: Charles Babbage Research Centre, St. Pierre, Manitoba, Canada, pp. xxi+879, Zbl 0403.05028
  • 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 0554.05001 Reprinted by Cambridge University Press 2001, ISBN 978-0-521-79489-3
  • У. Татт. Теория графов. — М.: Мир, 1988.[14]
• 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 0915.05041 Reprinted 2012, ISBN 978-0-19-966055-1

Примечания

1. Архив по истории математики Мактьютор — 1994.
2. Polymer International (англ.) — Wiley-Blackwell. — ISSN 0959-8103; 1097-0126 — doi:10.1002/(ISSN)1097-0126
3. Tutte, W. T. // Чешская национальная авторитетная база данных
4. Mathematics Genealogy Project (англ.) — 1997.
5. O'Connor, 2003, с. 1.
6. Copeland, 2006, с. 352—353.
7. Dan van der Vat. Obituary: William Tutte Архивная копия от 29 ноября 2012 на Wayback Machine. // The Guardian. — 2002.
8. West Montrose United Cemetery  (неопр.). Дата обращения: 9 декабря 2015. Архивировано 1 февраля 2017 года.
9. Copeland, 2006, с. 356—357.
10. Smith, 2011.
11. Arthur M. Hobbs and James G. Oxley. William T. Tutte (1917—2002) Архивная копия от 12 марта 2017 на Wayback Machine. // Notices of the American Mathematical Society. — 2004. — №. 5.
12. Barbara Elve. Tutte honoured by cryptographic centre Архивная копия от 4 марта 2016 на Wayback Machine
13. Colin Freeze. Top secret institute comes out of the shadows to recruit top talent Архивная копия от 4 марта 2016 на Wayback Machine. // Globe and Mail. — 2011.
14. Теория графов — У. Татт — Google Libri

Литература

• 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.
• West N.^[англ.]. Historical Dictionary of Naval Intelligence. — Scarecrow Press, 2010. — ISBN 9780810873773.
• J. O'Connor, E.F. Robertson. MacTutor Biography: William Thomas Tutte. — University of St Andrews, 2003.
• Mark Ward. Code-cracking machine returned to life // BBC News.