Cijfers en spionnen
In de Wiskundehoek van vandaag zal ik kijken naar een onderwerp dat ik heb besproken tijdens het jaarlijkse Kids Science Camp van de National Children's Foundation. De stichting is op zoek naar kinderen en jongeren met wetenschappelijke interesses. Je hoeft niet extreem begaafd te zijn, maar je moet wel een wetenschappelijke inslag hebben. Zeer goede schoolcijfers zijn niet vereist. Probeer het, misschien vind je het leuk. Ben je een leerling van de bovenbouw van de basisschool of middelbare school, meld je dan aan. Meestal worden meldingen gedaan door ouders of de school, maar dit is niet altijd het geval. Vind de website van de Stichting en ontdek alles.
Er wordt op school steeds meer gesproken over "coderen", verwijzend naar de activiteit die vroeger bekend stond als "programmeren". Dit is een gebruikelijke procedure voor theoretische docenten. Ze graven oude methoden op, geven ze een nieuwe naam en 'vooruitgang' wordt vanzelf gemaakt. Er zijn verschillende gebieden waar een dergelijk cyclisch fenomeen zich voordoet.
Geconcludeerd kan worden dat ik didactiek devalueer. Nee. In de ontwikkeling van de beschaving keren we soms terug naar wat was, werd verlaten en nu nieuw leven wordt ingeblazen. Maar onze hoek is wiskundig, niet filosofisch.
Tot een bepaalde gemeenschap behoren betekent ook "gemeenschappelijke symbolen", gemeenschappelijke lezingen, gezegden en gelijkenissen. Degene die perfect de Poolse taal heeft geleerd "er is een groot struikgewas in Szczebrzeszyn, een kever zoemt in het riet" zal onmiddellijk worden ontmaskerd als een spion van een vreemde staat als hij de vraag niet beantwoordt wat de specht aan het doen is. Natuurlijk is hij aan het stikken!
Dit is niet zomaar een grap. In december 1944 lanceerden de Duitsers tegen hoge kosten hun laatste offensief in de Ardennen. Ze mobiliseerden soldaten die vloeiend Engels spraken om de beweging van geallieerde troepen te verstoren, bijvoorbeeld door ze op kruispunten de verkeerde kant op te leiden. Na een moment van verbazing begonnen de Amerikanen de soldaten verdachte vragen te stellen, waarvan de antwoorden duidelijk zouden zijn voor iemand uit Texas, Nebraska of Georgia en ondenkbaar voor iemand die daar niet is opgegroeid. Onwetendheid over de realiteit leidde direct tot de executie.
Ter zake. Ik raad lezers het boek van Lukasz Badovsky en Zaslav Adamasek "Laboratorium in een bureaula - wiskunde" aan. Dit is een prachtig boek dat op briljante wijze laat zien dat wiskunde daadwerkelijk ergens nuttig voor is en dat ‘wiskunde-experiment’ niet alleen maar loze woorden zijn. Het omvat onder meer het beschreven ontwerp van een "kartonnen enigma" - een apparaat dat ons slechts vijftien minuten kost om te maken en dat werkt als een serieuze encryptiemachine. Het idee zelf was zo bekend, de genoemde auteurs hebben het prachtig uitgewerkt, en ik zal het een beetje veranderen en het in meer wiskundige kleding wikkelen.
ijzerzagen
In een van de straten van mijn vakantiedorp in de buitenwijken van Warschau is onlangs een bestrating van “trlinka” – zeshoekige straatstenen – gedemonteerd. Het was lastig om te reizen, maar de ziel van de wiskundige verheugde zich. Een vlak bestrijken met regelmatige (dat wil zeggen regelmatige) polygonen is niet eenvoudig. Dit kunnen alleen driehoeken, vierkanten en regelmatige zeshoeken zijn.
Misschien maakte ik een grapje met deze spirituele vreugde, maar de zeshoek is een prachtig figuur. Hieruit kun je een redelijk succesvol coderingsapparaat maken. Geometrie zal helpen. De zeshoek heeft rotatiesymmetrie - hij overlapt zichzelf wanneer hij wordt gedraaid met een veelvoud van 60 graden. Het veld gemarkeerd, bijvoorbeeld met de letter A in de linkerbovenhoek afb. 1 nadat hij deze hoek heeft gedraaid, valt hij ook in veld A - en hetzelfde geldt voor de andere letters. Laten we dus zes vierkanten uit het raster knippen, elk met een andere letter. Plaats het resulterende raster op een vel papier. Voer in de zes vrije velden zes letters in van de tekst die we willen coderen. Laten we het vel 60 graden draaien. Er verschijnen zes nieuwe velden. Voer de volgende zes letters van ons bericht in.
Rijst. 1. Trlinks van de vreugde van wiskunde.
Aan de rechterkant afb. 1 we hebben een tekst die op deze manier is gecodeerd: "Er is een enorme zware stoomlocomotief op het station."
Nu komt een beetje schoolwiskunde van pas. Op hoeveel manieren kunnen twee getallen ten opzichte van elkaar worden gerangschikt?
Wat een domme vraag? Voor twee: de een voor of de ander.
Prima. En drie cijfers?
Het is ook niet moeilijk om alle instellingen op een rijtje te zetten:
123, 132, 213, 231, 312, 321.
Nou, het is voor vier! Het kan nog steeds duidelijk worden beschreven. Raad de volgorde regel die ik heb gezet:
1234, 1243, 1423, 4123, 1324, 1342,
1432, 4132, 2134, 2143, 2413, 4213,
2314, 2341, 2431, 4231, 3124, 3142,
3412, 4312, 3214, 3241, 3421, 4321
Als de cijfers vijf zijn, krijgen we 120 mogelijke instellingen. Laten we ze bellen permutaties. Het aantal mogelijke permutaties van n getallen is het product 1 2 3 ... n, genaamd сильный en gemarkeerd met een uitroepteken: 3!=6, 4!=24, 5!=120. Voor het volgende getal 6 hebben we 6!=720. We zullen dit gebruiken om ons zeshoekige cijferschild complexer te maken.
We kiezen een permutatie van getallen van 0 tot 5, bijvoorbeeld 351042. Onze zeshoekige scrambling disk heeft een streepje in het middelste veld - zodat het "in de nulstand" kan worden gezet - een streepje naar boven, zoals in fig. 1. We leggen de schijf op deze manier op een vel papier waarop we ons rapport moeten schrijven, maar we schrijven het niet meteen op, maar draaien het drie keer 60 graden (dwz 180 graden) en voeren zes letters in de lege velden. We keren terug naar de startpositie. We draaien de wijzerplaat vijf keer 60 graden, dat wil zeggen vijf "tanden" van onze wijzerplaat. Wij printen. De volgende schaalpositie is de positie 60 graden rond nul gedraaid. De vierde stand is 0 graden, dit is de startstand.
Begrijp je wat er is gebeurd? We hebben een extra mogelijkheid - om onze "machine" meer dan zevenhonderd keer ingewikkelder te maken! We hebben dus twee onafhankelijke posities van de "automaat" - de keuze van het raster en de keuze van de permutatie. Het rooster kan op 66 = 46656 manieren gekozen worden, permutatie 720. Dit geeft 33592320 mogelijkheden. Meer dan 33 miljoen cijfers! Bijna iets minder, want sommige roosters kunnen niet uit papier worden gesneden.
In het onderste deel afb. 1 we hebben een bericht dat als volgt is gecodeerd: "Ik stuur je vier parachutedivisies." Het is gemakkelijk te begrijpen dat de vijand dit niet mag weten. Maar zal hij hier iets van begrijpen:
Тпоропвманвеордизз
ik,
zelfs met handtekening 351042?
We bouwen Enigma, een Duitse codeermachine
Rijst. 2. Een voorbeeld van de initiële setup van onze coderingsmachine.
Permutaties (AF) (BJ) (CL) (DW) (EI) (GT) (HO) (KS) (MX) (NU) (PZ) (RY).
Zoals ik al zei, heb ik het idee om zo'n kartonnen machine te maken te danken aan het boek "Lab in a Desk Drawer - Mathematics". Mijn ‘constructie’ wijkt enigszins af van die van de auteurs.
De codeermachine die door de Duitsers tijdens de oorlog werd gebruikt, had een ingenieus eenvoudig principe, enigszins vergelijkbaar met degene die we zagen met de hexadecimale code. Elke keer hetzelfde: harde toewijzing van een letter aan een andere letter breken. Het moet vervangbaar zijn. Hoe het te doen om er controle over te hebben?
Laten we niet zomaar een permutatie kiezen, maar een met cycli van lengte 2. Simpel gezegd, zoiets als de "Gaderipoluka" die hier een paar maanden geleden werd beschreven, maar die alle letters van het alfabet omvat. Laten we het eens worden over 24 letters - zonder ą, ę, ć, ó, ń, ś, ó, ż, ź, v, q. Hoeveel van dergelijke permutaties zijn er? Dit is een taak voor afgestudeerden van de middelbare school (ze zouden het meteen moeten kunnen oplossen). Hoeveel? Veel? Een aantal duizend? Ja:
1912098225024001185793365052108800000000 (laten we dit nummer niet eens proberen te lezen). Er zijn zoveel mogelijkheden om de "nul"-stand in te stellen. En het kan moeilijk zijn.
Onze machine bestaat uit twee ronde schijven. Op een ervan, dat nog steeds staat, zijn brieven geschreven. Het lijkt een beetje op de wijzerplaat van een oude telefoon, waarbij je een nummer hebt gekozen door de knop helemaal te draaien. Rotary is de tweede met een kleurenschema. De makkelijkste manier is om ze met een speld op een gewone kurk te zetten. In plaats van kurk kunt u een dun bord of dik karton gebruiken. Lukasz Badowski en Zasław Adamaszek raden aan om beide schijven in een cd-doosje te plaatsen.
Stel je voor dat we het woord ARMATY willen coderen (Rijst. 2 en 3). Zet het apparaat in de nulpositie (pijl omhoog). De letter A komt overeen met F. Draai het interne diagram één letter naar rechts. We moeten de letter R coderen, nu komt deze overeen met A. Na de volgende rotatie zien we dat de letter M overeenkomt met U. De volgende rotatie (vierde diagram) geeft de correspondentie A - P. Op de vijfde wijzerplaat hebben we T - A. Tenslotte (zesde cirkel) D – D De vijand zal zich waarschijnlijk niet realiseren dat onze CFK's gevaarlijk voor hem zullen zijn. Hoe zullen “onze mensen” de boodschap lezen? Ze moeten dezelfde machine hebben, identiek ‘geprogrammeerd’, dat wil zeggen met dezelfde permutatie. Het cijfer begint op positie nul. De waarde van F is dus gelijk aan A. Draai de draaiknop met de klok mee. De letter A wordt nu geassocieerd met R. Hij draait de draaiknop naar rechts en onder de letter U vindt M, enz. De cryptograaf rent naar de generaal: “Generaal, ik meld, de wapens komen eraan!”
Rijst. 3. Het werkingsprincipe van ons papier Enigma.
| Rijst. 3. Het werkingsprincipe van ons papier Enigma. | ||
De mogelijkheden van zelfs zo'n primitief Enigma zijn verbluffend. We kunnen andere uitvoerpermutaties kiezen. We kunnen - en hier zijn er zelfs nog meer mogelijkheden - niet slechts één “serif” regelmatig, maar in een bepaalde, dagelijks veranderende volgorde, zoals een zeshoek (bijvoorbeeld eerst drie letters, dan zeven, dan acht, vier... . enz.).
Hoe kun je raden?! En toch voor Poolse wiskundigen (Marian Reevski, Henryk Zigalski, Jerzy Ruzicki) gebeurd. De aldus verkregen informatie was van onschatbare waarde. Voorheen hadden ze een even belangrijke bijdrage aan de geschiedenis van onze verdediging. Vaclav Serpinski i Stanislav Mazurkevichdie in 1920 de code van Russische troepen schond. De onderschepte kabel gaf Piłsudski de mogelijkheid om de beroemde manoeuvre vanaf de rivier de Vepsz te maken.
Ik herinner me Vaslav Sierpinski (1882-1969). Hij leek een wiskundige voor wie de buitenwereld niet bestond. Hij kon niet praten over zijn deelname aan de overwinning in 1920, zowel om militaire als ... om politieke redenen (de autoriteiten van de Poolse Volksrepubliek hielden niet van degenen die ons verdedigden tegen de Sovjet-Unie).
Rijst. 4. Permutatie (AP) (BF) (CM) (DS) (EW) (GY) (HK) (IU) (JX) (LZ) (NR) (OT).
Rijst. 5. Mooie decoratie, maar niet geschikt voor encryptie. Te regelmatig.
1-taak. Na afb. 4 je hebt een andere permutatie om Enigma te maken. Kopieer de tekening naar de xerograaf. Bouw een auto, codeer je voor- en achternaam. Mijn CWONUE JTRYGT. Als u uw aantekeningen privé wilt houden, gebruikt u Cardboard Enigma.
2-taak. Versleutel je voor- en achternaam van één van de ‘auto’s’ die je zag, maar (let op!) met een extra complicatie: we draaien niet één tandje naar rechts, maar volgens het patroon {1, 2, 3, 2, 1 , 2, 3 , 2, 1, ....} – dat wil zeggen, eerst met één, dan met twee, dan met drie, dan met 2, dan weer met 1, dan met 2, enz., zo’n “golfje ”. Zorg ervoor dat mijn voor- en achternaam worden gecodeerd als CZTTAK SDBITH. Begrijp je nu hoe krachtig de Enigma-machine was?
Oplossen van problemen voor middelbare scholieren. Hoeveel opties zijn er om Enigma aan te passen (in deze versie, zoals beschreven in het artikel)? We hebben 24 brieven. Selecteer het eerste paar letters - dit kan op
manieren. Het volgende paar kan gekozen worden op
manieren, meer
enzovoort. Na de bijbehorende berekeningen (alle getallen moeten worden vermenigvuldigd), krijgen we
151476660579404160000
Deel dit getal dan door 12! (12 faculteit) omdat dezelfde paren in verschillende volgordes kunnen worden verkregen. Dus uiteindelijk krijgen we “gewoon”
316234143225,
dat is iets meer dan 300 miljard, wat niet een schrikbarend groot aantal lijkt voor de supercomputers van vandaag. Als echter rekening wordt gehouden met de willekeurige volgorde van de permutaties zelf, neemt dit aantal aanzienlijk toe. We kunnen ook andere soorten permutaties bedenken.
Zie ook:
