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: (248 + 147) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(248 + 147) mod 5 ≡ (248 mod 5 + 147 mod 5) mod 5.
248 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 248
= 240
147 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 147
= 140
Somit gilt:
(248 + 147) mod 5 ≡ (3 + 2) mod 5 ≡ 5 mod 5 ≡ 0 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (16 ⋅ 33) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(16 ⋅ 33) mod 11 ≡ (16 mod 11 ⋅ 33 mod 11) mod 11.
16 mod 11 ≡ 5 mod 11 kann man relativ leicht bestimmen, weil ja 16 = 11 + 5 = 1 ⋅ 11 + 5 ist.
33 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 33 = 33 + 0 = 3 ⋅ 11 + 0 ist.
Somit gilt:
(16 ⋅ 33) mod 11 ≡ (5 ⋅ 0) mod 11 ≡ 0 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 520128 mod 601.
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. 520 -> x
2. mod(x²,601) -> 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: 5201=520
2: 5202=5201+1=5201⋅5201 ≡ 520⋅520=270400 ≡ 551 mod 601
4: 5204=5202+2=5202⋅5202 ≡ 551⋅551=303601 ≡ 96 mod 601
8: 5208=5204+4=5204⋅5204 ≡ 96⋅96=9216 ≡ 201 mod 601
16: 52016=5208+8=5208⋅5208 ≡ 201⋅201=40401 ≡ 134 mod 601
32: 52032=52016+16=52016⋅52016 ≡ 134⋅134=17956 ≡ 527 mod 601
64: 52064=52032+32=52032⋅52032 ≡ 527⋅527=277729 ≡ 67 mod 601
128: 520128=52064+64=52064⋅52064 ≡ 67⋅67=4489 ≡ 282 mod 601
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 417165 mod 601.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 165 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 165 an und zerlegen 165 in eine Summer von 2er-Potenzen:
165 = 128+32+4+1
1: 4171=417
2: 4172=4171+1=4171⋅4171 ≡ 417⋅417=173889 ≡ 200 mod 601
4: 4174=4172+2=4172⋅4172 ≡ 200⋅200=40000 ≡ 334 mod 601
8: 4178=4174+4=4174⋅4174 ≡ 334⋅334=111556 ≡ 371 mod 601
16: 41716=4178+8=4178⋅4178 ≡ 371⋅371=137641 ≡ 12 mod 601
32: 41732=41716+16=41716⋅41716 ≡ 12⋅12=144 ≡ 144 mod 601
64: 41764=41732+32=41732⋅41732 ≡ 144⋅144=20736 ≡ 302 mod 601
128: 417128=41764+64=41764⋅41764 ≡ 302⋅302=91204 ≡ 453 mod 601
417165
= 417128+32+4+1
= 417128⋅41732⋅4174⋅4171
≡ 453 ⋅ 144 ⋅ 334 ⋅ 417 mod 601
≡ 65232 ⋅ 334 ⋅ 417 mod 601 ≡ 324 ⋅ 334 ⋅ 417 mod 601
≡ 108216 ⋅ 417 mod 601 ≡ 36 ⋅ 417 mod 601
≡ 15012 mod 601 ≡ 588 mod 601
Es gilt also: 417165 ≡ 588 mod 601
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 65.
Also bestimme x, so dass 65 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 65
| =>101 | = 1⋅65 + 36 |
| =>65 | = 1⋅36 + 29 |
| =>36 | = 1⋅29 + 7 |
| =>29 | = 4⋅7 + 1 |
| =>7 | = 7⋅1 + 0 |
also gilt: ggt(101,65)=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= 29-4⋅7 | |||
| 7= 36-1⋅29 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅29 -4⋅(36 -1⋅ 29)
= 1⋅29 -4⋅36 +4⋅ 29) = -4⋅36 +5⋅ 29 (=1) |
| 29= 65-1⋅36 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅36 +5⋅(65 -1⋅ 36)
= -4⋅36 +5⋅65 -5⋅ 36) = 5⋅65 -9⋅ 36 (=1) |
| 36= 101-1⋅65 | eingesetzt in die Zeile drüber: | 1 |
= 5⋅65 -9⋅(101 -1⋅ 65)
= 5⋅65 -9⋅101 +9⋅ 65) = -9⋅101 +14⋅ 65 (=1) |
Es gilt also: ggt(101,65)=1 = -9⋅101 +14⋅65
oder wenn man -9⋅101 auf die linke Seite bringt:
1 +9⋅101 = +14⋅65
Es gilt also: 14⋅65 = 9⋅101 +1
Somit 14⋅65 = 1 mod 101
14 ist also das Inverse von 65 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 89 und q = 73. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
