Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(321 - 403) mod 8 ≡ (1 - 3) mod 8 ≡ -2 mod 8 ≡ 6 mod 8.

Um längere Rechnungen zu vermeiden, rechnen wir:

(67 ⋅ 23) mod 6 ≡ (67 mod 6 ⋅ 23 mod 6) mod 6.

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

23 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 23 = 18 + 5 = 3 ⋅ 6 + 5 ist.

Somit gilt:

(67 ⋅ 23) mod 6 ≡ (1 ⋅ 5) mod 6 ≡ 5 mod 6.

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

2: 201²=201¹⁺¹=201¹⋅201¹ ≡ 201⋅201=40401 ≡ 159 mod 353

4: 201⁴=201²⁺²=201²⋅201² ≡ 159⋅159=25281 ≡ 218 mod 353

8: 201⁸=201⁴⁺⁴=201⁴⋅201⁴ ≡ 218⋅218=47524 ≡ 222 mod 353

16: 201¹⁶=201⁸⁺⁸=201⁸⋅201⁸ ≡ 222⋅222=49284 ≡ 217 mod 353

32: 201³²=201¹⁶⁺¹⁶=201¹⁶⋅201¹⁶ ≡ 217⋅217=47089 ≡ 140 mod 353

64: 201⁶⁴=201³²⁺³²=201³²⋅201³² ≡ 140⋅140=19600 ≡ 185 mod 353

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

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

205 = 128+64+8+4+1

343²⁰⁵

= 343^128+64+8+4+1

= 343¹²⁸⋅343⁶⁴⋅343⁸⋅343⁴⋅343¹

≡ 76 ⋅ 398 ⋅ 543 ⋅ 556 ⋅ 343 mod 733
≡ 30248 ⋅ 543 ⋅ 556 ⋅ 343 mod 733 ≡ 195 ⋅ 543 ⋅ 556 ⋅ 343 mod 733
≡ 105885 ⋅ 556 ⋅ 343 mod 733 ≡ 333 ⋅ 556 ⋅ 343 mod 733
≡ 185148 ⋅ 343 mod 733 ≡ 432 ⋅ 343 mod 733
≡ 148176 mod 733 ≡ 110 mod 733

Es gilt also: 343²⁰⁵ ≡ 110 mod 733

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

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

also gilt: ggt(67,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= 67-2⋅30	eingesetzt in die Zeile drüber:	1	= -3⋅30 +13⋅(67 -2⋅ 30) = -3⋅30 +13⋅67 -26⋅ 30) = 13⋅67 -29⋅ 30 (=1)

Es gilt also: ggt(67,30)=1 = 13⋅67 -29⋅30

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

1 -13⋅67 = -29⋅30

-29⋅30 = -13⋅67 + 1 |+67⋅30

-29⋅30 + 67⋅30 = -13⋅67 + 67⋅30 + 1

(-29 + 67) ⋅ 30 = (-13 + 30) ⋅ 67 + 1

38⋅30 = 17⋅67 + 1

Es gilt also: 38⋅30 = 17⋅67 +1

Somit 38⋅30 = 1 mod 67

38 ist also das Inverse von 30 mod 67