Klasse 5 (G9)
Klasse 6 (G9)
Klasse 7 (G9)
Klasse 8 (G8)
Klasse 9-10 (G8)
Kursstufe (G8)
cosh
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: (4003 - 15996) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(4003 - 15996) mod 4 ≡ (4003 mod 4 - 15996 mod 4) mod 4.
4003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 4003
= 4000
15996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 15996
= 15000
Somit gilt:
(4003 - 15996) mod 4 ≡ (3 - 0) mod 4 ≡ 3 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (63 ⋅ 82) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(63 ⋅ 82) mod 4 ≡ (63 mod 4 ⋅ 82 mod 4) mod 4.
63 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 63 = 60 + 3 = 15 ⋅ 4 + 3 ist.
82 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 82 = 80 + 2 = 20 ⋅ 4 + 2 ist.
Somit gilt:
(63 ⋅ 82) mod 4 ≡ (3 ⋅ 2) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 489128 mod 769.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 489 -> x
2. mod(x²,769) -> 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: 4891=489
2: 4892=4891+1=4891⋅4891 ≡ 489⋅489=239121 ≡ 731 mod 769
4: 4894=4892+2=4892⋅4892 ≡ 731⋅731=534361 ≡ 675 mod 769
8: 4898=4894+4=4894⋅4894 ≡ 675⋅675=455625 ≡ 377 mod 769
16: 48916=4898+8=4898⋅4898 ≡ 377⋅377=142129 ≡ 633 mod 769
32: 48932=48916+16=48916⋅48916 ≡ 633⋅633=400689 ≡ 40 mod 769
64: 48964=48932+32=48932⋅48932 ≡ 40⋅40=1600 ≡ 62 mod 769
128: 489128=48964+64=48964⋅48964 ≡ 62⋅62=3844 ≡ 768 mod 769
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 127207 mod 359.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 207 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 207 an und zerlegen 207 in eine Summer von 2er-Potenzen:
207 = 128+64+8+4+2+1
1: 1271=127
2: 1272=1271+1=1271⋅1271 ≡ 127⋅127=16129 ≡ 333 mod 359
4: 1274=1272+2=1272⋅1272 ≡ 333⋅333=110889 ≡ 317 mod 359
8: 1278=1274+4=1274⋅1274 ≡ 317⋅317=100489 ≡ 328 mod 359
16: 12716=1278+8=1278⋅1278 ≡ 328⋅328=107584 ≡ 243 mod 359
32: 12732=12716+16=12716⋅12716 ≡ 243⋅243=59049 ≡ 173 mod 359
64: 12764=12732+32=12732⋅12732 ≡ 173⋅173=29929 ≡ 132 mod 359
128: 127128=12764+64=12764⋅12764 ≡ 132⋅132=17424 ≡ 192 mod 359
127207
= 127128+64+8+4+2+1
= 127128⋅12764⋅1278⋅1274⋅1272⋅1271
≡ 192 ⋅ 132 ⋅ 328 ⋅ 317 ⋅ 333 ⋅ 127 mod 359
≡ 25344 ⋅ 328 ⋅ 317 ⋅ 333 ⋅ 127 mod 359 ≡ 214 ⋅ 328 ⋅ 317 ⋅ 333 ⋅ 127 mod 359
≡ 70192 ⋅ 317 ⋅ 333 ⋅ 127 mod 359 ≡ 187 ⋅ 317 ⋅ 333 ⋅ 127 mod 359
≡ 59279 ⋅ 333 ⋅ 127 mod 359 ≡ 44 ⋅ 333 ⋅ 127 mod 359
≡ 14652 ⋅ 127 mod 359 ≡ 292 ⋅ 127 mod 359
≡ 37084 mod 359 ≡ 107 mod 359
Es gilt also: 127207 ≡ 107 mod 359
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 37.
Also bestimme x, so dass 37 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 37
| =>89 | = 2⋅37 + 15 |
| =>37 | = 2⋅15 + 7 |
| =>15 | = 2⋅7 + 1 |
| =>7 | = 7⋅1 + 0 |
also gilt: ggt(89,37)=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= 15-2⋅7 | |||
| 7= 37-2⋅15 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅15 -2⋅(37 -2⋅ 15)
= 1⋅15 -2⋅37 +4⋅ 15) = -2⋅37 +5⋅ 15 (=1) |
| 15= 89-2⋅37 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅37 +5⋅(89 -2⋅ 37)
= -2⋅37 +5⋅89 -10⋅ 37) = 5⋅89 -12⋅ 37 (=1) |
Es gilt also: ggt(89,37)=1 = 5⋅89 -12⋅37
oder wenn man 5⋅89 auf die linke Seite bringt:
1 -5⋅89 = -12⋅37
-12⋅37 = -5⋅89 + 1 |+89⋅37
-12⋅37 + 89⋅37 = -5⋅89 + 89⋅37 + 1
(-12 + 89) ⋅ 37 = (-5 + 37) ⋅ 89 + 1
77⋅37 = 32⋅89 + 1
Es gilt also: 77⋅37 = 32⋅89 +1
Somit 77⋅37 = 1 mod 89
77 ist also das Inverse von 37 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 41 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
