| p | q | n | (p-1)(q-1) | e gewählt |
| 47 | 59 | | | 17 |
Euklidischer Algorithmus zur Bestimmung des ggT (2668,17)
2668 : 17 =
Rest
denn >> 16 =
-
*17
:
=
Rest
denn >> 1 =
-
*16
:
=
Rest
ggT(2668,17)=1 -> Nachweis 2668 und 17 sind teilerfremd
Erweiterter Euklidischer Algorithmus
1 =
-
17 - (
) Einsetzen 16=2668-156*17
17 -
+
*17
*17 - 1*2668
Der Faktor vor e ist das modulare Inverse zu e.
ist das modulare Inverse zu 17