Bil Tat

Bil Tat
Puno ime	Vilijam Tomas Tat
Datum rođenja	(1917-05-14)14. maj 1917.
Mesto rođenja	Njumarket, Ujedinjeno Kraljevstvo
Datum smrti	2. maj 2002.(2002-05-02) (84 god.)
Mesto smrti	Kičener, Kanada

Vilijam Tomas "Bil" Tat (14. maj 1917 - 2. maj 2002) bio je britanski razbijač šifara i matematičar. Tokom Drugog svetskog rata napravio je fundamentalni napredak u kriptoanalizi Lorencove šifre, velikog nemačkog šifarskog sistema koji je koriščen za tajne komunikacije unutar Vrhovne komande Vermahta. Strateška priroda inteligencije dobijene iz Tatovog ključnog prodora, u velikom dešifrovanju Lorencovih šifrovanih poruka, uveliko je doprinela, a možda i odlučno, porazu nacističke Nemačke. On je takođe imao niz matematičkih dostignuća, uključujući i rad na temeljima iz oblasti teorije grafova i teorije matroida.

Tatovo istraživanje u oblasti grafova pokazalo se od izuzetnog značaja. U vreme kada je teorija grafova još uvek bila primitivna tema, Tat je počeo da proučava matroide (uređene parove) i razvio ih u teoriju proširujući rad koji je Hasler Vitni razvio oko sredine 1930-ih. Iako su Tatovi doprinosi teoriji grafova imali uticaj na savremenu teoriju grafova i mnoge od njegovih teorema su korišćene da nastave napredak na tom polju, većina njegove terminologije nije bila u skladu sa njihovom konvencijalnom upotrebom. Samim tim njegovu terminologiju ne koriste današnji teoretičari grafova.

Detinjstvo, mladost i školovanje

Tat je rođen u Njumarketu u Safoku. On je bio mlađi sin Vilijama Džona Tata (1873 – 1944), baštovana, i Eni (1881 – 1956), kućne pomoćnice. U Engleskoj je pohađao osnovnu školu i sa deset godina osvojio stipendiju na Kembridžu. Godine 1935. dobio je stipendiju za fakultet prirodnih nauka na Triniti koledžu gde se specializovao u oblasti hemije i diplomirao sa prvoklasnim počastima 1938. Nastavio je sa fizičkom hemijom kao apsolvent ali se kasnije prebacio na oblasti matematike krajem 1940. Kao student (uz svoja tri prijatelja) prvi je rešio problem deljenja kvadrata na kvadrate. Sva četvorica su zajedno stvorila pseudonim Blanš Dekart iza koga se Tat krio godinama.

Drugi svetski rat

Ubrzo nakon izbijanja Drugog svetskog rRata, Tatov učitelj, Patrik Daf, predložio ga je za ratni posao u Vladinoj školi za Kodiranje i Šifru u Blečli Parku (BP). Intervjuisan je, i poslat na obuku u Londonu pre odlaska u Blečli park, gde se pridružio Istraživačkom Odseku. U početku, radio je na Hagelinovoj šifri, koju je koristila Italijanska mornarica. Bila je to rotor šifrirajuća mašina koja je dostupna komercijalno, pa je mehanika šifrovanja bila poznata, a dešifrovanje poruka zahtevalo samo shvatanje kako je mašina postavljena.

U leto 1941, Tat je prebačen da radi na projektu nazvan Riba(engl. FISH). Obaveštajne informacije su otkrile da su Nemci  pozvali bežični teleprinter prenosni sistem  "Sägefisch" (sawfish – riba testerača). Ovo je navelo britance da koriste kod Riba (engl. Fish) za nemački teleprinter šifrirajući sistem. Nadimak Tani (engl. Tunny - tunafish, tuna) je korišćen za prvi ne-Morzeov link, i to je subsekventno korišćeno za Lorencovu SZ mašinu i poruke koje je ona kodirala.

Telegrafija je koristila 5-bitnu Međunarodnu Telegrafsku Abecedu Br. 2 (engl. ITA2)  Ništa se nije znalo o mehanizmu šifrovanja, osim toga da je porukama prethodio indikator od 12 slova koji je podrazumevao rotor šifrirajuću mašinu sa 12 točkova. Prvi korak morao je da biti dijagnostikovanje mašina uspostavljanjem logičke strukture i time funkcionisanje mašina. Tat je ovde odigrao ključnu ulogu, nedugo pre pobede saveznika u Evropi 1945,  kada je Blečli park kupio Tani Lorencvu mašinu za šifrovanje. Tatova istraživanja na kraju su dovela do dešifrovanja Tani-šifrovanih poruka između nemačke Vrhovne komande Vermahta (OKW)  u Berlinu i njihovih vojnih komandi širom okupirane Evrope, i doprinele su - možda po najviše- porazu Nemačke.

Dijagnostikovanje mašine za šifrovanje

Dana 31. avgust 1941, dve verzije iste poruke su poslate korišćenjem identičnog ključa, koji je sadržao dubinu. Ovo je dozvolilo Džon Tiltmanu, Blečliparkskom veteranu i izrazito talentovanom kriptoanalizeru, da zaključi da je u pitanju Vemam koder koji koristi funkciju isključive disjunkcije (XOR) - označava se sa "⊕", i da dekodira obe poruke, time dobijajući nejasan ključ. Nakon besplodnog perioda tokom kog je Istraživački Odsek kriptoanalizera pokušavalo da zaključi kako Tani mašina funkcioniše, ovaj i neki drugi ključevi su predati Tutu, od koga su zatražili da "vidi šta može da učini od njih".

Tokom svoje obuke, Tat je naučio Kasiski tehniku pregledanja pisanja na kbadratni papir, započinjući nobi red posle definisanog broja karaktera za koje je smatralo da je frekvencija ponavljanja ključa. Ako je broj tačan, kolone matrice bi pokazale više ponavljanja sekvenci nego slučajno. Tat je znao da Tanijevi indikatori koriste 25 slova(uključujući j) za 11 pozicija, ali samo 23 slova za ostale. Tako je pokušao Kasiskijebu tehniku na prvom impulsu ključa karaktera koristeći ponavljanja 25 h 23 = 575. Nije posmatrao veliki broj ponavljanja u koloni sa ovim periodom, nego fenomen dijagonale. Tako je opet pokušao sa 574, koje je pokazivalo ponavljanje u kolonama. Prepoznajući da su prosti činioci ovog broja 2, 7 i 41, pokušao je opet sa periodom od 41 i dobio "trougao tačaka i krstova koji je ispunjen ponavljanjima".

Bilo je očigledno da prvi impuls ključa bio komplikovaniji nego onaj napravljen od jednog točka sa 4 čegtrdeset jednim ključnim impulsom. Tat je ovo nazvao komponentom ključa H1 (χ1). Shvatio je da postoji druga komponenta koja je XOR-ovana sa ovom, koja se nije ubek menjala sa svakim novim karakterom, i da je to produkt točka koji je nazvao PSY1. Isto se primenjivalo za svaki od 5 impulsa (χ1χ2χ3χ4χ5 i ψ1ψ2ψ3ψ4ψ5). Dakle za pojedinačni karakter, ceo knjuč K se sastojao iz dve komponente:

K=χ XOR ψ

U Blečli parku, markirani impulsi su označavani sa x, a prostorni impulsi sa •. Na primer, slovo H bi se kodiralo "••x•x". Tatova derivacija chi i psi komponenata je postala moguća zahvaljujući činjenici da je iza tačke verovatnije da dolazi još jedna tačka, nego što nije, takođe i za krst (verovatnije je da dolazi još jedan krst, nego da ne dokazi). Ovo je rezultat slabosti Nemačkog ključa, koji su kasnije eleminisali. Jednom kad je Tat došao do tog otkrića, ostatak Istraživačkog Odseka se pridružio u proučavanju ostalih impulsa, i otkriveno je da pet chi točkova napredovalo svakim novim karakterom i da je pet psi točkova pomerano zajedno pod kontrolom mu ili "motor" točkova. U toku sledeća dva meseca, Tat i ostatak članova Istraživačkog Odseka su shvatili kompletnu logičku strukturu mašine, sa njenim skupom točkova koji su sadržali bregove koji su mogli biti ili u poziciji (podignuti) da dodaju x u niz karaktera, ili u alternativnoj poziciji da dodaju • .

Dijagnostikovanje funkcionalne Tanijebe mašine na ovaj način je istinski značajano kriptoanalitičko dostignuće koje je, u citatu za Tatubu indukciju kao Officer of the Order of Canada, je opisano kao jedno od "najvećih intelektualnih dostignuća Drugog svetskog rata".

Tatov statistički metod

Za dekodiranje Tani(engl. Tunny) poruke bilo je potrebno znanje ne samo logičkog načina funkcionisanja mašine, ali takođe i početni položaj svakog rotora za određenu poruku. Istrazivao je način na koji bi manipulacijom čipteksta stvorio spektar frekvencija koji bi odudarao obliku koji je taj proces težio da stvori. Dok je bio upućen na Istraživački Odsek u julu 1942, Alan Tjuring je shvatio da je nili kombinacija vrednosti uzastopnih karaktera u redu šifrovanog teksta i ključ je naglašavao na bilo kakva odstupanja od standardne distibucije. Rezultantni tok (simbolizovan grčkim slovom "delta" Δ) nazvan je razlikom jer je nili kombinacija ista kao oduzimanje po modulu 2.

Razlog zbog kojeg je to omogućilo dešifrovanje mašine bio je da, iako se frekventna raspodela znakova u šifriranom tekstu ne može razlikovati od slučajnog toka, isto tako nije važilo za verziju šifriranog teksta iz koje je či (eng. chi) element ključa bio uklonjen. U tom slučaju, zbog toga što je otvoreni tekst sadržao ponovljeni karakter i psi točkovi nisu krenuli dalje, diferencirani psi karakter (Δ) bi bio nulti karakter ('/' u Bletčli Parku(engl. Bletchley Park)). Kada bi bila izvršena operacija nili (XOR) sa bilo kojim znakom, ovaj karakter ne bi imao efekta. Ponovljeni znakovi u otvorenom tekstu bili su češći kako zbog karakteristika nemačkog jezika (EE, TT, LL i SS (nemački: EE, TT, LL i SS) su relativno česti), tako i zbog toga što su telegrafi često ponavljali znakove velikih brojeva i velikih slova, koji bi svojim gubitakom u običnoj telegrafskoj poruci mogli dovesti do besmislica.

Generalni Izveštaj o Tani:

Turingeri (engl. Turingery) je uveo princip da bi ključna razlika u jednom, sada nazvana ΔΚ, mogla doneti informacije koje se ne mogu dobiti od običnog ključa. Ovaj princip Δ bio je osnovna osnova gotovo svih statističkih metoda razbijanja točkova.

Tat je iskoristio ovo pojačanje nejednakosti u diferenciranim vrednostima, a do novembra 1942. proizveo je način za otkrivanje polaznih tačaka točkova mašine koja je postala poznata kao "Statistička metoda". Suština ove metode bila je da se pronađu početna podešavanja či (chi) komponente ključa iscrpnim isprobavanjem svih pozicija njegove kombinacije sa šifriranim tekstom i traženjem dokaza o nejednakosti koja odražava karakteristike originalnog otvorenog teksta. Zato što bi svi ponavljani znakovi u otvorenom tekstu uvek generisali • i slično ∆ψ₁ ⊕ ψ∆₂ bi generisao • kad god se psi(psi) točkovi ne pomeraju, a oko pola vremena kada su radile - ukupno oko 70%.

Pored primene diferencijacije na pune 5-bitne znakove ITA2 (engl. ITA2)koda, Tat ga je primenio na pojedinačne impulse (bitove). Postavke trenutnog či (chi) kotura trebalo je da budu uspostavljene kako bi se omogućila relevantna sekvenca znakova da se generišu či (chi) točkovi. Bilo je potpuno nepraktično generisati 22 miliona znakova iz svih pet či (chi) točkova, tako da je u početku bila ograničena na 41 × 31 = 1271 od prva dva. Nakon što je objasnio svoje nalaze Maku Njumanu, Njuman je dobio zadatak da razvije automatizovani pristup poređenju šifriranog teksta i ključa za traženje odstupanja od slučajnosti. Prva mašina je nazvana Hit Robinson (engl. Heath Robinson), ali mnogo brži računar Kolos (engl. Colossus computer), koji je razvio Tomi Flovers (engl. Tommy Flowers) i koristeći algoritme koje je napisao Tat i njegove kolege, ubrzo je preuzeo razbijanje kodova.

Doktorat i karijera

Tat je doktorirao matematiku na Kembridžu 1948. godine pod montorstvom Šauna Vilija, koji je takođe radio u Bletčli Parku na Taniju. Krajem 1945. godine, Tate je nastavio studije na Kembridžu, sada kao diplomirani student matematike. On je objavio neke ranije započete radove, jedan od danas poznatih radova koji karakterišu grafikoni koji imaju savršeno podudaranje, a drugi koji konstruiše ne-Hamiltonov graf(eng. non-Hamiltonian graph). On je stvorio revolucionarnu doktorsku tezu, Algebarska teorija grafova, o temi kasnije poznatoj kao teorija matroida.

Iste godine, pozvan od Harolda Skota Makdonalda Koksetera(engl. Harold Scott MacDonald Coxeter), prihvatio je poziciju na Univerzitetu u Torontu. Godine 1962. preselio se na Univerzitet Voterlu u Voterluu, Ontario, gde je ostao do kraja akademske karijere. Zvanično je penzionisan 1985. godine, ali je ostao aktivan kao redovni profesor u penziji. Tate je pomogao u osnivanju Odeljenja za kombinatoriku i optimizaciju na Univerzitetu Voterlu.

Njegova matematička karijera bila je usredsređena na kombinatoriku, posebno na teoriju grafova, za koju je smatrao da je pomogao u stvaranju moderne forme i teoriji matroida, na koju je dao značajan doprinos; jedan kolega ga je opisao kao "vodećeg matematičara u kombinatorici tri decenije". Bio je glavni urednik Žurnala kombinatorne teorije (engl. Journal of Combinatorial Theory) dok se nije povukao iz Vaterlua 1985. Takođe je bio član uredničkih odbora nekoliko drugih časopisa za matematička istraživanja.

Doprinosi matematici

Tat je takođe razvio algoritam za određivanje da li je zadat binaran matroid cikličan.

Tat je napisao rad sa naslovom Kako nacrtati graf? u kome je dokazao da je svaka oblast u 3-povezanom grafu ograđena perifernim ciklusom. Koristeći ovu činjenicu, Tat je razvio alternativni dokaz da je svaki graf Kuratovskog je neplanaran pokazavši da grafovi K₅ i K_3,3 sadrže po 3 različita periferna ciklusa sa zajedničkom granom. Osim što je koristeći periferne cikluse da dokaže da su grafovi Kuratovskog neplanarni, Tat je dokazao da svaki 3-povezan graf može da s nacrta sa svim konveksnim oblastima, i osmislio algoritam koji konstruiše ravan rešavanjem sistem linearnih jednačina. Rezultujuća skica je poznata kao Tatovo ugrađivanje. Tatov algoritam koristi baricentarni kordinatni sistem perifernih ciklusa jednostavnih 3-povezanih grafova.

Uspostavilo se da su tvrđenja koja je objavivao u svojim radovima od veoma velikog značaja zato što su algoritmi koje je Tat razvio postali popularne metode crtanja planarnih grafova. Jedno od glavnih razloga zbog koga je Tateovo ugrađivanje popularno je zato što su neophodna izračunavanja u njegovih algoritamu jendostavna i garantuju 1-1 odnos između grafa i njegovog prikaza u Euklidskom prostoru, što je ključno kada želimo da parametrizujemo trodimenzionalnu mrežu na ravan. "Tateova teorema je osnova rešenja za sve ostale probleme kompjuterske grafike, kao što je pretapanje slika.

Tat je primarno zaslužan za napredak teorije numeracije planarnih grafova, koji sadrže bliske povezanosti sa hromatskim i dihromatskim polinomijama. Njegov rad je uključio neke veoma napredne tehnologije koje je on izumeo, sadržavši značajne stepene redove (čiji koeficijenti broje odgovarajuće vrste grafova) i funkcije koje isplivavaju kao njihove sume, kao i geometrijsku spretnost u uočavanju tih redova u kontekstu teorije grafova.

Tat je sav svoj rad sumirao u knjizi "Izabrani radovi V. T. Tatea", 1979 i u "Teorija grafova kao što je znamo" 1998.

Pozicije, počastvovanja i nagrade

Tatov rad tokom Drugog svetskog rata zajedno, kao i kasnije u polju kombinatorike, doneo mu je razne pozicije, počastvovanja i nagrade:

Tat je bio bibliotekar u Elitnom astronomskom društvu u Kanadi 1959-1960. godine, čak je i asteroid 14989 Tat (1997 UB7) nazban po njemu.

Kao posledica Tateovog rada u parku Bletčer, kanadska komunikaciona zaštita je nazvala međunarodnu organizaciju sa ciljem da promoviše kriptografiju, Tateov instiTat matematike i računarstva (eng. Tutte Institute for Mathematics and Computing (TIMC)), u njegovu čast 2011.

U septembru 2014, Tat je proslavljen u svom rodnom gradu, sa sopstvenom skulpturom, nakon sto su lokalne novine započele kampanju u memoriam njemu.

Blečli park u Milton Kajnesu je proslavio Tateov rad sa izložbom pod nazivom Bil Tat: Matematičar + Dekoder koja je bila zakazana za 15. maj 2017. godine sve do 2019, kojoj je prethodilo predavanje o njegovom životu i radu tokom Bil Tateovog vekovnog simpozijuma 14. maja 2017. godine sa.

Privatni život i smrt

Pored prednosti u sopstvenoj karijeri rad u Univerzitetu u Vaterlou, život u ruralnom delu Baterlua se njegovoj ženi Doroteji i njemu svidela. Kupili su kuću blizu mesta Istočna Montroza u Ontariju gde su uživali u planinarenju i provođenju vremena u sopstvenoj bašti na Velikoj reci. Čak su i dozvoljavali i drugima da uživaju u lepoti njihovog poseda.

Oni su imali široko znanje o pticama njihove bašte. Doroteja, strastveni baštovan, je bila i planinar. Zajedno sa Bilom su organizovali planinarske izlete. Pred kraj svog života Bil je idalje uživao u dugim šetnjama. Nakon smrti njegove žene 1994, vratio se u Njumarket u Sufolku, ali se ipak 2000. godine vratio u Baterlu, gde je i dve godine kasnije i umro. Sahranjen je na groblju u Istočnoj Montozi.

Literatura

• Roberts, Jerry (2017). Lorenz: Breaking Hitler's top secret code at Bletchley Park. Stroud, Gloucestershire: The History Press. ISBN 978-0-7509-7885-9. 
• Copeland, B. Jack, ur. (2006). Colossus: The Secrets of Bletchley Park's Codebreaking Computers. Oxford: Oxford University Press. ISBN 978-0-19-284055-4. 
• Hinsley, Francis Harry; Stripp, Alan (2001). Codebreakers: The Inside Story of Bletchley Park. Oxford University Press. str. 141—148. ISBN 978-0-19-280132-6.