nach Aufgabentypen suchen

Aufgabentypen anhand von Beispielen durchstöbern

Browserfenster aktualisieren (F5), um neue Beispiele bei den Aufgabentypen zu sehen

Modulo addieren

Beispiel:

Berechne ohne WTR: (68 - 14001) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 - 14001) mod 7 ≡ (68 mod 7 - 14001 mod 7) mod 7.

68 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 68 = 70-2 = 7 ⋅ 10 -2 = 7 ⋅ 10 - 7 + 5.

14001 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 14001 = 14000+1 = 7 ⋅ 2000 +1.

Somit gilt:

(68 - 14001) mod 7 ≡ (5 - 1) mod 7 ≡ 4 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (68 ⋅ 43) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 43) mod 9 ≡ (68 mod 9 ⋅ 43 mod 9) mod 9.

68 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 68 = 63 + 5 = 7 ⋅ 9 + 5 ist.

43 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 43 = 36 + 7 = 4 ⋅ 9 + 7 ist.

Somit gilt:

(68 ⋅ 43) mod 9 ≡ (5 ⋅ 7) mod 9 ≡ 35 mod 9 ≡ 8 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 92164 mod 953.

Lösung einblenden

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

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

Zur technischen Durchführung mit einem TI-WTR bietet sich folgende Vorgehensweise an:
1. 921 -> x
2. mod(x²,953) -> x

  • den Pfeil "->" erhält man durch Drücken der [sto->]-Taste
  • die x-Taste ist direkt darüber
  • "mod" erhält man durch [math]->NUM->8:mod
  • das Komma "," erhält man durch Drücken von [2nd][.]

1: 9211=921

2: 9212=9211+1=9211⋅9211 ≡ 921⋅921=848241 ≡ 71 mod 953

4: 9214=9212+2=9212⋅9212 ≡ 71⋅71=5041 ≡ 276 mod 953

8: 9218=9214+4=9214⋅9214 ≡ 276⋅276=76176 ≡ 889 mod 953

16: 92116=9218+8=9218⋅9218 ≡ 889⋅889=790321 ≡ 284 mod 953

32: 92132=92116+16=92116⋅92116 ≡ 284⋅284=80656 ≡ 604 mod 953

64: 92164=92132+32=92132⋅92132 ≡ 604⋅604=364816 ≡ 770 mod 953

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 765228 mod 823.

Lösung einblenden

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

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

228 = 128+64+32+4

1: 7651=765

2: 7652=7651+1=7651⋅7651 ≡ 765⋅765=585225 ≡ 72 mod 823

4: 7654=7652+2=7652⋅7652 ≡ 72⋅72=5184 ≡ 246 mod 823

8: 7658=7654+4=7654⋅7654 ≡ 246⋅246=60516 ≡ 437 mod 823

16: 76516=7658+8=7658⋅7658 ≡ 437⋅437=190969 ≡ 33 mod 823

32: 76532=76516+16=76516⋅76516 ≡ 33⋅33=1089 ≡ 266 mod 823

64: 76564=76532+32=76532⋅76532 ≡ 266⋅266=70756 ≡ 801 mod 823

128: 765128=76564+64=76564⋅76564 ≡ 801⋅801=641601 ≡ 484 mod 823

765228

= 765128+64+32+4

= 765128⋅76564⋅76532⋅7654

≡ 484 ⋅ 801 ⋅ 266 ⋅ 246 mod 823
≡ 387684 ⋅ 266 ⋅ 246 mod 823 ≡ 51 ⋅ 266 ⋅ 246 mod 823
≡ 13566 ⋅ 246 mod 823 ≡ 398 ⋅ 246 mod 823
≡ 97908 mod 823 ≡ 794 mod 823

Es gilt also: 765228 ≡ 794 mod 823

erweiterter Euklid'scher Algorithmus

Beispiel:

Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 25.

Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 61 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 61 und 25

=>61 = 2⋅25 + 11
=>25 = 2⋅11 + 3
=>11 = 3⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(61,25)=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= 11-3⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(11 -3⋅ 3)
= 1⋅3 -1⋅11 +3⋅ 3)
= -1⋅11 +4⋅ 3 (=1)
3= 25-2⋅11 eingesetzt in die Zeile drüber: 1 = -1⋅11 +4⋅(25 -2⋅ 11)
= -1⋅11 +4⋅25 -8⋅ 11)
= 4⋅25 -9⋅ 11 (=1)
11= 61-2⋅25 eingesetzt in die Zeile drüber: 1 = 4⋅25 -9⋅(61 -2⋅ 25)
= 4⋅25 -9⋅61 +18⋅ 25)
= -9⋅61 +22⋅ 25 (=1)

Es gilt also: ggt(61,25)=1 = -9⋅61 +22⋅25

oder wenn man -9⋅61 auf die linke Seite bringt:

1 +9⋅61 = +22⋅25

Es gilt also: 22⋅25 = 9⋅61 +1

Somit 22⋅25 = 1 mod 61

22 ist also das Inverse von 25 mod 61

Schlüsselpaar für RSA

Beispiel:

Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 41. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.

Lösung einblenden