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: (35007 + 279) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(35007 + 279) mod 7 ≡ (35007 mod 7 + 279 mod 7) mod 7.
35007 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 35007
= 35000
279 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 279
= 280
Somit gilt:
(35007 + 279) mod 7 ≡ (0 + 6) mod 7 ≡ 6 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (83 ⋅ 28) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(83 ⋅ 28) mod 8 ≡ (83 mod 8 ⋅ 28 mod 8) mod 8.
83 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 83 = 80 + 3 = 10 ⋅ 8 + 3 ist.
28 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 28 = 24 + 4 = 3 ⋅ 8 + 4 ist.
Somit gilt:
(83 ⋅ 28) mod 8 ≡ (3 ⋅ 4) mod 8 ≡ 12 mod 8 ≡ 4 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 59664 mod 719.
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. 596 -> x
2. mod(x²,719) -> 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: 5961=596
2: 5962=5961+1=5961⋅5961 ≡ 596⋅596=355216 ≡ 30 mod 719
4: 5964=5962+2=5962⋅5962 ≡ 30⋅30=900 ≡ 181 mod 719
8: 5968=5964+4=5964⋅5964 ≡ 181⋅181=32761 ≡ 406 mod 719
16: 59616=5968+8=5968⋅5968 ≡ 406⋅406=164836 ≡ 185 mod 719
32: 59632=59616+16=59616⋅59616 ≡ 185⋅185=34225 ≡ 432 mod 719
64: 59664=59632+32=59632⋅59632 ≡ 432⋅432=186624 ≡ 403 mod 719
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 152238 mod 431.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 238 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 238 an und zerlegen 238 in eine Summer von 2er-Potenzen:
238 = 128+64+32+8+4+2
1: 1521=152
2: 1522=1521+1=1521⋅1521 ≡ 152⋅152=23104 ≡ 261 mod 431
4: 1524=1522+2=1522⋅1522 ≡ 261⋅261=68121 ≡ 23 mod 431
8: 1528=1524+4=1524⋅1524 ≡ 23⋅23=529 ≡ 98 mod 431
16: 15216=1528+8=1528⋅1528 ≡ 98⋅98=9604 ≡ 122 mod 431
32: 15232=15216+16=15216⋅15216 ≡ 122⋅122=14884 ≡ 230 mod 431
64: 15264=15232+32=15232⋅15232 ≡ 230⋅230=52900 ≡ 318 mod 431
128: 152128=15264+64=15264⋅15264 ≡ 318⋅318=101124 ≡ 270 mod 431
152238
= 152128+64+32+8+4+2
= 152128⋅15264⋅15232⋅1528⋅1524⋅1522
≡ 270 ⋅ 318 ⋅ 230 ⋅ 98 ⋅ 23 ⋅ 261 mod 431
≡ 85860 ⋅ 230 ⋅ 98 ⋅ 23 ⋅ 261 mod 431 ≡ 91 ⋅ 230 ⋅ 98 ⋅ 23 ⋅ 261 mod 431
≡ 20930 ⋅ 98 ⋅ 23 ⋅ 261 mod 431 ≡ 242 ⋅ 98 ⋅ 23 ⋅ 261 mod 431
≡ 23716 ⋅ 23 ⋅ 261 mod 431 ≡ 11 ⋅ 23 ⋅ 261 mod 431
≡ 253 ⋅ 261 mod 431
≡ 66033 mod 431 ≡ 90 mod 431
Es gilt also: 152238 ≡ 90 mod 431
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 39.
Also bestimme x, so dass 39 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 39
| =>83 | = 2⋅39 + 5 |
| =>39 | = 7⋅5 + 4 |
| =>5 | = 1⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(83,39)=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= 5-1⋅4 | |||
| 4= 39-7⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -1⋅(39 -7⋅ 5)
= 1⋅5 -1⋅39 +7⋅ 5) = -1⋅39 +8⋅ 5 (=1) |
| 5= 83-2⋅39 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅39 +8⋅(83 -2⋅ 39)
= -1⋅39 +8⋅83 -16⋅ 39) = 8⋅83 -17⋅ 39 (=1) |
Es gilt also: ggt(83,39)=1 = 8⋅83 -17⋅39
oder wenn man 8⋅83 auf die linke Seite bringt:
1 -8⋅83 = -17⋅39
-17⋅39 = -8⋅83 + 1 |+83⋅39
-17⋅39 + 83⋅39 = -8⋅83 + 83⋅39 + 1
(-17 + 83) ⋅ 39 = (-8 + 39) ⋅ 83 + 1
66⋅39 = 31⋅83 + 1
Es gilt also: 66⋅39 = 31⋅83 +1
Somit 66⋅39 = 1 mod 83
66 ist also das Inverse von 39 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 41 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
