| p | q | n | (p-1)(q-1) | e gewählt |
| 47 | 59 | | | 59 |
Euklidischer Algorithmus zur Bestimmung des ggT (2668, 59)
:
=
Rest
denn >> 13 =
-
*59
59 :
=
Rest
denn >> 7 =
-
*13
13 :
= 1 Rest
denn >> 6 =
- 1*
7 :
= 1 Rest
denn >> 1 =
- 6
Erweiterter Euklidischer Algorithmus
1 = 7 - (
) =
*7 - 13
2* (
) - 13 = 2*59 -
- 13 = 2*59 -
2*59 - 9*(
) = 2*59 -
*2668 +
*59
*59 - 9*2668
ist das modulare Inverse zu