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: (68 + 1396) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(68 + 1396) mod 7 ≡ (68 mod 7 + 1396 mod 7) mod 7.
68 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 68
= 70
1396 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 1396
= 1400
Somit gilt:
(68 + 1396) mod 7 ≡ (5 + 3) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (85 ⋅ 60) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(85 ⋅ 60) mod 8 ≡ (85 mod 8 ⋅ 60 mod 8) mod 8.
85 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 85 = 80 + 5 = 10 ⋅ 8 + 5 ist.
60 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 60 = 56 + 4 = 7 ⋅ 8 + 4 ist.
Somit gilt:
(85 ⋅ 60) mod 8 ≡ (5 ⋅ 4) mod 8 ≡ 20 mod 8 ≡ 4 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 41364 mod 503.
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. 413 -> x
2. mod(x²,503) -> 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: 4131=413
2: 4132=4131+1=4131⋅4131 ≡ 413⋅413=170569 ≡ 52 mod 503
4: 4134=4132+2=4132⋅4132 ≡ 52⋅52=2704 ≡ 189 mod 503
8: 4138=4134+4=4134⋅4134 ≡ 189⋅189=35721 ≡ 8 mod 503
16: 41316=4138+8=4138⋅4138 ≡ 8⋅8=64 ≡ 64 mod 503
32: 41332=41316+16=41316⋅41316 ≡ 64⋅64=4096 ≡ 72 mod 503
64: 41364=41332+32=41332⋅41332 ≡ 72⋅72=5184 ≡ 154 mod 503
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 154208 mod 269.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 208 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 208 an und zerlegen 208 in eine Summer von 2er-Potenzen:
208 = 128+64+16
1: 1541=154
2: 1542=1541+1=1541⋅1541 ≡ 154⋅154=23716 ≡ 44 mod 269
4: 1544=1542+2=1542⋅1542 ≡ 44⋅44=1936 ≡ 53 mod 269
8: 1548=1544+4=1544⋅1544 ≡ 53⋅53=2809 ≡ 119 mod 269
16: 15416=1548+8=1548⋅1548 ≡ 119⋅119=14161 ≡ 173 mod 269
32: 15432=15416+16=15416⋅15416 ≡ 173⋅173=29929 ≡ 70 mod 269
64: 15464=15432+32=15432⋅15432 ≡ 70⋅70=4900 ≡ 58 mod 269
128: 154128=15464+64=15464⋅15464 ≡ 58⋅58=3364 ≡ 136 mod 269
154208
= 154128+64+16
= 154128⋅15464⋅15416
≡ 136 ⋅ 58 ⋅ 173 mod 269
≡ 7888 ⋅ 173 mod 269 ≡ 87 ⋅ 173 mod 269
≡ 15051 mod 269 ≡ 256 mod 269
Es gilt also: 154208 ≡ 256 mod 269
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 48.
Also bestimme x, so dass 48 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 48
| =>67 | = 1⋅48 + 19 |
| =>48 | = 2⋅19 + 10 |
| =>19 | = 1⋅10 + 9 |
| =>10 | = 1⋅9 + 1 |
| =>9 | = 9⋅1 + 0 |
also gilt: ggt(67,48)=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= 10-1⋅9 | |||
| 9= 19-1⋅10 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅10 -1⋅(19 -1⋅ 10)
= 1⋅10 -1⋅19 +1⋅ 10) = -1⋅19 +2⋅ 10 (=1) |
| 10= 48-2⋅19 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅19 +2⋅(48 -2⋅ 19)
= -1⋅19 +2⋅48 -4⋅ 19) = 2⋅48 -5⋅ 19 (=1) |
| 19= 67-1⋅48 | eingesetzt in die Zeile drüber: | 1 |
= 2⋅48 -5⋅(67 -1⋅ 48)
= 2⋅48 -5⋅67 +5⋅ 48) = -5⋅67 +7⋅ 48 (=1) |
Es gilt also: ggt(67,48)=1 = -5⋅67 +7⋅48
oder wenn man -5⋅67 auf die linke Seite bringt:
1 +5⋅67 = +7⋅48
Es gilt also: 7⋅48 = 5⋅67 +1
Somit 7⋅48 = 1 mod 67
7 ist also das Inverse von 48 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 37 und q = 47. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
