Aufgabenbeispiele von MGK Klasse 10
Durch Aktualisieren des Browsers (z.B. mit Taste F5) kann man neue Beispielaufgaben sehen
Modulo addieren
Beispiel:
Berechne ohne WTR: (105 - 54) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(105 - 54) mod 5 ≡ (105 mod 5 - 54 mod 5) mod 5.
105 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 105
= 100
54 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 54
= 50
Somit gilt:
(105 - 54) mod 5 ≡ (0 - 4) mod 5 ≡ -4 mod 5 ≡ 1 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (60 ⋅ 29) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(60 ⋅ 29) mod 10 ≡ (60 mod 10 ⋅ 29 mod 10) mod 10.
60 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 60 = 60 + 0 = 6 ⋅ 10 + 0 ist.
29 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 29 = 20 + 9 = 2 ⋅ 10 + 9 ist.
Somit gilt:
(60 ⋅ 29) mod 10 ≡ (0 ⋅ 9) mod 10 ≡ 0 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 274128 mod 571.
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. 274 -> x
2. mod(x²,571) -> 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: 2741=274
2: 2742=2741+1=2741⋅2741 ≡ 274⋅274=75076 ≡ 275 mod 571
4: 2744=2742+2=2742⋅2742 ≡ 275⋅275=75625 ≡ 253 mod 571
8: 2748=2744+4=2744⋅2744 ≡ 253⋅253=64009 ≡ 57 mod 571
16: 27416=2748+8=2748⋅2748 ≡ 57⋅57=3249 ≡ 394 mod 571
32: 27432=27416+16=27416⋅27416 ≡ 394⋅394=155236 ≡ 495 mod 571
64: 27464=27432+32=27432⋅27432 ≡ 495⋅495=245025 ≡ 66 mod 571
128: 274128=27464+64=27464⋅27464 ≡ 66⋅66=4356 ≡ 359 mod 571
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 272121 mod 277.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 121 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 121 an und zerlegen 121 in eine Summer von 2er-Potenzen:
121 = 64+32+16+8+1
1: 2721=272
2: 2722=2721+1=2721⋅2721 ≡ 272⋅272=73984 ≡ 25 mod 277
4: 2724=2722+2=2722⋅2722 ≡ 25⋅25=625 ≡ 71 mod 277
8: 2728=2724+4=2724⋅2724 ≡ 71⋅71=5041 ≡ 55 mod 277
16: 27216=2728+8=2728⋅2728 ≡ 55⋅55=3025 ≡ 255 mod 277
32: 27232=27216+16=27216⋅27216 ≡ 255⋅255=65025 ≡ 207 mod 277
64: 27264=27232+32=27232⋅27232 ≡ 207⋅207=42849 ≡ 191 mod 277
272121
= 27264+32+16+8+1
= 27264⋅27232⋅27216⋅2728⋅2721
≡ 191 ⋅ 207 ⋅ 255 ⋅ 55 ⋅ 272 mod 277
≡ 39537 ⋅ 255 ⋅ 55 ⋅ 272 mod 277 ≡ 203 ⋅ 255 ⋅ 55 ⋅ 272 mod 277
≡ 51765 ⋅ 55 ⋅ 272 mod 277 ≡ 243 ⋅ 55 ⋅ 272 mod 277
≡ 13365 ⋅ 272 mod 277 ≡ 69 ⋅ 272 mod 277
≡ 18768 mod 277 ≡ 209 mod 277
Es gilt also: 272121 ≡ 209 mod 277
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 83.
Also bestimme x, so dass 83 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 83
| =>89 | = 1⋅83 + 6 |
| =>83 | = 13⋅6 + 5 |
| =>6 | = 1⋅5 + 1 |
| =>5 | = 5⋅1 + 0 |
also gilt: ggt(89,83)=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= 6-1⋅5 | |||
| 5= 83-13⋅6 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅6 -1⋅(83 -13⋅ 6)
= 1⋅6 -1⋅83 +13⋅ 6) = -1⋅83 +14⋅ 6 (=1) |
| 6= 89-1⋅83 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅83 +14⋅(89 -1⋅ 83)
= -1⋅83 +14⋅89 -14⋅ 83) = 14⋅89 -15⋅ 83 (=1) |
Es gilt also: ggt(89,83)=1 = 14⋅89 -15⋅83
oder wenn man 14⋅89 auf die linke Seite bringt:
1 -14⋅89 = -15⋅83
-15⋅83 = -14⋅89 + 1 |+89⋅83
-15⋅83 + 89⋅83 = -14⋅89 + 89⋅83 + 1
(-15 + 89) ⋅ 83 = (-14 + 83) ⋅ 89 + 1
74⋅83 = 69⋅89 + 1
Es gilt also: 74⋅83 = 69⋅89 +1
Somit 74⋅83 = 1 mod 89
74 ist also das Inverse von 83 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 67 und q = 97. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
