Voorbereiden toets deel 2: Cryptografie – Pagina 2

Les 6: Algoritme van Euclides

We hebben in deze les een algoritme geleerd dat je kunt gebruiken om de grootst gemene deler mee te berekenen. Hierbij maken we gebruik van de rekenregel $\text{ggd}(a,b)=\text{ggd}(a \text{ mod } b,b)$ . Bij het algoritme van Euclides gebruiken we dit om steeds het grootste getal te vervangen door een kleiner getal totdat we de ggd gemakkelijk kunnen aflezen. Hier staat het voorbeeld wat we in de les gedaan hebben:

$\text{ggd}(696,156)=\text{ggd}(696 \text{ mod } 156, 156) = \text{ggd}(72,156)$
$\text{ggd}(72, 156)=\text{ggd}(72, 156 \text{ mod }72) = \text{ggd}(72,12)$
$\text{ggd}(72, 12)=\text{ggd}(72 \text{ mod }12, 72) = \text{ggd}(0,12)=12$
Conclusie: $\text{ggd}(696,156)=12$

In les 6 hebben we het algoritme van Euclides gebruikt om $\text{ggd}(a,b)$ te schrijven in de vorm $\text{ggd}(a,b)=k\cdot a+m\cdot b$ . De truc hierbij is dat we gezien hebben dat $b \text{ mod } a = a - b//a \cdot a$ , waarbij $b//a$ staat voor $b$ gedeeld door $a$ naar beneden afgerond. Door dit trucje herhaald toe te passen, krijgen we uiteindelijk $\text{ggd}(a,b)=k\cdot a+m\cdot b$ . In de tabel hieronder zie je hoe dat werkt bij het voorbeeld van $\text{ggd}(656, 156)$ uit het bovenstaande voorbeeld.

Opdrachten

Vraag 7:
Noteer alle positieve delers van 210.

Uitwerking:

Een truc is om de kleine delers van 210 af te gaan. Bij iedere kleine deler $d$ hoort dan ook een grote deler $\frac{210}{d}$ . Dat geeft in dit geval de delers:
1 en 210
2 en 105
3 en 70
5 en 42
6 en 35
7 en 30
10 en 21
14 en 15

Vraag 8:
Bereken met het algoritme van Euclides de grootst gemene deler van 972 en 1012.

Uitwerking:

$\text{ggd}(972, 1012)=\text{ggd}(972, 1012\text{ mod } 1012) = \text{ggd}(972,40)$
$\text{ggd}(972, 40)=\text{ggd}(972 \text{ mod }40,40) = \text{ggd}(12,40)$
$\text{ggd}(12, 40)=\text{ggd}(12, 40 \text{ mod }12) = \text{ggd}(12,4)$
$\text{ggd}(12, 4)=\text{ggd}(12 \text{ mod }4,4) = \text{ggd}(0,4)=4$
Conclusie: $\text{ggd}(972,1012)=4$

Vraag 9:
Vind gehele waarden $a$ en $b$ , zodat $3 = 6123a+6174b$ .

Uitwerking:

$\text{ggd}(6123, 6174)=\text{ggd}(6123, 6174 \text{ mod } 6123)=\text{ggd}(6123,51)$ geeft $51=6174-6123$
$\text{ggd}(6123, 51)=\text{ggd}(6123 \text{ mod } 51,51)=\text{ggd}(3,51)$ geeft $3=6123 - 120\cdot 51 = 6123-120\cdot (6174-6123)=121\cdot 6123 -120\cdot 6174$ .
Conclusie: Het antwoord is $3=121\cdot 6123 - 120\cdot 6174$

Vraag 10:
Bereken met het uitgebreide algoritme van Euclides een geheel getal $a$ zodat $1017a\text { mod } 5087 = 1$ .

Uitwerking:

$\text{ggd}(1017, 5087)=\text{ggd}(1017, 5087 \text{ mod } 1017)=\text{ggd}(1017,2)$ geeft $2=5087-5\cdot 1017$ .
$\text{ggd}(1017, 2)=\text{ggd}(1017 \text{ mod } 2, 2)=\text{ggd}(1,2)$ geeft $1=1017 - 508\cdot 2 = 1017 - 508\cdot (5087-5\cdot 1017) = 1017-508\cdot 5087 +2540\cdot 1017 = 2541\cdot 1017-508\cdot 5087$ .
Modulo 5087 wordt dit $2541\cdot 1017 \text{ mod } = 1$ .

Vraag 11:
Je mag gehele getallen (ook negatief!) $a$ en $b$ vrij kiezen en berekent dan $d=50a+35b$ . Wat is het kleinste positieve getal $d$ dat je kunt krijgen?

Uitwerking:

De grootst gemene deler van 50 en 35 is 5. Daardoor komt er altijd een veelvoud van 5 uit $50a+35b$ . Een kleiner getal dan 5 is dus niet mogelijk. We kunnen wel 5 krijgen met behulp van het algoritme van Euclides:
$\text{ggd}(50,35)=\text{ggd}(50\text{ mod } 35, 35)=\text{ggd}(15,35)$ geeft $15=50-35$
$\text{ggd}(15,35)=\text{ggd}(35, 35\text{ mod } 15)=\text{ggd}(35,5)$ geeft $5=35-2\cdot 15=35 - 2\cdot (50-35)=-2\cdot 50+3\cdot 35$ , zoals gevraagd.

Vraag 12:
Vind de decryptiefunctie die hoort bij $E(x)=(7x+3)\text{ mod }26$ .

Uitwerking:

We moeten een getal $a$ vinden zodat $7\cdot a \text{ mod } 26$ . Dat kan met het algoritme van Euclides, zoals in vraag 10:
$\text{ggd}(7,26)=\text{ggd}(7, 26\text{ mod } 7)=\text{ggd}(7,5)$ geeft $5=26-3\cdot 7$
$\text{ggd}(7,5)=\text{ggd}(2,5)$ geeft $2=7-5=7-(26-3\cdot 7)=4\cdot 7-26$
$\text{ggd}(2,5)=\text{ggd}(\text{2,5\text{ mod } 2)=\text{ggd}(2,1}$ geeft $1=5-2\cdot 2=26-3\cdot 7 - 2(4\cdot 7-26) = 3\cdot 26-11\cdot 7$
Modulo 26 geeft dit $-11\cdot 7 \text{ mod } 26 = 1$ .
Dit betekent dat de decryptiefunctie $D(x)=-11(x-3)\text{ mod } 26$ werkt. Immers, we moeten eerst de plus 3 ongedaan maken door min 3 te doen en daarna keer 7 ongedaan maken wat schijnbaar kan door keer -11 te doen.

NB: In plaats van -11 kun je ook $-11+26=15$ pakken als je met positieve getallen wilt werken.

Vraag 13:
Als we ASCII gebruiken zijn er 256 tekens. Je zou dan de encryptiefunctie $E(x)=117x+59\text{ mod }256$ kunnen gebruiken. Vind de decryptiefunctie die hierbij hoort.

Uitwerking:

We gebruiken hetzelfde stappenplan als in vraag 12:
$\text{ggd}(117, 256)=\text{ggd}(117, 256\text{ mod } 117)=\text{ggd}(117,22)$ geeft $22=256-2\cdot 117$ .
$\text{ggd}(117, 22)=\text{ggd}(117\text{ mod } 22, 22)=\text{ggd}(7,22)$ geeft $7=117-5\cdot 22 = 117-5(256-2\cdot 117)=11\cdot 117-5\cdot 256$ .
$\text{ggd}(7, 22)=\text{ggd}(7, 22\text{ mod } 7)=\text{ggd}(7,1)$ geeft $1=22-3\cdot 7 = 256-2\cdot 117-3(11\cdot 117-5\cdot 256)=16\cdot 256-35\cdot 117$ .
Modulo 256 staat hier $-35\cdot 117 \text{ mod } 256 = 1$
Op dezelfde manier als in opdracht 12 kunnen we nu dus de decryptiefunctie opstellen met $D(x)=-35(x-59)\text{ mod } 256$ .

Vraag 14:
Bereken hoeveel positieve gehele getallen $n$ er tot en met 1000 zijn waarvoor geldt dat $\text{ggd}(n,1000)=1$ .

Uitwerking:

Het zijn alle getallen die geen veelvoud zijn van 2 of van 5.
Er zijn $500$ even getallen tot en met 1000 en $200$ veelvouden van 5. De hebben we echter alle veelvouden van 10 zowel geteld bij de even getallen als bij de veelvouden van 5. Er zijn $100$ veelvouden van 10 tot en met 1000 die we dubbel geteld hebben. Er zijn dus in totaal $500+200-100=600$ getallen tot en met 1000 die een veelvoud zijn van 2 en/of 5.
Het aantal getallen $n$ tot en met 1000 met $\text{ggd}(n,1000)=1$ is dus $1000-600 = 400$ .

Pagina's: 1234567