Um längere Rechnungen zu vermeiden, rechnen wir:

(1606 - 320) mod 8 ≡ (1606 mod 8 - 320 mod 8) mod 8.

1606 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 1606 = 1600+6 = 8 ⋅ 200 +6.

320 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 320 = 320+0 = 8 ⋅ 40 +0.

Somit gilt:

(1606 - 320) mod 8 ≡ (6 - 0) mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(87 ⋅ 37) mod 7 ≡ (87 mod 7 ⋅ 37 mod 7) mod 7.

87 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 87 = 84 + 3 = 12 ⋅ 7 + 3 ist.

37 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 37 = 35 + 2 = 5 ⋅ 7 + 2 ist.

Somit gilt:

(87 ⋅ 37) mod 7 ≡ (3 ⋅ 2) mod 7 ≡ 6 mod 7.

Die 64 im Exponent ist ja ein reine 2er-Potenz (2⁶).

Deswegen quadrieren wir einfach mit jedem Schritt das Ergebnis und kommen so immer eine 2er-Potenz im Exponenten höher:

1: 558¹=558

2: 558²=558¹⁺¹=558¹⋅558¹ ≡ 558⋅558=311364 ≡ 19 mod 853

4: 558⁴=558²⁺²=558²⋅558² ≡ 19⋅19=361 ≡ 361 mod 853

8: 558⁸=558⁴⁺⁴=558⁴⋅558⁴ ≡ 361⋅361=130321 ≡ 665 mod 853

16: 558¹⁶=558⁸⁺⁸=558⁸⋅558⁸ ≡ 665⋅665=442225 ≡ 371 mod 853

32: 558³²=558¹⁶⁺¹⁶=558¹⁶⋅558¹⁶ ≡ 371⋅371=137641 ≡ 308 mod 853

64: 558⁶⁴=558³²⁺³²=558³²⋅558³² ≡ 308⋅308=94864 ≡ 181 mod 853

Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 122 (grauer Kasten).

Dann schauen wir die Binärdarstellung von 122 an und zerlegen 122 in eine Summer von 2er-Potenzen:

122 = 64+32+16+8+2

553¹²²

= 553^64+32+16+8+2

= 553⁶⁴⋅553³²⋅553¹⁶⋅553⁸⋅553²

≡ 111 ⋅ 298 ⋅ 691 ⋅ 66 ⋅ 148 mod 733
≡ 33078 ⋅ 691 ⋅ 66 ⋅ 148 mod 733 ≡ 93 ⋅ 691 ⋅ 66 ⋅ 148 mod 733
≡ 64263 ⋅ 66 ⋅ 148 mod 733 ≡ 492 ⋅ 66 ⋅ 148 mod 733
≡ 32472 ⋅ 148 mod 733 ≡ 220 ⋅ 148 mod 733
≡ 32560 mod 733 ≡ 308 mod 733

Es gilt also: 553¹²² ≡ 308 mod 733

Berechnung des größten gemeinsamen Teilers von 97 und 30

=>97	= 3⋅30 + 7
=>30	= 4⋅7 + 2
=>7	= 3⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(97,30)=1

Jetzt formen wir jede Zeile von unten nach oben um indem wir das Prokukt auf die andere Seite bringen.
Wir starten mit der zweitletzten Zeile:

1= 7-3⋅2
2= 30-4⋅7	eingesetzt in die Zeile drüber:	1	= 1⋅7 -3⋅(30 -4⋅ 7) = 1⋅7 -3⋅30 +12⋅ 7) = -3⋅30 +13⋅ 7 (=1)
7= 97-3⋅30	eingesetzt in die Zeile drüber:	1	= -3⋅30 +13⋅(97 -3⋅ 30) = -3⋅30 +13⋅97 -39⋅ 30) = 13⋅97 -42⋅ 30 (=1)

Es gilt also: ggt(97,30)=1 = 13⋅97 -42⋅30

oder wenn man 13⋅97 auf die linke Seite bringt:

1 -13⋅97 = -42⋅30

-42⋅30 = -13⋅97 + 1 |+97⋅30

-42⋅30 + 97⋅30 = -13⋅97 + 97⋅30 + 1

(-42 + 97) ⋅ 30 = (-13 + 30) ⋅ 97 + 1

55⋅30 = 17⋅97 + 1

Es gilt also: 55⋅30 = 17⋅97 +1

Somit 55⋅30 = 1 mod 97

55 ist also das Inverse von 30 mod 97