[Wi] (pws) modulair rekenen

[Hanneke]

Ik doe m'n profielwerkstuk over RSA (cryptografie met priemgetallen) en nu is punt 3:
Bereken e zo dat d * e mod (p-1)*(q-1) = 1 (d, p en q zijn bekend).
Nou is dit (met kleine getallen) nog wel door uit te proberen te vinden. Maar hoe zou je dit kunnen uit rekenen?

De voorbeeldgetallen heb ik even boven liggen, maar zet ik morgen wel neer.
Hier staat trouwens hoe d, p en q gekozen zijn en meer over RSA.

[WelVrolijk]

Dat kan gewoon met het uitgebreide algoritme van Euclides.

Dus:
- Bepaal de ggd van d en (p-1)(q-1) en houd precies bij wat je doet.
- Je zult uitkomen op 1 (want beide getallen zijn relatief priem.
- Onderaan staat nu een of andere vergelijking die als uitkomst 1 heeft.
- Door nu steeds "de vergelijking erboven" in te vullen in de vergelijking die je al had (en dan de haakjes weg te werken) kom je dan uiteindelijk uit op een vergelijking van de vorm n.d + m.(p-1)(q-1) = 1.
Met andere woorden: n.d = 1 mod (p-1)(q-1).
Dus die n is (een voorbeeld van) de gezochte e.

-----

Voorbeeldje voor het uitgebreid algoritme van Euclides:
Ik wil de ggd van 15 en 11 schrijven als lineaire combinatie van 15 en 11.

15 - 11 = 4
11 - 2.4 = 3
4 - 3 = 1
Dus 1 is de ggd van 11 en 15

Ik begin met de onderste regel
1 = 1.4 - 1.3
Nu heb ik 1 geschreven als lineaire combinatie van 3 en 4.
Ik vul in dat 11 - 2.4 = 3
1 = 1.4 - (11 - 2.4) = 3.4 - 1.11
Nu heb ik 1 geschreven als lineaire combinatie van 4 en 11.
Ik vul in dat 15 - 11 = 4
1 = 3.(15-11) - 1.11 = 3.15 - 4.11
Nu heb ik 1 geschreven als lineaire combinatie van 11 en 15.
Klaar.

Nu weet ik dus meteen dat 3.15 = 1 mod 11.
Ook weet ik dat (-4).11 = 1 mod 15, en dus ook dat 11.11 = 1 mod 15 (immers, -4 + 15 = 11)

Sorry, die laatste regel komt waarschijnlijk een beetje uit de lucht vallen.


We weten:
(-4).11 + 3.15 = 1.
Dus:
1 = (-4).11 + 3.15 =
= (-4).11 + 15.11 - 11.15 + 3.15 =
= (-4+15).11 + (-11+3).15 =
= 11.11 - 8.15
Dus 11.11 = 1 + 8.15,
dus 11.11 = 1 mod 15.