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: (17998 + 352) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(17998 + 352) mod 9 ≡ (17998 mod 9 + 352 mod 9) mod 9.
17998 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 17998
= 18000
352 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 352
= 360
Somit gilt:
(17998 + 352) mod 9 ≡ (7 + 1) mod 9 ≡ 8 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (61 ⋅ 60) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(61 ⋅ 60) mod 8 ≡ (61 mod 8 ⋅ 60 mod 8) mod 8.
61 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 61 = 56 + 5 = 7 ⋅ 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:
(61 ⋅ 60) mod 8 ≡ (5 ⋅ 4) mod 8 ≡ 20 mod 8 ≡ 4 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 43332 mod 929.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 433 -> x
2. mod(x²,929) -> 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: 4331=433
2: 4332=4331+1=4331⋅4331 ≡ 433⋅433=187489 ≡ 760 mod 929
4: 4334=4332+2=4332⋅4332 ≡ 760⋅760=577600 ≡ 691 mod 929
8: 4338=4334+4=4334⋅4334 ≡ 691⋅691=477481 ≡ 904 mod 929
16: 43316=4338+8=4338⋅4338 ≡ 904⋅904=817216 ≡ 625 mod 929
32: 43332=43316+16=43316⋅43316 ≡ 625⋅625=390625 ≡ 445 mod 929
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 150247 mod 313.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 247 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 247 an und zerlegen 247 in eine Summer von 2er-Potenzen:
247 = 128+64+32+16+4+2+1
1: 1501=150
2: 1502=1501+1=1501⋅1501 ≡ 150⋅150=22500 ≡ 277 mod 313
4: 1504=1502+2=1502⋅1502 ≡ 277⋅277=76729 ≡ 44 mod 313
8: 1508=1504+4=1504⋅1504 ≡ 44⋅44=1936 ≡ 58 mod 313
16: 15016=1508+8=1508⋅1508 ≡ 58⋅58=3364 ≡ 234 mod 313
32: 15032=15016+16=15016⋅15016 ≡ 234⋅234=54756 ≡ 294 mod 313
64: 15064=15032+32=15032⋅15032 ≡ 294⋅294=86436 ≡ 48 mod 313
128: 150128=15064+64=15064⋅15064 ≡ 48⋅48=2304 ≡ 113 mod 313
150247
= 150128+64+32+16+4+2+1
= 150128⋅15064⋅15032⋅15016⋅1504⋅1502⋅1501
≡ 113 ⋅ 48 ⋅ 294 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 5424 ⋅ 294 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313 ≡ 103 ⋅ 294 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 30282 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313 ≡ 234 ⋅ 234 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 54756 ⋅ 44 ⋅ 277 ⋅ 150 mod 313 ≡ 294 ⋅ 44 ⋅ 277 ⋅ 150 mod 313
≡ 12936 ⋅ 277 ⋅ 150 mod 313 ≡ 103 ⋅ 277 ⋅ 150 mod 313
≡ 28531 ⋅ 150 mod 313 ≡ 48 ⋅ 150 mod 313
≡ 7200 mod 313 ≡ 1 mod 313
Es gilt also: 150247 ≡ 1 mod 313
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 46.
Also bestimme x, so dass 46 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 46
| =>83 | = 1⋅46 + 37 |
| =>46 | = 1⋅37 + 9 |
| =>37 | = 4⋅9 + 1 |
| =>9 | = 9⋅1 + 0 |
also gilt: ggt(83,46)=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= 37-4⋅9 | |||
| 9= 46-1⋅37 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅37 -4⋅(46 -1⋅ 37)
= 1⋅37 -4⋅46 +4⋅ 37) = -4⋅46 +5⋅ 37 (=1) |
| 37= 83-1⋅46 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅46 +5⋅(83 -1⋅ 46)
= -4⋅46 +5⋅83 -5⋅ 46) = 5⋅83 -9⋅ 46 (=1) |
Es gilt also: ggt(83,46)=1 = 5⋅83 -9⋅46
oder wenn man 5⋅83 auf die linke Seite bringt:
1 -5⋅83 = -9⋅46
-9⋅46 = -5⋅83 + 1 |+83⋅46
-9⋅46 + 83⋅46 = -5⋅83 + 83⋅46 + 1
(-9 + 83) ⋅ 46 = (-5 + 46) ⋅ 83 + 1
74⋅46 = 41⋅83 + 1
Es gilt also: 74⋅46 = 41⋅83 +1
Somit 74⋅46 = 1 mod 83
74 ist also das Inverse von 46 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 67 und q = 97. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
