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: (17992 - 268) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(17992 - 268) mod 9 ≡ (17992 mod 9 - 268 mod 9) mod 9.
17992 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 17992
= 18000
268 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 268
= 270
Somit gilt:
(17992 - 268) mod 9 ≡ (1 - 7) mod 9 ≡ -6 mod 9 ≡ 3 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (41 ⋅ 19) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(41 ⋅ 19) mod 10 ≡ (41 mod 10 ⋅ 19 mod 10) mod 10.
41 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 41 = 40 + 1 = 4 ⋅ 10 + 1 ist.
19 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 19 = 10 + 9 = 1 ⋅ 10 + 9 ist.
Somit gilt:
(41 ⋅ 19) mod 10 ≡ (1 ⋅ 9) mod 10 ≡ 9 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 423128 mod 863.
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. 423 -> x
2. mod(x²,863) -> 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: 4231=423
2: 4232=4231+1=4231⋅4231 ≡ 423⋅423=178929 ≡ 288 mod 863
4: 4234=4232+2=4232⋅4232 ≡ 288⋅288=82944 ≡ 96 mod 863
8: 4238=4234+4=4234⋅4234 ≡ 96⋅96=9216 ≡ 586 mod 863
16: 42316=4238+8=4238⋅4238 ≡ 586⋅586=343396 ≡ 785 mod 863
32: 42332=42316+16=42316⋅42316 ≡ 785⋅785=616225 ≡ 43 mod 863
64: 42364=42332+32=42332⋅42332 ≡ 43⋅43=1849 ≡ 123 mod 863
128: 423128=42364+64=42364⋅42364 ≡ 123⋅123=15129 ≡ 458 mod 863
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 199142 mod 541.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 142 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 142 an und zerlegen 142 in eine Summer von 2er-Potenzen:
142 = 128+8+4+2
1: 1991=199
2: 1992=1991+1=1991⋅1991 ≡ 199⋅199=39601 ≡ 108 mod 541
4: 1994=1992+2=1992⋅1992 ≡ 108⋅108=11664 ≡ 303 mod 541
8: 1998=1994+4=1994⋅1994 ≡ 303⋅303=91809 ≡ 380 mod 541
16: 19916=1998+8=1998⋅1998 ≡ 380⋅380=144400 ≡ 494 mod 541
32: 19932=19916+16=19916⋅19916 ≡ 494⋅494=244036 ≡ 45 mod 541
64: 19964=19932+32=19932⋅19932 ≡ 45⋅45=2025 ≡ 402 mod 541
128: 199128=19964+64=19964⋅19964 ≡ 402⋅402=161604 ≡ 386 mod 541
199142
= 199128+8+4+2
= 199128⋅1998⋅1994⋅1992
≡ 386 ⋅ 380 ⋅ 303 ⋅ 108 mod 541
≡ 146680 ⋅ 303 ⋅ 108 mod 541 ≡ 69 ⋅ 303 ⋅ 108 mod 541
≡ 20907 ⋅ 108 mod 541 ≡ 349 ⋅ 108 mod 541
≡ 37692 mod 541 ≡ 363 mod 541
Es gilt also: 199142 ≡ 363 mod 541
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 40.
Also bestimme x, so dass 40 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 40
| =>89 | = 2⋅40 + 9 |
| =>40 | = 4⋅9 + 4 |
| =>9 | = 2⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(89,40)=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= 9-2⋅4 | |||
| 4= 40-4⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -2⋅(40 -4⋅ 9)
= 1⋅9 -2⋅40 +8⋅ 9) = -2⋅40 +9⋅ 9 (=1) |
| 9= 89-2⋅40 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅40 +9⋅(89 -2⋅ 40)
= -2⋅40 +9⋅89 -18⋅ 40) = 9⋅89 -20⋅ 40 (=1) |
Es gilt also: ggt(89,40)=1 = 9⋅89 -20⋅40
oder wenn man 9⋅89 auf die linke Seite bringt:
1 -9⋅89 = -20⋅40
-20⋅40 = -9⋅89 + 1 |+89⋅40
-20⋅40 + 89⋅40 = -9⋅89 + 89⋅40 + 1
(-20 + 89) ⋅ 40 = (-9 + 40) ⋅ 89 + 1
69⋅40 = 31⋅89 + 1
Es gilt also: 69⋅40 = 31⋅89 +1
Somit 69⋅40 = 1 mod 89
69 ist also das Inverse von 40 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 67 und q = 83. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
