Les 12 Algoritme van Euclides
Inhoud van les 12: Algoritme van Euclides
12.1 Deler, priemdeler en priemfactor
12.2 Gemene delers
12.3 De grootste gemene deler
12.4 Algoritme van Euclides
12.5 Het algoritme van Euclides en Excel
12.1 Deler, priemdeler en priemfactor
Een geheel getal a is een deler van een geheel getal b als het getal a precies een geheel aantal keerin het getal b past. Meer wiskundig: een geheel getal a is een deler van een geheel getal b als er eengeheel getal k is, zodanig dat er geldt a*k = b
In de wiskunde is er een notatie voor "deler zijn van". Deze notatie is een verticale rechte streep: |. Wanneer je schrijft a | b, bedoel je dus dat a een deler is van b.
Het getal a is een priemdeler van b als a zelf een priemgetal is en als je b door a kunt delen. Voor het vervolg van de module is het belangrijk dat je jezelf er eerst van overtuigt dat je het begrippriemdeler goed beheerst. Op de sub-pagina staat een aantal opgaven over delers en priemdelers. Voer deze eerst uit voor je verder gaat.
Priemdelers.docx
In de moderne cryptografie zijn priemgetallen erg belangrijk. Dit komt doordat het voor producten van twee heel grote priemgetallen van bijvoorbeeld elk 150 cijfers lang, heel erg moeilijk is de priemfactorontbinding te bepalen, anders gezegd is het nauwelijks mogelijk te ontdekken hoe het product van de vermenigvuldiging tot stand is gekomen. Van de priemgetallen die nodig zijn voor moderne cryptografie zijn er heel veel bekend. Zoveel zelfs dat je ze niet allemaal kunt gaan proberen om een ontbinding van m te vinden. Veel grotere priemgetallen vinden van bijvoorbeeld miljoenen cijfers lang, is niet eenvoudig. De grootste bekende priemgetallen zijn Mersenne-priemgetallen, genoemd naar de Franse wiskundige Marin Mersenne. Deze priemgetallen zijn van de vorm 2p-1, waarbij p een priemgetal is. Maar niet alle getallen van deze vorm zijn priemgetallen. Voor getallen van deze vorm bestaan testen om te onderzoeken of ze priem zijn.
Klik hier om naar de site te gaan.
Leesactiviteit
Lees de tekst op onderstaande site van Kennislink over priemgetallen van meer dan 10.000.000 cijfers en beantwoord daarna de vragen.
a) Wat zijn Mersenne-getallen?
b) Wat is GIMPS?
c) Wie was Edson Smith?
d) Is het voor de cryptografie van belang dat er een priemgetal is gevonden van meer dan 10.000.000 cijfers?
klik hier
Priemfactoren van een groot samengesteld getal vinden is erg moeilijk. Zo is bijvoorbeeld wel bekend dat het getal 216384+1 niet priem is, maar is er geen enkele priemfactor van bekend. Het is een getal van 5000 cijfers.
Voor de cryptografie zijn priemgetallen van een paar honderd cijfers van belang. We zullen daar in deze module niet mee hoeven rekenen, maar we willen wel proberen te begrijpen waarom priemgetallen de oplossing boden in een zoektocht naar asymmetrische sleutels.
Daarvoor moeten we het begrip grootste gemene deler kennen. Op de sub-pagina Grootste Gemene Deler wordt een tweetal opgaven aangeboden die je moet kunnen maken om het vervolg te kunnen begrijpen. Voer de opgaven onder het kopje Grootste Gemene Deler hieronder uit .
De grootste gemene deler van a en m is het grootste gehele getal dat deler is van zowel a als m. We noteren dit als ggd(a,m).
De volgende methode is goed te doen voor kleine getallen, maar voor grote getallen is de priemfactorontbinding erg moeilijk te vinden en kun je deze methode dus niet gebruiken. Het is wel van belang om grip te krijgen op de ggd.
Eerst een voorbeeld:
Daarbij hanteren we een paar eenvoudige wetmatigheden:
Een even getal is deelbaar door 2.
Als de som van de cijfers deelbaar is door 3, dan is het getal deelbaar door 3
Als het getal eindigt op een 5 of een 0 dan is het deelbaar door 5.
Hiermee vind je de ontbindingen van de meeste 'kleine' getallen wel, maar als je meer regeltjes wilt dan kun je die vinden op http://members.chello.nl/f.waanders1/deelbaar.htm
Bepaal de ggd(264, 2436)
We ontbinden 264 en 2436 zo ver mogelijk in priemfactoren.
264=2*132=2*2*66=2*2*2*33=2*2*2*3*11
2436=2*1218=2*2*609=2*2*3*203=2*2*3*7*29
De gemeenschappelijke delers van 264 en 2436 zijn 2, 2 en 3.
De ggd(264,2436) is nu 2*2*3=12
Opgave 1
a) Geef de positieve delers van 120.
b) Geef de positieve delers van 112.
c) Wat zijn de gemeenschappelijke delers van 120 en 112?
d) Wat is grootste gemeenschappelijke deler van 120 en 112?
Nog een voorbeeld:
Bereken ggd(980, 504).
980=2*2*5*7*7,
504=2*2*2*3*3*7.
In beide priemfactorontbindingen zit twee keer de priemfactor 2 en een keer de priemfactor 7, dus ggd(980,504)=2*2*7=28.
Opgave 2
a) Bereken ggd(252, 198).
b) Bereken ggd(6466, 5429).
c) Bereken ggd(47, 0).
d) Geef ggd(a, 0) a ≠ 0.
e) Geef ggd(0,0)
Ga nu verder met 12.2 Gemene delers
12.2 Gemene delers
De Griek Euclides van Alexandrië heeft een methode beschreven waarmee je de grootste gemene deler voor grote getallen kunt berekenen. Euclides is één van de belangrijkste wiskundigen van de afgelopen 2400 jaar.
Wie was Euclides
Euclides (ook Euclides van Alexandrië genoemd) was een Griekse wiskundige uit de 3e eeuw v. Chr. die werkzaam was in de bibliotheek van Alexandrië. Zijn bekendste werk is de Elementen, een boek waarin hij de eigenschappen van geometrische vormen en gehele getallen afleidt uit een verzameling axioma's. Hij wordt daarom wel beschouwd als een voorloper van de axiomatische methode in de moderne wiskunde. Veel van de resultaten in de Elementen zijn afkomstig van eerdere wiskundigen. Euclides' belangrijke prestatie was om ze allemaal in één samenhangend logisch kader te plaatsen. Zijn vijfde postulaat staat bekend als het parallellenpostulaat. Lang is geprobeerd dit axioma, dat ingewikkelder en minder vanzelfsprekend is dan de andere, uit de eerste vier axioma's te bewijzen. Maar in de 19e eeuw realiseerden Janos Bolyai, Nikolai Ivanovich Lobachevsky en waarschijnlijk ook Carl Friedrich Gauss zich dat het verwerpen van dit postulaat leidt tot volledig consistente niet-Euclidische meetkundes, die verder werden ontwikkeld door Bernhard Riemann. Naast meetkunde behandelt de Elementen ook elementaire getaltheorie, zoals de theorie van deelbaarheid, de grootste gemene deler en het algoritme van Euclides. Tot in de 20e eeuw werd de Elementen gebruikt als leerboek voor de meetkunde en was het zelfs samen met de Bijbel een van de meest gedrukte boeken. Toch schiet Euclides' methodologie tekort vergeleken met de huidige standaard van wiskundige precisie, omdat een aantal logische axioma's ontbreekt. De moderne axiomatische behandeling van de meetkunde gaat terug op David Hilbert in 1899.
Van de wiskunde die Euclides in 'De Elementen' beschreef, gebruiken we in de cryptografie niets. Het algoritme van Euclides dat we nu gaan bespreken is wel een belangrijke stelling in de cryptografie. Hoe je het algoritme op een snelle wijze kunt toepassen in een Excel-blad wordt na opgave 9 in 12.5 gedemonstreerd in een filmpje.
Opgave 1
Het getal 11 is deler van 66 en 33.
a) Is het getal 11 ook deler van 66+33?
b) Is het getal 11 ook deler van 66-33?
c) Is het getal 11 ook deler van 33-66?
Uit opgave 1 ontstaat het vermoeden dat:
Als d een deler is van a en een deler is van b, dan is d ook een deler van a+b en a-b
Als we er goed over nadenken dan is dat ook wel logisch, immers
d is een deler van a, dus er is een geheel getal v waarvoor geldt a=v*d.
d is een deler van b, dus er is een geheel getal w waarvoor geldt b=w*d.
We kunnen a+b dus schrijven als a+b=v*d+w*d=(v+w)*d.
v+w is een heel getal, dus d is een deler van a+b.
ReflectieWaarom moet d ook een deler zijn van a-b?
Opgave 2
Het getal d = 11 is deler van de getallen a = 187 en m = 341.
a) Zoek getallen v en w waarvoor geldt dat 187 = v * 11 en 341 = w * 11.
b) Laat zien dat a + m = (v + w)*11 en a - m = (v - w)*11.
Opgave 3
Als a=6885 en m=2574 dan ggd(a,m) = 9, Deze noemen we d.
a) Leg uit dat d|(a-2*m).
b) Leg uit dat m en (a-2*m) geen grotere deler dan d gemeenschappelijk kunnen hebben
en dat er dus geldt dat d=ggd(m,a-2*m).
Uit opgave 3 ontstaat het vermoeden dat:
Als d een deler is van a en een deler is van m, dan is d ook een deler van a+qm en a-qm
Als we er goed over nadenken dan is ook dat wel logisch, immers
d is een deler van a, dus er is een geheel getal v waarvoor geldt a=v*d.
d is een deler van m, dus er is een geheel getal w waarvoor geldt m=w*d.
We kunnen a+qm dus schrijven als a+qm=v*d+qw*d=(v+qw)*d.
v+qw is een geheel getal, dus d is een deler van a+qm.
Reflectie
Waarom is d ook een deler van a-qm?
klik hier
12.3 De grootste gemene deler
Opgave 4
Gegeven de getallen a, m en d = ggd(a , m),
Het getal q is een geheel getal.
We weten nu dat d|(a - q * m).
Leg uit dat m en (a - q * m) geen grotere deler dan d gemeenschappelijk kunnen hebben en dat er dus geldt dat
d = ggd(m ,a - q * m).
We hebben nu gezien dat we de grootste gemene deler van een paar getallen kunnen vinden, zonder eerst alle delers op te moeten schrijven. We trekken telkens het kleinste getal een aantal keer van het grootste getal af. Zoiets deden we eerder in opgave 2 van les 10. Omdat we graag met zo klein mogelijke getallen rekenen, berekenen we liever de ggd van a - m en m dan van a en m. Het beste kunnen we het kleinste getal zo vaak mogelijk van het grootste getal aftrekken, maar wel zo dat de uitkomst positief blijft.
Voorbeeld:
Bereken de ggd(252, 198)
Berkening: 252 - 198 = 54, dus ggd(252, 198) = ggd(198, 54)
198 - 3 * 54 = 36, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36)
54 - 36 = 18, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36) = ggd(36, 18)
36 - 2 * 18 = 0, dus ggd(252, 198) = ggd(198, 54) = ggd(54, 36) = ggd(36, 18) = ggd(18, 0) = 18.
Merk op dat weer geldt als ieder getal een deler is van 0, behalve 0 zelf. Zie opgave 2 op de sub-pagina Grootste Gemene Delers.
Opgave 5
Bereken op bovenstaande manier:
a) ggd(6466,5429)
b) ggd(5346,897)
c) ggd(47,0)
In het voorbeeld boven opgave 5 zagen we, dat als we de ggd(252,198) willen bereken we 252reduceren door het getal 198 daar zovaak als mogelijk is van af te trekken (in dit geval één keer) zodat het resultaat nog net positief is. Bij de berekening maken we intuïtief gebruik van de geheeltallige deling en de REST-functie, of modulo-berekening.
We geven nu een paar formele definities. Op de sub-pagina (a div m) en (a mod m) worden deze verder toegelicht en kun je het modulo-rekenen oefenen met een paar opgaven.
Definitie a div b:
Voor gehele getallen a en positieve gehele getallen m is a div m het grootste gehele getal k dat voldoet aan k*m 
a.
Voorbeeld: 17 div 5 = 3 en -17 div 5 =-4
Definitie a mod m:
Voor gehele getallen a en positieve gehele getallen m is a mod m = a - m*(a div m),
Samengevat:
Voor gehele getallen a en positieve gehele getallen m geldt
(1) a = m*(a div m) + (a mod m)
(2) 0 a mod m < m.
Als je met het bovenstaande geen moeite hebt kun je rustig verder.
Zo niet kijk dan eerst naar de voorbeelden en verdere uitleg onder het kopje 12.3A (a div m) en (a mod m)
Opgave 6
Gegeven zijn de positieve gehele getallen a=2164, m=153 en q=2164 div 153,
met a > m dan is q het grootste getal waarvoor geldt dat a-q
*m
0.
Er geldt dus 2164-2164
*153=2164(mod 153).
a) Leg uit dat ggd(2164,153)=ggd(153,2164(mod 153)).
b) Onderzoek of ggd(153,2164)=ggd(2164,153(mod 2164)).
Opgave 7
Gegeven zijn de positieve gehele getallen a, m en q=a div m, met a>m en q is het grootste getal is waarvoor geldt dat a-q*m>=0.
Er geldt dus a-q*m=a(mod m).
a) Leg uit dat ggd(a,m)=ggd(m,a(modm)).
b) Onderzoek of ggd(m,a)=ggd(a,m(mod a)) ook geldt als
m>
a.
De methode om een grootste gemene deler snel te berekenen die we in de bovenstaande opgaven ontdekt hebben, heet het "Algoritme van Euclides".
12.3A (a div m) en (a mod m)
Inhoud van deze pagina
E.1 Breukdeling en gehele deling
E.2 De rest bij deling
E.3 Somregel en productregel
E.1 Breukdeling en gehele deling
In les 1 heb je het verschil gezien tussen coderen en versleutelen. Doordat we het omzetten van rijtjes symbolen naar getallen (coderen) en omgekeerd (decoderen) op een van tevoren afgesproken manier gaan doen, kunnen we ons bij het beschrijven van de cryptosystemen beperken tot het werken met getallen. In de systemen die we in les 1 hebben bekeken, hadden we maar 26 symbolen en daarmee hadden we aan de getallen 0 tot en met 25 genoeg. De bewerkingen die we met deze getallen hebben uitgevoerd lieten zich eenvoudig informeel beschrijven. Nu we de beschikking hebben over meer symbolen en we ook nog gaan werken met rijtjes symbolen, krijgen we te maken met veel grotere getallen. En omdat we ons niet vast willen leggen op welke getallen er in onze boodschappen voor zullen komen, is het nodig wat gestructureerder naar de bewerkingen met gehele getallen te kijken.
Bij affiene cryptografie in les 2 was het nodig om bij elke uitkomst van een berekening te bepalen wat de rest bij deling door 26 was. Op die manier bestond zowel de onbewerkte als de versleutelde boodschap uit een rij van getallen uit de verzameling
0, 1, 2, 3, ..., 25. In deze subpagina wordt dat idee uitgebreid.
Hoeveel pootjes van 25 cm kun je zagen uit een balk van 240 cm? Het antwoord dat de rekenmachine geeft bij de deling 240:25 is in dit geval onzin: als je pootjes van 25 cm nodig hebt, dan heb je niets aan het laatste stukje dat toch te klein is. Als k het (grootste) aantal pootjes van 25 cm is dat we uit de balk van 240 cm kunnen zagen, dan is k het grootste gehele getal dat voldoet aan 25*k =240. In dit geval is dat dus 9.
Om onderscheid te maken tussen de 'breukdeling' en de 'geheeltallige deling' noteren we
de gehele deling als 240 div 5 (= 9)
en de breukdeling als 240:25 (= 9,6).
Voor positieve gehele getallen a en m verstaan we onder a div m dus het geheel aantal keren dat m in a past.
Voor negatieve gehele getallen a is het wat lastiger in te zien wat a div m zou moeten zijn. Bij de positieve gehele a zochten we de grootste gehele k die voldeed aan k*m = a. We spreken af dat we dat voor negatieve gehele a net zo doen.
Wanneer we (-240)div25 berekenen, komt daar dus -10 uit, want -10*25=-250 en dat is kleiner dan -240. De uitkomst -9 is niet goed, want -9*25=-225 en dat is meer dan -240.
Formeel kunnen we de operator div dus als volgt vastleggen:
|
Voor gehele getallen a en positieve gehele getallen m is a div m het grootste gehele getal k dat voldoet aan k*m = a.
|
Opgave 1
Bereken:
a) 17 div 5.
b) 944 div 13.
c) 91 div 7.
d) (-22) div 7.
E.2 De rest bij deling
Zoals je bij het zagen van pootjes uit een balk in het algemeen iets overhoudt, blijft er bij geheeltallige deling in het algemeen een rest over. Bij deling van 25 door 7 is het resultaat 3. Maar 3*7 maakt de 25 niet vol. Er blijft als rest over: 25-3*7=25-21=4. Deze rest noteren we als 25 mod 7.
We spreken dit uit als: "25 modulo 7". De rest van een geheel getal bepalen na deling door m, noemen we a reduceren modulo m.
In het algemeen is voor gehele getallen a en positieve gehele getallen m het getal amodm de rest bij geheeltallige deling van a door m. Formeel:
|
Voor gehele getallen a en positieve gehele getallen m is
a mod m = a-m*(adivm) de rest bij geheeltallige deling van a door m
|
Opgave 2
Bereken:
a) 17 mod 5.
b) 944 mod 13.
c) 91 mod 7.
d) (-22) mod 7.
De operatoren div en mod voldoen aan de volgende eigenschappen:
|
Voor gehele getallen a en positieve gehele getallen m geldt
(1) a = m*(a div m)+(a mod m)
(2) 0 ≤ a mod m < m
|
Opgave 3
a) Controleer deze eigenschappen voor a = 17 en m = 5.
b) Controleer deze eigenschappen voor a = -22 en m =7.
c) Leg uit hoe deze twee eigenschappen volgen uit de definities van div en mod.
Als we berekeningen modulo een bepaald getal moeten uitvoeren, kunnen we gebruik maken van een aantal rekenregels. We zullen deze regels hier aan de hand van voorbeelden aannemelijk maken, maar ze niet bewijzen. In hoofdstuk 6 kom je precies te weten waarom de rekenregels kloppen.
Opgave 4
We hebben een balk van 240 cm en een balk van 190 cm en we gaan daar zo veel mogelijk pootjes van 25 cm afzagen.
a) Hoeveel cm houden we bij elke balk over?
b) Het is niet verrassend dat we dezelfde lengte overhouden. Waarom niet?
We zagen in deze opgave dat het verschil van twee getallen een veelvoud is van m als de twee getallen dezelfde rest hebben na deling door m. Dit resulteert in de volgende regel:
|
Voor gehele getallen a en b en positieve gehele getallen m geldt:
a(modm) =b(modm) precies dan als (a-b) modm= 0.
|
Opgave 5
a) Controleer deze eigenschap voor a=17, b=32 en m=5.
b) Laat zien dat het drietal a=22, b=35 en m=11 niet voldoet.
c) Geef een m zodanig dat het drietal a=22, b=35 en m wel voldoet.
Opgave 6
We hebben een balk van 240 cm en een balk van 155 cm. We plakken de balken aan elkaar en zagen hier pootjes van 25 cm van.
a) Hoe lang is het stukje balk dat we uiteindelijk overhouden?
We doen hetzelfde nog een keer, maar nu met een balk van 190 cm en een balk van 305 cm.
b) Hoe lang is nu het stukje balk dat we uiteindelijk overhouden?
c) Leg uit waarom de uitkomsten bij a) en b) hetzelfde zijn.
Opgave 7
We nemen 7 balken van 240 cm en zagen er pootjes van 25 cm van. Vervolgens plakken we alle restanten aan elkaar en zagen daar ook weer pootjes van 25 cm van.
a)Hoe lang is het stukje balk dat we uiteindelijk overhouden?
We doen hetzelfde met 7 balken van 190 cm.
b) Hoe bereken je makkelijk hoe lang het stukje is dat we uiteindelijk overhouden?
Weer hetzelfde, dit keer met 32 balken van 240 cm.
c) Hoe bereken je nu makkelijk hoe lang het stukje is dat we uiteindelijk overhouden?
d) Waarom doen die 25 balken extra er niet toe?
E.3 Somregel en productregel
In opgave 5 en 6 hebben we een idee gekregen hoe het optellen en vermenigvuldigen bij modulo-rekenen werkt. Inderdaad blijkt er een somregel en een productregel voor het modulo-rekenen te zijn:
|
Voor gehele getallen a, b, c en d en positieve gehele getallen m geldt:
als a(modm)=b(modm) en c(modm)=d(modm) dan
Somregel: (a+c) modm=(b+d) modm
Productregel: (a*c) modm=(b*d) modm
|
Opgave 8
Bereken de volgende uitdrukkingen. Doe dit zonder je rekenmachine te gebruiken en geef steeds aan welke rekenregel je gebruikt.
a) (123+456)mod10.
b) (113*222)mod10.
c) 17*(355+773)mod7.
Als we met de getallen 0 tot en met 25, de rangnummers van de 26 letters in het alfabet rekenen dan brengen we bij de rekenkundige bewerkingen (optellen en vermenigvuldigen) eigenlijk met behulp van modulo-rekenen het resultaat terug tot een getal in dit domein, ook al noemden we dat niet zo. De verzameling getallen {0,1,...m-1} duiden we aan met Zm.
Wanneer het duidelijk is dat we in Zm rekenen, en dus modulo m rekenen, laten we het "mod(m)" soms weg.
Voorbeeld:
Bereken 7*5 in Zm.
Berekening (7*5)mod12 = 35mod12 = 11 of 7*5 = 11.
Opgave 9
Waarom kun je de berekening in bovenstaand voorbeeld niet opschrijven als 7*5 = 35 = 11?
Opgave 10
Vul onderstaande tabellen in Z5 verder in.
| + |
0 |
1 |
2 |
3 |
4 |
|
* |
0 |
1 |
2 |
3 |
4 |
|
| 0 |
0 |
1 |
2 |
|
|
|
0 |
0 |
0 |
0 |
|
|
|
| 1 |
1 |
2 |
|
|
|
|
1 |
0 |
1 |
|
|
|
|
| 2 |
2 |
|
|
|
|
|
2 |
0 |
|
|
|
|
|
| 3 |
|
|
|
|
|
|
3 |
|
|
|
|
|
|
| 4 |
|
|
|
|
|
|
4 |
|
|
|
|
|
|
Opgave 11
Los de volgende vergelijkingen op:
a) In Z5: 3+x = 1
b) In Z8: 3+x = 1
c) In Z19: 14+x = 5
d) In Z19: 11+x = 0
Het oplossen van vergelijkingen van het type zoals in de vorige opgave zal niet zoveel problemen geven. Ook zonder dat je de hele opteltabel hebt uitgeschreven lukt het wel 14 +x = 5 op te lossen in Z19. In Z19 betekent 14 +x= 5 eigenlijk (14 +x) mod19 = 5 en dat wil zeggen dat je rest 5 overhoudt als je 14 +x door 19 deelt. Er is dus een k zodanig dat 14 + x - 19*k = 5, ofwel 9 +x= 19*k. Voor k=0 levert dit geen getal uit Z19; voor k=1 levert dit 9+x=19, dus x=10.
De berekening verloopt dus als volgt:
14+x = 5 in Z19
(14+x)mod19 = 5
14+x-19*k = 5
9+x = 19k, dus x = 10 en k =1
Misschien heb je het bij de opgave op een manier gedaan die je makkelijker vindt, maar bekijk ook de manier van redeneren hierboven goed.
Opgave 12
Los de volgende vergelijkingen op bovenstaande manier op:
a) In Z23: 16+x = 7
b) In Z1278: 756+x = 341
Je ziet dat een vergelijking met een optelling oplossen niet zo moeilijk is. Wanneer er een vermenigvuldiging in de vergelijking zit, is een oplossing vinden minder eenvoudig. Een van de problemen is het volgende.
Als je niet modulo-rekent, kun je concluderen dat als ac = bc, dat dan daaruit a = b volgt.
Bij modulo-rekenen geldt niet altijd dat als
a*c≡mb*c,dat dan a≡mb. (≡m staat voor "gelijkwaardig in Zm")
Opgave 13
a) Ga dit na voor a = 12, b = 7, c = 6 en m = 10.
b) Leg uit waarom het in dit voorbeeld niet geldt.
c) Wat voor een getal moet m zijn om wel te laten gelden dat a ≡ mb als a*c ≡mb*c?
Afgezien daarvan is het ook lastig omdat je niet eenvoudig links en rechts door hetzelfde getal kunt delen.
Ga nu verder met les 12.3 opgave 6
12.4 Algoritme van Euclides
Voor a > 0 en a een geheel getal is ggd(a,0)=a en als m geheel,
dan geldt ggd(a,m)=ggd(m,a(mod m)).
Voorbeeld:
Bereken ggd(99, 45) met behulp van het algoritme van Euclides.
99 : 45 = 2 rest 9, want 99=2*45+9,
dus ggd(99, 45) = ggd(45, 9).
45 : 9 = 5 rest 0, want 45=5*9+0,
dus ggd(45, 9) = ggd(9,0) = 9 (want ggd(a, 0) = a).
Hieruit volgt dus ook ggd(99, 45) = 9.
Voor een berekening met kleine getallen kun je de berekening wel als hierboven opschrijven.
We zetten de tussenstappen in een tabel. We willen de 2 en de 9 uit de uitkomst 2 rest 9 graag in twee verschillende kolommen zetten. De 9 is de rest na deling. De rest geven we aan met de letter r. De 2 is het gehele deel van het quotiënt. Dit gehele deel geven we aan met de letter q.
| a |
m |
q |
r |
| 99 |
45 |
2 |
9 |
| 45 |
9 |
5 |
0 |
| 9 |
0 |
|
Op elke regel is de ggd(a,m) gelijk, dus ggd(99,45)=ggd(45,9)=ggd(9,0)=9.
Voor het begruik van grotere getallen wordt een tabel onontbeerlijk.
Voorbeeld:
Bereken ggd(148104,47223).
Herhaald het algoritme van Euclides toepassen levert:
| a |
m |
q |
r |
| 148104 |
47223 |
3 |
6435 |
| 47223 |
6435 |
7 |
2178 |
| 6435 |
2178 |
2 |
2079 |
| 2178 |
2079 |
1 |
99 |
| 2079 |
99 |
21 |
0 |
| 99 |
0 |
|
|
Opgave 8
a) Waar vind je de grootste gemene deler in de bovenstaande tabel?
b) Wat is dus ggd(148104,47223)?
Opgave 9
a) Bereken ggd(96, 22) met behulp van het algoritme van Euclides.
b) Bereken ggd(484, 576).
c) Bereken ggd(47957, 32395).
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.
