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: (13998 + 35006) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(13998 + 35006) mod 7 ≡ (13998 mod 7 + 35006 mod 7) mod 7.
13998 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 13998
= 14000
35006 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 35006
= 35000
Somit gilt:
(13998 + 35006) mod 7 ≡ (5 + 6) mod 7 ≡ 11 mod 7 ≡ 4 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (18 ⋅ 41) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(18 ⋅ 41) mod 9 ≡ (18 mod 9 ⋅ 41 mod 9) mod 9.
18 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 18 = 18 + 0 = 2 ⋅ 9 + 0 ist.
41 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 41 = 36 + 5 = 4 ⋅ 9 + 5 ist.
Somit gilt:
(18 ⋅ 41) mod 9 ≡ (0 ⋅ 5) mod 9 ≡ 0 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 592128 mod 953.
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. 592 -> x
2. mod(x²,953) -> 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: 5921=592
2: 5922=5921+1=5921⋅5921 ≡ 592⋅592=350464 ≡ 713 mod 953
4: 5924=5922+2=5922⋅5922 ≡ 713⋅713=508369 ≡ 420 mod 953
8: 5928=5924+4=5924⋅5924 ≡ 420⋅420=176400 ≡ 95 mod 953
16: 59216=5928+8=5928⋅5928 ≡ 95⋅95=9025 ≡ 448 mod 953
32: 59232=59216+16=59216⋅59216 ≡ 448⋅448=200704 ≡ 574 mod 953
64: 59264=59232+32=59232⋅59232 ≡ 574⋅574=329476 ≡ 691 mod 953
128: 592128=59264+64=59264⋅59264 ≡ 691⋅691=477481 ≡ 28 mod 953
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 466111 mod 563.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 111 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 111 an und zerlegen 111 in eine Summer von 2er-Potenzen:
111 = 64+32+8+4+2+1
1: 4661=466
2: 4662=4661+1=4661⋅4661 ≡ 466⋅466=217156 ≡ 401 mod 563
4: 4664=4662+2=4662⋅4662 ≡ 401⋅401=160801 ≡ 346 mod 563
8: 4668=4664+4=4664⋅4664 ≡ 346⋅346=119716 ≡ 360 mod 563
16: 46616=4668+8=4668⋅4668 ≡ 360⋅360=129600 ≡ 110 mod 563
32: 46632=46616+16=46616⋅46616 ≡ 110⋅110=12100 ≡ 277 mod 563
64: 46664=46632+32=46632⋅46632 ≡ 277⋅277=76729 ≡ 161 mod 563
466111
= 46664+32+8+4+2+1
= 46664⋅46632⋅4668⋅4664⋅4662⋅4661
≡ 161 ⋅ 277 ⋅ 360 ⋅ 346 ⋅ 401 ⋅ 466 mod 563
≡ 44597 ⋅ 360 ⋅ 346 ⋅ 401 ⋅ 466 mod 563 ≡ 120 ⋅ 360 ⋅ 346 ⋅ 401 ⋅ 466 mod 563
≡ 43200 ⋅ 346 ⋅ 401 ⋅ 466 mod 563 ≡ 412 ⋅ 346 ⋅ 401 ⋅ 466 mod 563
≡ 142552 ⋅ 401 ⋅ 466 mod 563 ≡ 113 ⋅ 401 ⋅ 466 mod 563
≡ 45313 ⋅ 466 mod 563 ≡ 273 ⋅ 466 mod 563
≡ 127218 mod 563 ≡ 543 mod 563
Es gilt also: 466111 ≡ 543 mod 563
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-59-Inverse zur Zahl 42.
Also bestimme x, so dass 42 ⋅ x ≡ 1 mod 59 gilt:
Berechnung des größten gemeinsamen Teilers von 59 und 42
| =>59 | = 1⋅42 + 17 |
| =>42 | = 2⋅17 + 8 |
| =>17 | = 2⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(59,42)=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= 17-2⋅8 | |||
| 8= 42-2⋅17 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅17 -2⋅(42 -2⋅ 17)
= 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1) |
| 17= 59-1⋅42 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅42 +5⋅(59 -1⋅ 42)
= -2⋅42 +5⋅59 -5⋅ 42) = 5⋅59 -7⋅ 42 (=1) |
Es gilt also: ggt(59,42)=1 = 5⋅59 -7⋅42
oder wenn man 5⋅59 auf die linke Seite bringt:
1 -5⋅59 = -7⋅42
-7⋅42 = -5⋅59 + 1 |+59⋅42
-7⋅42 + 59⋅42 = -5⋅59 + 59⋅42 + 1
(-7 + 59) ⋅ 42 = (-5 + 42) ⋅ 59 + 1
52⋅42 = 37⋅59 + 1
Es gilt also: 52⋅42 = 37⋅59 +1
Somit 52⋅42 = 1 mod 59
52 ist also das Inverse von 42 mod 59
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 47 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
