Um längere Rechnungen zu vermeiden, rechnen wir:

(247 - 78) mod 8 ≡ (247 mod 8 - 78 mod 8) mod 8.

247 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 247 = 240+7 = 8 ⋅ 30 +7.

78 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 78 = 80-2 = 8 ⋅ 10 -2 = 8 ⋅ 10 - 8 + 6.

Somit gilt:

(247 - 78) mod 8 ≡ (7 - 6) mod 8 ≡ 1 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 57) mod 11 ≡ (70 mod 11 ⋅ 57 mod 11) mod 11.

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

57 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 57 = 55 + 2 = 5 ⋅ 11 + 2 ist.

Somit gilt:

(70 ⋅ 57) mod 11 ≡ (4 ⋅ 2) mod 11 ≡ 8 mod 11.

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: 246¹=246

2: 246²=246¹⁺¹=246¹⋅246¹ ≡ 246⋅246=60516 ≡ 713 mod 757

4: 246⁴=246²⁺²=246²⋅246² ≡ 713⋅713=508369 ≡ 422 mod 757

8: 246⁸=246⁴⁺⁴=246⁴⋅246⁴ ≡ 422⋅422=178084 ≡ 189 mod 757

16: 246¹⁶=246⁸⁺⁸=246⁸⋅246⁸ ≡ 189⋅189=35721 ≡ 142 mod 757

32: 246³²=246¹⁶⁺¹⁶=246¹⁶⋅246¹⁶ ≡ 142⋅142=20164 ≡ 482 mod 757

64: 246⁶⁴=246³²⁺³²=246³²⋅246³² ≡ 482⋅482=232324 ≡ 682 mod 757

128: 246¹²⁸=246⁶⁴⁺⁶⁴=246⁶⁴⋅246⁶⁴ ≡ 682⋅682=465124 ≡ 326 mod 757

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

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

105 = 64+32+8+1

246¹⁰⁵

= 246^64+32+8+1

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

≡ 395 ⋅ 384 ⋅ 156 ⋅ 246 mod 739
≡ 151680 ⋅ 156 ⋅ 246 mod 739 ≡ 185 ⋅ 156 ⋅ 246 mod 739
≡ 28860 ⋅ 246 mod 739 ≡ 39 ⋅ 246 mod 739
≡ 9594 mod 739 ≡ 726 mod 739

Es gilt also: 246¹⁰⁵ ≡ 726 mod 739

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

=>97	= 1⋅54 + 43
=>54	= 1⋅43 + 11
=>43	= 3⋅11 + 10
=>11	= 1⋅10 + 1
=>10	= 10⋅1 + 0

also gilt: ggt(97,54)=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= 11-1⋅10
10= 43-3⋅11	eingesetzt in die Zeile drüber:	1	= 1⋅11 -1⋅(43 -3⋅ 11) = 1⋅11 -1⋅43 +3⋅ 11) = -1⋅43 +4⋅ 11 (=1)
11= 54-1⋅43	eingesetzt in die Zeile drüber:	1	= -1⋅43 +4⋅(54 -1⋅ 43) = -1⋅43 +4⋅54 -4⋅ 43) = 4⋅54 -5⋅ 43 (=1)
43= 97-1⋅54	eingesetzt in die Zeile drüber:	1	= 4⋅54 -5⋅(97 -1⋅ 54) = 4⋅54 -5⋅97 +5⋅ 54) = -5⋅97 +9⋅ 54 (=1)

Es gilt also: ggt(97,54)=1 = -5⋅97 +9⋅54

oder wenn man -5⋅97 auf die linke Seite bringt:

1 +5⋅97 = +9⋅54

Es gilt also: 9⋅54 = 5⋅97 +1

Somit 9⋅54 = 1 mod 97

9 ist also das Inverse von 54 mod 97