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: (15998 - 43) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(15998 - 43) mod 4 ≡ (15998 mod 4 - 43 mod 4) mod 4.
15998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 15998
= 15000
43 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 43
= 40
Somit gilt:
(15998 - 43) mod 4 ≡ (2 - 3) mod 4 ≡ -1 mod 4 ≡ 3 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (85 ⋅ 17) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(85 ⋅ 17) mod 11 ≡ (85 mod 11 ⋅ 17 mod 11) mod 11.
85 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 85 = 77 + 8 = 7 ⋅ 11 + 8 ist.
17 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 17 = 11 + 6 = 1 ⋅ 11 + 6 ist.
Somit gilt:
(85 ⋅ 17) mod 11 ≡ (8 ⋅ 6) mod 11 ≡ 48 mod 11 ≡ 4 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 21616 mod 509.
Die 16 im Exponent ist ja ein reine 2er-Potenz (24).
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. 216 -> x
2. mod(x²,509) -> 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: 2161=216
2: 2162=2161+1=2161⋅2161 ≡ 216⋅216=46656 ≡ 337 mod 509
4: 2164=2162+2=2162⋅2162 ≡ 337⋅337=113569 ≡ 62 mod 509
8: 2168=2164+4=2164⋅2164 ≡ 62⋅62=3844 ≡ 281 mod 509
16: 21616=2168+8=2168⋅2168 ≡ 281⋅281=78961 ≡ 66 mod 509
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 795131 mod 967.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 131 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 131 an und zerlegen 131 in eine Summer von 2er-Potenzen:
131 = 128+2+1
1: 7951=795
2: 7952=7951+1=7951⋅7951 ≡ 795⋅795=632025 ≡ 574 mod 967
4: 7954=7952+2=7952⋅7952 ≡ 574⋅574=329476 ≡ 696 mod 967
8: 7958=7954+4=7954⋅7954 ≡ 696⋅696=484416 ≡ 916 mod 967
16: 79516=7958+8=7958⋅7958 ≡ 916⋅916=839056 ≡ 667 mod 967
32: 79532=79516+16=79516⋅79516 ≡ 667⋅667=444889 ≡ 69 mod 967
64: 79564=79532+32=79532⋅79532 ≡ 69⋅69=4761 ≡ 893 mod 967
128: 795128=79564+64=79564⋅79564 ≡ 893⋅893=797449 ≡ 641 mod 967
795131
= 795128+2+1
= 795128⋅7952⋅7951
≡ 641 ⋅ 574 ⋅ 795 mod 967
≡ 367934 ⋅ 795 mod 967 ≡ 474 ⋅ 795 mod 967
≡ 376830 mod 967 ≡ 667 mod 967
Es gilt also: 795131 ≡ 667 mod 967
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 64.
Also bestimme x, so dass 64 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 64
| =>97 | = 1⋅64 + 33 |
| =>64 | = 1⋅33 + 31 |
| =>33 | = 1⋅31 + 2 |
| =>31 | = 15⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(97,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= 31-15⋅2 | |||
| 2= 33-1⋅31 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅31 -15⋅(33 -1⋅ 31)
= 1⋅31 -15⋅33 +15⋅ 31) = -15⋅33 +16⋅ 31 (=1) |
| 31= 64-1⋅33 | eingesetzt in die Zeile drüber: | 1 |
= -15⋅33 +16⋅(64 -1⋅ 33)
= -15⋅33 +16⋅64 -16⋅ 33) = 16⋅64 -31⋅ 33 (=1) |
| 33= 97-1⋅64 | eingesetzt in die Zeile drüber: | 1 |
= 16⋅64 -31⋅(97 -1⋅ 64)
= 16⋅64 -31⋅97 +31⋅ 64) = -31⋅97 +47⋅ 64 (=1) |
Es gilt also: ggt(97,64)=1 = -31⋅97 +47⋅64
oder wenn man -31⋅97 auf die linke Seite bringt:
1 +31⋅97 = +47⋅64
Es gilt also: 47⋅64 = 31⋅97 +1
Somit 47⋅64 = 1 mod 97
47 ist also das Inverse von 64 mod 97
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.