Cifre și spioni
În Math Corner de astăzi, voi arunca o privire asupra unui subiect pe care l-am discutat la Tabăra anuală de știință pentru copii a Fundației Naționale pentru Copii. Fundația caută copii și tineri cu interese științifice. Nu trebuie să fii extrem de dotat, dar trebuie să ai o „sine științifică”. Nu sunt necesare note școlare foarte bune. Încercați, s-ar putea să vă placă. Dacă sunteți elev în școală primară sau liceu, aplicați. De obicei, părinții sau școala fac rapoartele, dar nu este întotdeauna cazul. Găsiți site-ul Fundației și aflați.
În școală se vorbește din ce în ce mai mult despre „codare”, referindu-se la activitatea cunoscută anterior ca „programare”. Aceasta este o procedură comună pentru educatorii teoreticieni. Ei dezgroapă metode vechi, le dau un nume nou, iar „progresul” se face de la sine. Există mai multe zone în care apare un astfel de fenomen ciclic.
Se poate concluziona că devalorizez didactica. Nu. În dezvoltarea civilizației, ne întoarcem uneori la ceea ce a fost, a fost abandonat și acum este reînviat. Dar colțul nostru este matematic, nu filozofic.
Apartenența la o anumită comunitate înseamnă și „simboluri comune”, lecturi comune, zicători și pilde. Cel care a învățat perfect limba poloneză „există un desiș mare în Szczebrzeszyn, un gândac bâzâie în stuf” va fi imediat expus ca spion al unui stat străin dacă nu răspunde la întrebarea ce face ciocănitoarea. Bineînțeles că se sufocă!
Aceasta nu este doar o glumă. În decembrie 1944, nemții și-au lansat ultima ofensivă în Ardeni, cu cheltuieli mari. Ei au mobilizat soldați care vorbeau fluent engleza pentru a perturba mișcarea trupelor aliate, de exemplu, conducându-le în direcția greșită la răscruce de drumuri. După un moment de surpriză, americanii au început să pună soldaților întrebări suspecte, ale căror răspunsuri ar fi evidente pentru o persoană din Texas, Nebraska sau Georgia și de neconceput pentru cineva care nu a crescut acolo. Necunoașterea realităților a dus direct la execuție.
Până la punctul. Recomand cititorilor cartea lui Lukasz Badowski și Zaslaw Adamashek „Laboratorul într-un sertar de birou – Matematică”. Aceasta este o carte minunată care arată cu brio că matematica este cu adevărat utilă pentru ceva și că „experimentul de matematică” nu sunt cuvinte goale. Include, printre altele, construcția descrisă a „enigmei de carton” - un dispozitiv care ne va dura doar cincisprezece minute pentru a fi creat și care funcționează ca o mașină de cifrat serioasă. Ideea în sine era atât de cunoscută, autorii menționați au pus-o la punct frumos și o voi schimba puțin și o împachetez în haine mai matematice.
ferăstraie
Pe una dintre străzile satului meu dacha din suburbiile Varșoviei, pavajul a fost recent demontat din „trlinka” - plăci de pavaj hexagonale. Călătoria a fost incomodă, dar sufletul matematicianului s-a bucurat. Acoperirea planului cu poligoane regulate (adică regulate) nu este ușoară. Poate fi doar triunghiuri, pătrate și hexagoane regulate.
Poate am glumit puțin cu această bucurie spirituală, dar hexagonul este o figură frumoasă. Din el puteți face un dispozitiv de criptare destul de reușit. Geometria va ajuta. Hexagonul are simetrie de rotație - se suprapune atunci când este rotit cu un multiplu de 60 de grade. Câmpul marcat, de exemplu, cu litera A în stânga sus smochin. 1 după ce se întoarce prin acest unghi, va cădea și în caseta A - și la fel cu alte litere. Deci, să decupăm șase pătrate din grilă, fiecare cu o literă diferită. Punem grila obtinuta in acest fel pe o coala de hartie. În cele șase câmpuri libere, introduceți șase litere din textul pe care vrem să-l criptăm. Să rotim foaia la 60 de grade. Vor apărea șase câmpuri noi - introduceți următoarele șase litere ale mesajului nostru.
Orez. 1. Trlink-uri ale bucuriei matematicii.
În dreapta smochin. 1 avem un text codificat astfel: „Există o locomotivă cu abur uriașă grea în gară”.
Acum puțină matematică la școală va fi utilă. În câte moduri pot fi aranjate două numere unul față de celălalt?
Ce întrebare stupidă? Pentru doi: fie unul în față, fie celălalt.
Amenda. Și trei numere?
De asemenea, nu este dificil să enumerați toate setările:
123, 132, 213, 231, 312, 321.
Ei bine, este pentru patru! Încă poate fi precizat clar. Ghiciți regula de ordine pe care am pus-o:
1234, 1243, 1423, 4123, 1324, 1342,
1432, 4132, 2134, 2143, 2413, 4213,
2314, 2341, 2431, 4231, 3124, 3142,
3412, 4312, 3214, 3241, 3421, 4321
Când cifrele sunt cinci, obținem 120 de setări posibile. Să-i numim permutări. Numărul de permutări posibile ale n numere este produsul 1 2 3 ... n, numit puternic și marcat cu un semn de exclamare: 3!=6, 4!=24, 5!=120. Pentru următorul număr 6 avem 6!=720. Vom folosi asta pentru a face scutul nostru de cifră hexagonal mai complex.
Alegem o permutare a numerelor de la 0 la 5, de exemplu 351042. Discul nostru hexagonal de amestecare are o liniuță în câmpul din mijloc - pentru a putea fi pus „în poziția zero” - o liniuță în sus, ca în fig. 1. Punem discul astfel pe o coală de hârtie pe care trebuie să ne scriem raportul, dar nu îl scriem imediat, ci îl întoarcem de trei ori cu 60 de grade (adică 180 de grade) și introducem șase litere în câmpurile goale. Ne întoarcem la poziția de start. Rotim cadranul de cinci ori cu 60 de grade, adică cu cinci „dinți” ai cadranului nostru. Imprimăm. Următoarea poziție a scalei este poziția rotită cu 60 de grade în jurul zero. Poziția a patra este 0 grade, aceasta este poziția de pornire.
Înțelegi ce s-a întâmplat? Avem o oportunitate suplimentară - să ne complicăm „mașina” de peste șapte sute de ori! Deci, avem două poziții independente ale „automatului” - alegerea grilei și alegerea permutației. Grila poate fi aleasă în 66 = 46656 moduri, permutarea 720. Aceasta oferă 33592320 de posibilități. Peste 33 de milioane de cifruri! Aproape puțin mai puțin, pentru că unele grile nu pot fi tăiate din hârtie.
În partea inferioară smochin. 1 avem un mesaj codificat astfel: „Vă trimit patru divizii de parașute”. Este ușor de înțeles că inamicul nu ar trebui să aibă voie să știe despre asta. Dar va înțelege el ceva din acestea:
ТПОРОПВМАНВЕОРДИЗЗ
YYLOAKVMDEYCHESH,
chiar si cu semnatura 351042?
Construim Enigma, o mașină de cifrat germană
Orez. 2. Un exemplu de configurare inițială a mașinii noastre de criptare.
Permutări (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
După cum am menționat deja, datorez cărții „Lab in a Drawer - Mathematics” ideea de a crea o astfel de mașină de carton. „Construcția” mea este oarecum diferită de cea dată de autorii ei.
Mașina de cifrare folosită de germani în timpul războiului avea un principiu ingenios de simplu, oarecum asemănător cu cel pe care l-am văzut cu cifrul hexadecimal. De fiecare data acelasi lucru: rupe alocarea grea a unei scrisori unei alte scrisori. Trebuie să fie înlocuibil. Cum să o faci pentru a avea control asupra ei?
Să alegem nu orice permutare, ci una care are cicluri de lungime 2. Mai simplu spus, ceva de genul „Gaderipoluk” descris aici acum câteva luni, dar care acoperă toate literele alfabetului. Să fim de acord asupra a 24 de litere - fără ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Câte astfel de permutări? Aceasta este o sarcină pentru absolvenții de liceu (ar trebui să o poată rezolva imediat). Câți? Mult? Câteva mii? Da:
1912098225024001185793365052108800000000 (să nu încercăm nici măcar să citim acest număr). Există atât de multe posibilități de a seta poziția „zero”. Și poate fi dificil.
Mașina noastră constă din două discuri rotunde. Pe una dintre ele, care este încă în picioare, sunt scrise scrisori. Este un pic ca formarea unui telefon vechi, unde ai format un număr rotind selectorul până la capăt. Rotary este al doilea cu o schemă de culori. Cel mai simplu mod este să le pui pe un dop obișnuit folosind un ac. În loc de plută, puteți folosi o placă subțire sau un carton gros. Lukasz Badowski și Zasław Adamaszek recomandă plasarea ambelor discuri într-o cutie de CD.
Imaginează-ți că vrem să codificăm cuvântul ARMATY (Orez. 2 și 3). Setați dispozitivul în poziția zero (săgeată în sus). Litera A corespunde lui F. Rotiți circuitul intern cu o literă spre dreapta. Avem litera R de codat, acum îi corespunde A. După următoarea rotație, vedem că litera M îi corespunde U. Următoarea rotație (a patra diagramă) dă corespondența A - P. Pe cadranul al cincilea avem T - A. În cele din urmă (al șaselea cerc) Y – Y Probabil că inamicul nu va ghici că CFCFA-urile noastre vor fi periculoase pentru el. Și cum vor citi „ai noștri” mesajul? Trebuie să aibă aceeași mașină, aceeași „programată”, adică cu aceeași permutare. Cifrul începe de la poziția zero. Deci valoarea lui F este A. Rotiți cadranul în sensul acelor de ceasornic. Litera A este acum asociată cu R. El întoarce cadranul la dreapta și sub litera U găsește M, etc. Funcționarul de criptare aleargă la general: „Generale, raportez, vin armele!”
Orez. 3. Principiul de funcționare al lucrării noastre Enigma.
| Orez. 3. Principiul de funcționare al lucrării noastre Enigma. | ||
Posibilitățile chiar și ale unei astfel de Enigme primitive sunt uimitoare. Putem alege alte permutări de ieșire. Putem - și există și mai multe oportunități aici - nu printr-un „serif” în mod regulat, ci într-o anumită ordine de schimbare zilnică, similară cu un hexagon (de exemplu, primele trei litere, apoi șapte, apoi opt, patru ... .. etc. .).
Cum poți ghici?! Și totuși pentru matematicienii polonezi (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) s-a întâmplat. Informațiile astfel obținute au fost de neprețuit. Anterior, au avut o contribuție la fel de importantă la istoria apărării noastre. Vaclav Serpinski i Stanislav Mazurkevicicare a încălcat codul trupelor ruse în 1920. Cablul interceptat i-a oferit lui Piłsudski posibilitatea de a face celebra manevră de pe râul Vepsz.
Îmi amintesc de Vaslav Sierpinski (1882-1969). Părea un matematician pentru care lumea exterioară nu exista. Nu a putut vorbi despre participarea sa la victoria din 1920 atât din motive militare, cât și... din motive politice (autoritățile Republicii Populare Polone nu i-au plăcut pe cei care ne-au apărat de Uniunea Sovietică).
Orez. 4. Permutație (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Orez. 5. Decor frumos, dar nu este potrivit pentru criptare. Prea regulat.
Sarcina 1. Na smochin. 4 ai o altă permutare pentru a crea Enigma. Copiați desenul pe xerograf. Construiește o mașină, codifică-ți numele și prenumele. CWONUE JTRYGT al meu. Dacă trebuie să-ți păstrezi notele private, folosește Cardboard Enigma.
Sarcina 2. Criptează-ți numele și prenumele uneia dintre „mașinile” pe care le-ai văzut, dar (atenție!) cu o complicație suplimentară: întoarcem nu o crestătură la dreapta, ci conform schemei {1, 2, 3, 2, 1, 2, 3, 2, 1, ....} - adică mai întâi cu unul, apoi cu doi, apoi cu trei, apoi cu 2, apoi din nou cu 1, apoi cu 2 etc., o astfel de „undă” . Asigurați-vă că numele și numele meu sunt criptate ca CZTTAK SDBITH. Acum înțelegi cât de puternică a fost mașina Enigma?
Rezolvarea problemelor pentru absolvenții de liceu. Câte opțiuni de configurare pentru Enigma (în această versiune, așa cum este descris în articol)? Avem 24 de scrisori. Selectăm prima pereche de litere - acest lucru se poate face pe
moduri. Următoarea pereche poate fi aleasă pe
moduri, mai mult
etc. După calculele corespunzătoare (toate numerele trebuie înmulțite), obținem
151476660579404160000
Apoi împărțiți acel număr la 12! (12 factorial), deoarece aceleași perechi pot fi obținute într-o ordine diferită. Deci, în final, obținem „total”
316234143225,
este puțin peste 300 de miliarde, ceea ce nu pare a fi un număr uluitor de mare pentru supercalculatoarele de astăzi. Cu toate acestea, dacă se ia în considerare ordinea aleatorie a permutărilor în sine, acest număr crește semnificativ. Ne putem gândi și la alte tipuri de permutări.
A se vedea, de asemenea:
