Beste,
Ik hoop dat iemand me kan helpen bij het leren begrijpen van het uitgebreide algoritme van Euclides (ten behoeve van het bepalen van de multiplicatieve inverse van een modulaire waarde).
Bijvoorbeeld:
Bereken de (multiplicatieve) inverse van 13 mod 271.
Dus bereken de waarde 13-1 waarvoor geldt dat 13 x 13-1 º 1 (mod 271)
Ik heb al veel gelezen, gezocht en geprobeerd maar ik kom er maar niet in uit.
Een ander voorbeeld:
Bereken de (multiplicatieve) inverse van 8 mod 3313.
Dus, bereken de waarde 8-1 waarvoor geldt dat 8 x 8-1 º 1 (mod 3313)
Alvast heel erg bedankt!Tommy
9-4-2014
Gebruik het algoritme van Euclides om $\mathrm{ggd}(13,271)$ en $\mathrm{ggd}(8,3313)$ te bepalen; dat algoritme levert, in beide gevallen, ook twee gehele getallen $a$ en $b$ zó dat de ggd gelijk is aan respectievelijk $13a+271b$ en $8a+3313b$.
Beide ggd's zijn gelijk aan $1$ en je vindt
$$
1=(-125)\cdot13 + 6\cdot 271
$$
en ook
$$
1=(-414)\cdot8+1\cdot3313
$$
Daar staan de multiplicatieve inversen.
kphart
9-4-2014
#72674 - Cryptografie - Student hbo