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: (54 + 5002) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(54 + 5002) mod 5 ≡ (54 mod 5 + 5002 mod 5) mod 5.
54 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 54
= 50
5002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 5002
= 5000
Somit gilt:
(54 + 5002) mod 5 ≡ (4 + 2) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (76 ⋅ 70) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(76 ⋅ 70) mod 6 ≡ (76 mod 6 ⋅ 70 mod 6) mod 6.
76 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 76 = 72 + 4 = 12 ⋅ 6 + 4 ist.
70 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 11 ⋅ 6 + 4 ist.
Somit gilt:
(76 ⋅ 70) mod 6 ≡ (4 ⋅ 4) mod 6 ≡ 16 mod 6 ≡ 4 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 176128 mod 239.
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. 176 -> x
2. mod(x²,239) -> 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: 1761=176
2: 1762=1761+1=1761⋅1761 ≡ 176⋅176=30976 ≡ 145 mod 239
4: 1764=1762+2=1762⋅1762 ≡ 145⋅145=21025 ≡ 232 mod 239
8: 1768=1764+4=1764⋅1764 ≡ 232⋅232=53824 ≡ 49 mod 239
16: 17616=1768+8=1768⋅1768 ≡ 49⋅49=2401 ≡ 11 mod 239
32: 17632=17616+16=17616⋅17616 ≡ 11⋅11=121 ≡ 121 mod 239
64: 17664=17632+32=17632⋅17632 ≡ 121⋅121=14641 ≡ 62 mod 239
128: 176128=17664+64=17664⋅17664 ≡ 62⋅62=3844 ≡ 20 mod 239
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 717194 mod 797.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 194 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 194 an und zerlegen 194 in eine Summer von 2er-Potenzen:
194 = 128+64+2
1: 7171=717
2: 7172=7171+1=7171⋅7171 ≡ 717⋅717=514089 ≡ 24 mod 797
4: 7174=7172+2=7172⋅7172 ≡ 24⋅24=576 ≡ 576 mod 797
8: 7178=7174+4=7174⋅7174 ≡ 576⋅576=331776 ≡ 224 mod 797
16: 71716=7178+8=7178⋅7178 ≡ 224⋅224=50176 ≡ 762 mod 797
32: 71732=71716+16=71716⋅71716 ≡ 762⋅762=580644 ≡ 428 mod 797
64: 71764=71732+32=71732⋅71732 ≡ 428⋅428=183184 ≡ 671 mod 797
128: 717128=71764+64=71764⋅71764 ≡ 671⋅671=450241 ≡ 733 mod 797
717194
= 717128+64+2
= 717128⋅71764⋅7172
≡ 733 ⋅ 671 ⋅ 24 mod 797
≡ 491843 ⋅ 24 mod 797 ≡ 94 ⋅ 24 mod 797
≡ 2256 mod 797 ≡ 662 mod 797
Es gilt also: 717194 ≡ 662 mod 797
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-79-Inverse zur Zahl 64.
Also bestimme x, so dass 64 ⋅ x ≡ 1 mod 79 gilt:
Berechnung des größten gemeinsamen Teilers von 79 und 64
| =>79 | = 1⋅64 + 15 |
| =>64 | = 4⋅15 + 4 |
| =>15 | = 3⋅4 + 3 |
| =>4 | = 1⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(79,64)=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= 4-1⋅3 | |||
| 3= 15-3⋅4 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅4 -1⋅(15 -3⋅ 4)
= 1⋅4 -1⋅15 +3⋅ 4) = -1⋅15 +4⋅ 4 (=1) |
| 4= 64-4⋅15 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅15 +4⋅(64 -4⋅ 15)
= -1⋅15 +4⋅64 -16⋅ 15) = 4⋅64 -17⋅ 15 (=1) |
| 15= 79-1⋅64 | eingesetzt in die Zeile drüber: | 1 |
= 4⋅64 -17⋅(79 -1⋅ 64)
= 4⋅64 -17⋅79 +17⋅ 64) = -17⋅79 +21⋅ 64 (=1) |
Es gilt also: ggt(79,64)=1 = -17⋅79 +21⋅64
oder wenn man -17⋅79 auf die linke Seite bringt:
1 +17⋅79 = +21⋅64
Es gilt also: 21⋅64 = 17⋅79 +1
Somit 21⋅64 = 1 mod 79
21 ist also das Inverse von 64 mod 79
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 89 und q = 67. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
