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: (2503 + 2502) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2503 + 2502) mod 5 ≡ (2503 mod 5 + 2502 mod 5) mod 5.
2503 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2503
= 2500
2502 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 2502
= 2500
Somit gilt:
(2503 + 2502) mod 5 ≡ (3 + 2) mod 5 ≡ 5 mod 5 ≡ 0 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (76 ⋅ 65) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(76 ⋅ 65) mod 7 ≡ (76 mod 7 ⋅ 65 mod 7) mod 7.
76 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 76 = 70 + 6 = 10 ⋅ 7 + 6 ist.
65 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 9 ⋅ 7 + 2 ist.
Somit gilt:
(76 ⋅ 65) mod 7 ≡ (6 ⋅ 2) mod 7 ≡ 12 mod 7 ≡ 5 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 23632 mod 479.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 236 -> x
2. mod(x²,479) -> 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: 2361=236
2: 2362=2361+1=2361⋅2361 ≡ 236⋅236=55696 ≡ 132 mod 479
4: 2364=2362+2=2362⋅2362 ≡ 132⋅132=17424 ≡ 180 mod 479
8: 2368=2364+4=2364⋅2364 ≡ 180⋅180=32400 ≡ 307 mod 479
16: 23616=2368+8=2368⋅2368 ≡ 307⋅307=94249 ≡ 365 mod 479
32: 23632=23616+16=23616⋅23616 ≡ 365⋅365=133225 ≡ 63 mod 479
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 505239 mod 659.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 239 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 239 an und zerlegen 239 in eine Summer von 2er-Potenzen:
239 = 128+64+32+8+4+2+1
1: 5051=505
2: 5052=5051+1=5051⋅5051 ≡ 505⋅505=255025 ≡ 651 mod 659
4: 5054=5052+2=5052⋅5052 ≡ 651⋅651=423801 ≡ 64 mod 659
8: 5058=5054+4=5054⋅5054 ≡ 64⋅64=4096 ≡ 142 mod 659
16: 50516=5058+8=5058⋅5058 ≡ 142⋅142=20164 ≡ 394 mod 659
32: 50532=50516+16=50516⋅50516 ≡ 394⋅394=155236 ≡ 371 mod 659
64: 50564=50532+32=50532⋅50532 ≡ 371⋅371=137641 ≡ 569 mod 659
128: 505128=50564+64=50564⋅50564 ≡ 569⋅569=323761 ≡ 192 mod 659
505239
= 505128+64+32+8+4+2+1
= 505128⋅50564⋅50532⋅5058⋅5054⋅5052⋅5051
≡ 192 ⋅ 569 ⋅ 371 ⋅ 142 ⋅ 64 ⋅ 651 ⋅ 505 mod 659
≡ 109248 ⋅ 371 ⋅ 142 ⋅ 64 ⋅ 651 ⋅ 505 mod 659 ≡ 513 ⋅ 371 ⋅ 142 ⋅ 64 ⋅ 651 ⋅ 505 mod 659
≡ 190323 ⋅ 142 ⋅ 64 ⋅ 651 ⋅ 505 mod 659 ≡ 531 ⋅ 142 ⋅ 64 ⋅ 651 ⋅ 505 mod 659
≡ 75402 ⋅ 64 ⋅ 651 ⋅ 505 mod 659 ≡ 276 ⋅ 64 ⋅ 651 ⋅ 505 mod 659
≡ 17664 ⋅ 651 ⋅ 505 mod 659 ≡ 530 ⋅ 651 ⋅ 505 mod 659
≡ 345030 ⋅ 505 mod 659 ≡ 373 ⋅ 505 mod 659
≡ 188365 mod 659 ≡ 550 mod 659
Es gilt also: 505239 ≡ 550 mod 659
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 54.
Also bestimme x, so dass 54 ⋅ x ≡ 1 mod 97 gilt:
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
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 37. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
