Um längere Rechnungen zu vermeiden, rechnen wir:

(403 - 1608) mod 8 ≡ (403 mod 8 - 1608 mod 8) mod 8.

403 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 403 = 400+3 = 8 ⋅ 50 +3.

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

Somit gilt:

(403 - 1608) mod 8 ≡ (3 - 0) mod 8 ≡ 3 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 71) mod 6 ≡ (28 mod 6 ⋅ 71 mod 6) mod 6.

28 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 28 = 24 + 4 = 4 ⋅ 6 + 4 ist.

71 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 71 = 66 + 5 = 11 ⋅ 6 + 5 ist.

Somit gilt:

(28 ⋅ 71) mod 6 ≡ (4 ⋅ 5) mod 6 ≡ 20 mod 6 ≡ 2 mod 6.

Die 128 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: 733¹=733

2: 733²=733¹⁺¹=733¹⋅733¹ ≡ 733⋅733=537289 ≡ 571 mod 983

4: 733⁴=733²⁺²=733²⋅733² ≡ 571⋅571=326041 ≡ 668 mod 983

8: 733⁸=733⁴⁺⁴=733⁴⋅733⁴ ≡ 668⋅668=446224 ≡ 925 mod 983

16: 733¹⁶=733⁸⁺⁸=733⁸⋅733⁸ ≡ 925⋅925=855625 ≡ 415 mod 983

32: 733³²=733¹⁶⁺¹⁶=733¹⁶⋅733¹⁶ ≡ 415⋅415=172225 ≡ 200 mod 983

64: 733⁶⁴=733³²⁺³²=733³²⋅733³² ≡ 200⋅200=40000 ≡ 680 mod 983

128: 733¹²⁸=733⁶⁴⁺⁶⁴=733⁶⁴⋅733⁶⁴ ≡ 680⋅680=462400 ≡ 390 mod 983

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

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

153 = 128+16+8+1

194¹⁵³

= 194^128+16+8+1

= 194¹²⁸⋅194¹⁶⋅194⁸⋅194¹

≡ 102 ⋅ 74 ⋅ 272 ⋅ 194 mod 389
≡ 7548 ⋅ 272 ⋅ 194 mod 389 ≡ 157 ⋅ 272 ⋅ 194 mod 389
≡ 42704 ⋅ 194 mod 389 ≡ 303 ⋅ 194 mod 389
≡ 58782 mod 389 ≡ 43 mod 389

Es gilt also: 194¹⁵³ ≡ 43 mod 389

Berechnung des größten gemeinsamen Teilers von 73 und 59

=>73	= 1⋅59 + 14
=>59	= 4⋅14 + 3
=>14	= 4⋅3 + 2
=>3	= 1⋅2 + 1
=>2	= 2⋅1 + 0

also gilt: ggt(73,59)=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= 3-1⋅2
2= 14-4⋅3	eingesetzt in die Zeile drüber:	1	= 1⋅3 -1⋅(14 -4⋅ 3) = 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14	eingesetzt in die Zeile drüber:	1	= -1⋅14 +5⋅(59 -4⋅ 14) = -1⋅14 +5⋅59 -20⋅ 14) = 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59	eingesetzt in die Zeile drüber:	1	= 5⋅59 -21⋅(73 -1⋅ 59) = 5⋅59 -21⋅73 +21⋅ 59) = -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73