Tutt, William Thomas

William Thomas Tutt
Angličtina  William Thomas Tutte
Datum narození	14. května 1917( 14.05.1917 ) [1]
Místo narození	Newmarket , West Suffolk [d] , Suffolk , Anglie , Velká Británie
Datum úmrtí	2. května 2002( 2002-05-02 ) [1] (ve věku 84 let)
Místo smrti	Ontario , Kanada
Země	Velká Británie  Kanada [2]
Vědecká sféra	kombinatorika a teorie grafů
Místo výkonu práce	University of Toronto University of Waterloo
Alma mater	Trinity College, University of Cambridge University of Cambridge [3] Cambridgeshire střední škola pro chlapce [d]
vědecký poradce	Sean Wylie [d]
Studenti	Stephan Foldes [d] [3]
Známý jako	Šifrovací analytik Lorenz
Ocenění a ceny	člen Královské společnosti Kanady ; Člen Královské společnosti v Londýně

William Thomas Tutte ( narozený  William Thomas Tutte ; 14. května 1917  – 2. května 2002 ) byl britský, později kanadský kryptograf a matematik .

Během druhé světové války významně přispěl k rozluštění Lorentzovy šifry , hlavního německého šifrovacího systému používaného pro tajnou komunikaci vrchními veliteli Wehrmachtu . Kromě toho získal řadu důležitých výsledků v teorii grafů [4] .

Životopis

Narozený v Newmarketu , Suffolk , syn zahradníka. Bakalářský titul v oboru chemie získal na Trinity College (Cambridge) . Na postgraduální škole pokračoval ve studiu fyzikální chemie, ale na konci roku 1940 přešel na matematiku. V roce 1941 získal titul Master of Science [4] .

Krátce po vypuknutí druhé světové války doporučil Tuttův učitel Partick Duff studenta pro práci ve vládním komunikačním centru v Bletchley Parku . Po rozhovoru byl Tutt poslán na výcvikový kurz do Londýna a poté se připojil k výzkumné jednotce v Bletchley Park. Zpočátku pracoval na šifrovacím stroji Hagelin , používaném italským námořnictvem. Jednalo se o komerčně dostupný rotační šifrovací stroj, takže šifrovací mechanismy byly známé a dešifrování zpráv vyžadovalo pouze určení nastavení stroje [5] . Nejznámějším dílem v Bletchley Parku je rozbor Lorenzovy šifry .

V roce 1948 obhájil doktorskou disertační práci v Cambridge pod vedením Seana Wylie, který také pracoval na Tunney v Bletchley Park. Ve stejném roce, na pozvání Harolda Coxetera , získal práci na University of Toronto a přestěhoval se do Kanady. V roce 1962 se přestěhoval na University of Waterloo ( Ontario ), se svou ženou se usadil na předměstí West Montrose . Ve Waterloo působil až do konce své akademické kariéry v roce 1985, ale i poté nadále působil v hodnosti emeritního profesora, podílel se na založení fakulty kombinatoriky a optimalizace na University of Waterloo.

Po smrti své manželky v roce 1994 se vrátil žít do svého rodného Newmarketu, ale poté se v roce 2000 znovu vrátil do Waterloo, kde o dva roky později zemřel [6] a byl pohřben na hřbitově West Montrose [7] .

Analýza Lorenzovy šifry

31. srpna 1941 byla německým operátorem odeslána zpráva o délce 4500 znaků. Zpráva byla přijata s chybami, poté byla znovu odeslána s drobnými změnami, ale se stejným klíčem. To umožnilo Johnu Tiltmanovi, veteránovi z Bletchley Parku, odvodit, že jde o Vernamovu šifru , a získat text dvou zpráv a klíč. Po neúspěšných pokusech kryptoanalytiků prolomit kód Tunneyho stroje byly dostupné informace předány Tuttovi k další práci [5] . Zahájeno dešifrování pomocí metody Kasiska , která spočívá v hledání skupin znaků, které se v šifrovém textu opakují. S ním zjistil, že délka klíčového slova je čtyřicet jedna znaků [8] . Tutt nazval tuto složku klíče 1 ( chi 1 ). Bylo však jasné, že struktura klíče je složitější, to znamená, že tam byla další složka, kterou nazval 1 ( psi 1 ). Stroj se tedy skládal z disků generujících každých pět bitů znaku. Tutt zjistil, že komponenty klíče byly kombinovány s funkcí XOR . To znamená, že pro každý znak může být klíč K reprezentován následovně:

Poté, co Tutt učinil závěr o -komponentě, se další výzkumníci připojili ke studiu struktury stroje. Během následujících dvou měsíců Tutt a další členové výzkumného týmu Bletchley Park přestavěli logickou strukturu šifrovacího stroje [9] .

Matematická kariéra

Raná matematická práce, provedená společně se spolužáky na Trinity College, publikovaná pod kolektivním pseudonymem Blanche Descartes .

Nejvýznamnější výsledky získal v kombinatorice , teorii grafů ( cyklové struktury , maximální velikost párování , faktorizace grafů , hamiltonovské a nehamiltonovské grafy, konstrukční problémy) [10] a teorii matroidů (práce v Cambridge 1948).

Byl šéfredaktorem Journal of Combinatorial Theory a působil v redakčních radách řady matematických časopisů.

Rozpoznávání a paměť

Mezi oceněními a čestnými tituly získanými za práci během druhé světové války a jeho následné matematické práce:

• 1958 – člen Královské společnosti Kanady ;
• 1971 - Cena Jeffreyho Williamse Kanadské matematické společnosti;
• 1975 Medaile Henryho Marshalla Toryho od Královské společnosti Kanady
• 1987 – člen Královské společnosti v Londýně ;
• 1998 - jmenován čestným ředitelem Centra aplikovaného kryptografického výzkumu [11] ;
• 2001 - důstojník Řádu Kanady ;
• 2001 - cena CRM-Fields-PIMS .

V letech 1959-1960 také pracoval jako knihovník Kanadské královské astronomické společnosti a po něm byla pojmenována planetka (14989) Tutt .

V roce 2011, jako uznání Tuttovy práce v Bletchley Parku, pojmenovalo Centrum pro bezpečnost komunikací Kanady na jeho počest Ústav matematiky a výpočetní techniky [12] .

V září 2014 byla na jeho počest postavena socha v Newmarketu  , rodném městě Thatty.

Knihy

• Tutte, WT (1966), Konektivita v grafech , sv. 15, Matematické expozice, Toronto, Ontario: University of Toronto Press 
• Tutte, WT (1966), Úvod do teorie matroidů , Santa Monica, Kalifornie: Zpráva RAND Corporation R-446-PR  . Také Tutte, WT (1971), Úvod do teorie matroidů , sv. 37, Moderní analytické a výpočetní metody ve vědě a matematice, N. Y. : American Elsevier Publishing Company, ISBN 978-0-444-00096-5 
• Tutte, WT, ed. (1969), Nedávný pokrok v kombinatorice. Sborník příspěvků ze třetí konference o kombinatorice ve Waterloo, květen 1968 , N. Y. - L. : Academic Press, s. xiv+347, ISBN 978-0-12-705150-5 
• Tutte, WT (1979), McCarthy, D. & Stanton, RG, eds., Selected papers of WT Tutte, Vols. I, II. , Winnipeg, Manitoba: Charles Babbage Research Center , St. Pierre, Manitoba, Kanada, s. xxi+879 
  • Svazek I: ISBN 978-0-9690778-1-7
  • Svazek II: ISBN 978-0-9690778-2-4
• Tutte, WT (1984), Teorie grafů , sv. 21, Encyklopedie matematiky a jejích aplikací, Menlo Park, Kalifornie: Addison-Wesley Publishing Company, ISBN 978-0-201-13520-6  přetištěno Cambridge University Press 2001, ISBN 978-0-521-79489-3
  • W. Tutt. Teorie grafů. — M .: Mir, 1988. [13]
• Tutte, WT (1998), Teorie grafů, jak jsem ji znal , sv. 11, Oxfordský cyklus přednášek z matematiky a jejích aplikací, Oxf. : Clarendon Press, ISBN 978-0-19-850251-7  Přetištěno 2012, ISBN 978-0-19-966055-1

Poznámky

1. ↑ 1 2 Archiv historie matematiky MacTutor
2. ↑ Polymer International  - Wiley- Blackwell . — ISSN 0959-8103 ; 1097-0126 – doi:10.1002/(ISSN)1097-0126
3. ↑ 1 2 Matematická genealogie  (anglicky) - 1997.
4. ↑ 12 O'Connor , 2003 , str. jeden.
5. ↑ 1 2 Copeland, 2006 , s. 352-353.
6. ↑ Dan van der Vat . Nekrolog: William Tutte Archivováno 29. listopadu 2012 na Wayback Machine . // Opatrovník. — 2002.
7. ↑ West Montrose United Cemetery . Datum přístupu: 9. prosince 2015. Archivováno z originálu 1. února 2017. (neurčitý)
8. ↑ Copeland, 2006 , str. 356-357.
9. ↑ Smith, 2011 .
10. ↑ Arthur M. Hobbs a James G. Oxley . William T. Tutte (1917-2002) Archivováno 12. března 2017 na Wayback Machine . // Oznámení Americké matematické společnosti. - 2004. - ne. 5.
11. ↑ Barbara Elve . Tutte oceněný kryptografickým centrem Archivováno 4. března 2016 na Wayback Machine
12. ↑ Colin Freeze . Přísně tajný institut vychází ze stínu, aby rekrutoval nejlepší talenty Archivováno 4. března 2016 na Wayback Machine . // Zeměkoule a pošta. — 2011.
13. ↑ Teorie grafů – W. Tutt – Google Libri

Literatura

• Jack Copeland. Colossus : The Secrets of Bletchley Park's Codebreaking Computers. — Oxf. : Oxford University Press , 2006. - 287 s. — 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. Historický slovník námořní inteligence. - Scarecrow Press, 2010. -ISBN 9780810873773.
• J. O'Connor, E. F. Robertson. MacTutor Biografie: William Thomas Tutte . — University of St Andrews, 2003.
• Mark Ward. Stroj na rozluštění kódů se vrátil k životu  // BBC News .