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: (1499 - 47) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1499 - 47) mod 5 ≡ (1499 mod 5 - 47 mod 5) mod 5.
1499 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1499
= 1400
47 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 47
= 40
Somit gilt:
(1499 - 47) mod 5 ≡ (4 - 2) mod 5 ≡ 2 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (39 ⋅ 78) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(39 ⋅ 78) mod 11 ≡ (39 mod 11 ⋅ 78 mod 11) mod 11.
39 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 39 = 33 + 6 = 3 ⋅ 11 + 6 ist.
78 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 78 = 77 + 1 = 7 ⋅ 11 + 1 ist.
Somit gilt:
(39 ⋅ 78) mod 11 ≡ (6 ⋅ 1) mod 11 ≡ 6 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 35516 mod 881.
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. 355 -> x
2. mod(x²,881) -> 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: 3551=355
2: 3552=3551+1=3551⋅3551 ≡ 355⋅355=126025 ≡ 42 mod 881
4: 3554=3552+2=3552⋅3552 ≡ 42⋅42=1764 ≡ 2 mod 881
8: 3558=3554+4=3554⋅3554 ≡ 2⋅2=4 ≡ 4 mod 881
16: 35516=3558+8=3558⋅3558 ≡ 4⋅4=16 ≡ 16 mod 881
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 170188 mod 461.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 188 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 188 an und zerlegen 188 in eine Summer von 2er-Potenzen:
188 = 128+32+16+8+4
1: 1701=170
2: 1702=1701+1=1701⋅1701 ≡ 170⋅170=28900 ≡ 318 mod 461
4: 1704=1702+2=1702⋅1702 ≡ 318⋅318=101124 ≡ 165 mod 461
8: 1708=1704+4=1704⋅1704 ≡ 165⋅165=27225 ≡ 26 mod 461
16: 17016=1708+8=1708⋅1708 ≡ 26⋅26=676 ≡ 215 mod 461
32: 17032=17016+16=17016⋅17016 ≡ 215⋅215=46225 ≡ 125 mod 461
64: 17064=17032+32=17032⋅17032 ≡ 125⋅125=15625 ≡ 412 mod 461
128: 170128=17064+64=17064⋅17064 ≡ 412⋅412=169744 ≡ 96 mod 461
170188
= 170128+32+16+8+4
= 170128⋅17032⋅17016⋅1708⋅1704
≡ 96 ⋅ 125 ⋅ 215 ⋅ 26 ⋅ 165 mod 461
≡ 12000 ⋅ 215 ⋅ 26 ⋅ 165 mod 461 ≡ 14 ⋅ 215 ⋅ 26 ⋅ 165 mod 461
≡ 3010 ⋅ 26 ⋅ 165 mod 461 ≡ 244 ⋅ 26 ⋅ 165 mod 461
≡ 6344 ⋅ 165 mod 461 ≡ 351 ⋅ 165 mod 461
≡ 57915 mod 461 ≡ 290 mod 461
Es gilt also: 170188 ≡ 290 mod 461
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 67.
Also bestimme x, so dass 67 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 67
| =>71 | = 1⋅67 + 4 |
| =>67 | = 16⋅4 + 3 |
| =>4 | = 1⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(71,67)=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= 67-16⋅4 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅4 -1⋅(67 -16⋅ 4)
= 1⋅4 -1⋅67 +16⋅ 4) = -1⋅67 +17⋅ 4 (=1) |
| 4= 71-1⋅67 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅67 +17⋅(71 -1⋅ 67)
= -1⋅67 +17⋅71 -17⋅ 67) = 17⋅71 -18⋅ 67 (=1) |
Es gilt also: ggt(71,67)=1 = 17⋅71 -18⋅67
oder wenn man 17⋅71 auf die linke Seite bringt:
1 -17⋅71 = -18⋅67
-18⋅67 = -17⋅71 + 1 |+71⋅67
-18⋅67 + 71⋅67 = -17⋅71 + 71⋅67 + 1
(-18 + 71) ⋅ 67 = (-17 + 67) ⋅ 71 + 1
53⋅67 = 50⋅71 + 1
Es gilt also: 53⋅67 = 50⋅71 +1
Somit 53⋅67 = 1 mod 71
53 ist also das Inverse von 67 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 41 und q = 67. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
