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: (3605 + 3608) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(3605 + 3608) mod 9 ≡ (3605 mod 9 + 3608 mod 9) mod 9.
3605 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 3605
= 3600
3608 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 3608
= 3600
Somit gilt:
(3605 + 3608) mod 9 ≡ (5 + 8) mod 9 ≡ 13 mod 9 ≡ 4 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (46 ⋅ 25) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(46 ⋅ 25) mod 11 ≡ (46 mod 11 ⋅ 25 mod 11) mod 11.
46 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 46 = 44 + 2 = 4 ⋅ 11 + 2 ist.
25 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 25 = 22 + 3 = 2 ⋅ 11 + 3 ist.
Somit gilt:
(46 ⋅ 25) mod 11 ≡ (2 ⋅ 3) mod 11 ≡ 6 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 181128 mod 439.
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. 181 -> x
2. mod(x²,439) -> 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: 1811=181
2: 1812=1811+1=1811⋅1811 ≡ 181⋅181=32761 ≡ 275 mod 439
4: 1814=1812+2=1812⋅1812 ≡ 275⋅275=75625 ≡ 117 mod 439
8: 1818=1814+4=1814⋅1814 ≡ 117⋅117=13689 ≡ 80 mod 439
16: 18116=1818+8=1818⋅1818 ≡ 80⋅80=6400 ≡ 254 mod 439
32: 18132=18116+16=18116⋅18116 ≡ 254⋅254=64516 ≡ 422 mod 439
64: 18164=18132+32=18132⋅18132 ≡ 422⋅422=178084 ≡ 289 mod 439
128: 181128=18164+64=18164⋅18164 ≡ 289⋅289=83521 ≡ 111 mod 439
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 712146 mod 883.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 146 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 146 an und zerlegen 146 in eine Summer von 2er-Potenzen:
146 = 128+16+2
1: 7121=712
2: 7122=7121+1=7121⋅7121 ≡ 712⋅712=506944 ≡ 102 mod 883
4: 7124=7122+2=7122⋅7122 ≡ 102⋅102=10404 ≡ 691 mod 883
8: 7128=7124+4=7124⋅7124 ≡ 691⋅691=477481 ≡ 661 mod 883
16: 71216=7128+8=7128⋅7128 ≡ 661⋅661=436921 ≡ 719 mod 883
32: 71232=71216+16=71216⋅71216 ≡ 719⋅719=516961 ≡ 406 mod 883
64: 71264=71232+32=71232⋅71232 ≡ 406⋅406=164836 ≡ 598 mod 883
128: 712128=71264+64=71264⋅71264 ≡ 598⋅598=357604 ≡ 872 mod 883
712146
= 712128+16+2
= 712128⋅71216⋅7122
≡ 872 ⋅ 719 ⋅ 102 mod 883
≡ 626968 ⋅ 102 mod 883 ≡ 38 ⋅ 102 mod 883
≡ 3876 mod 883 ≡ 344 mod 883
Es gilt also: 712146 ≡ 344 mod 883
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-79-Inverse zur Zahl 70.
Also bestimme x, so dass 70 ⋅ x ≡ 1 mod 79 gilt:
Berechnung des größten gemeinsamen Teilers von 79 und 70
| =>79 | = 1⋅70 + 9 |
| =>70 | = 7⋅9 + 7 |
| =>9 | = 1⋅7 + 2 |
| =>7 | = 3⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(79,70)=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= 7-3⋅2 | |||
| 2= 9-1⋅7 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅7 -3⋅(9 -1⋅ 7)
= 1⋅7 -3⋅9 +3⋅ 7) = -3⋅9 +4⋅ 7 (=1) |
| 7= 70-7⋅9 | eingesetzt in die Zeile drüber: | 1 |
= -3⋅9 +4⋅(70 -7⋅ 9)
= -3⋅9 +4⋅70 -28⋅ 9) = 4⋅70 -31⋅ 9 (=1) |
| 9= 79-1⋅70 | eingesetzt in die Zeile drüber: | 1 |
= 4⋅70 -31⋅(79 -1⋅ 70)
= 4⋅70 -31⋅79 +31⋅ 70) = -31⋅79 +35⋅ 70 (=1) |
Es gilt also: ggt(79,70)=1 = -31⋅79 +35⋅70
oder wenn man -31⋅79 auf die linke Seite bringt:
1 +31⋅79 = +35⋅70
Es gilt also: 35⋅70 = 31⋅79 +1
Somit 35⋅70 = 1 mod 79
35 ist also das Inverse von 70 mod 79
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 71 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.