## 12.5 Het algoritme van Euclides en Excel

Wanneer je het algoritme voor echt grote getallen moet uitvoeren, doe je het natuurlijk niet met de hand, maar wordt er een computerprogramma geschreven dat het werk voor je doet. Dit is niet zo moeilijk en je zou het eens kunnen proberen als je informatica hebt gekozen. In de antwoorden van les 10 vind je bij opgave 2 de pseudo-code voor een recursieve formule.
Voor de getallen waarmee wij werken in deze module heb je voldoende aan een rekenblad zoals Excel.
Hoe je dit in Excel uitvoert wordt gedemonstreerd in dit filmpje.

Klik hier voor film.

In opgave 9b hebben we berekend dat de ggd(484,576)=4. Als we het getallenpaar (484,576) zouden gebruiken om het klare alfabet te vercijferen dan blijkt het een beetje mis te gaan. Alle getallen in de bewerking blijken veelvouden van 4 te zijn! Ondanks dat de getallen van het getallenpaar groot genoeg zijn om 26 verschillende getallen op te leveren voor de vercijfering, krijgen we toch een probleem bij het ontcijferen. Er is geen inverse te vinden voor de ontcijfering. Als we echter 484 en 576 delen door 4, dan krijgen we getallen waarvoor de ggd gelijk is aan 1: ggd(121,144)=1. De inverse van 121 blijkt 25 te zijn waarmee we nu wel de code kunnen ontcijferen.
Onderzoek het probleem in het volgende werkblad in kolom C en D en de oplossing voor het probleem in kolom F en G:

Reflectie

In het voorbeeld bij opgave 8 en bij opgave 9a en 9c wordt steeds een ggd berekend die ongelijk is 1.
Welke getallenparen kun je daaruit afleiden die geschikt zijn om te gebruiken voor een encryptie met modulo-vermenigvuldiging?

klik hier

In les 9 hebben we met gebruik van de computer de letters van de klare tekst één voor één omgezet in ASCII-code. We hebben toen het volgende voorbeeld bekeken:
Voorbeeld
De zin: "Ik wou dat ik 2 hondjes was".
wordt gecodeerd in de volgende rij gehele getallen
073 107 032 119 111 117 032 100 097 116 032 105 107 032
050 032 104 111 110 100 106 101 115 032 119 097 115 046

We hebben een mogelijkheid om dit met de computer, rekenblad en een getallenpaar te versleutelen. We voegen de codes twee aan twee bij elkaar tot 6-cijferige getallen:
073107 032119 111117 032100 097116 032105 107032
050032 104111 110100 106101 115032 119097 115046
We zoeken een getallenpaar waarvan de modus groot genoeg is, bijvoorbeeld (1234,192731).
Merk op dat de ggd(1234,192731)=1:

a | m | q | r
1234 | 192731 | 0 | 1234
192731 | 1234 | 156 | 227
1234 | 227 | 5 | 99
227 | 99 | 2 | 29
99 | 29 | 3 | 12
29 | 12 | 2 | 5
12 | 5 | 2 | 2
5 | 2 | 2 | 1
2 | 1 | 2 | 0
1 | 0 |  |

We gebruiken nu het rekenblad om de tekst te vercijferen en vermenigvuldigen alle getallen met 1234 mod 192731.
Noteer de code op de eerste rij en sleep de functie REST(getal*1234;192731) over de tweede rij:

Met het resultaat kunnen we nu de boodschap versturen:
015 930 124 991 086 637 101 545 155 193 107 715 056 753
065 568 114 128 180 776 064 285 099 472 104 676 116 748
Zonder sleutel zal het lastig worden deze boodschap te ontcijferen, zeker als je de deler 192731 niet kent.

Opgave 10

Codeer de tekst 'nijmegen' volgens de ASCII-tabel, voeg de codes twee aan twee samen tot getallen van 6 cijfers en encrypt de tekst met de encryptiefunctie E(x)=1234*x+192731 mod 437217.

Opgave 11

Een boodschap is op de afgesproken manier gecodeerd en daarna versleuteld met de encryptiefunctie
E(x)=x+398843 mod 468713
De versleutelde boodschap is 466 957 027 229 034 246 031 240.
Ontcijfer en decodeer deze boodschap.

Nu we weten hoe we een getallenpaar kunnen vinden waarvan de ggd=1 is, wordt het ook interessant om een manier te bedenken voor het vinden van de inverse, die we weer nodig hebben voor de decryptie! Het algoritme van Euclides zal ons in de volgende les helpen bij het vinden van de inverse.