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: (25004 + 246) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(25004 + 246) mod 5 ≡ (25004 mod 5 + 246 mod 5) mod 5.
25004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 25004
= 25000
246 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 246
= 240
Somit gilt:
(25004 + 246) mod 5 ≡ (4 + 1) mod 5 ≡ 5 mod 5 ≡ 0 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (19 ⋅ 61) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(19 ⋅ 61) mod 4 ≡ (19 mod 4 ⋅ 61 mod 4) mod 4.
19 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 19 = 16 + 3 = 4 ⋅ 4 + 3 ist.
61 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 15 ⋅ 4 + 1 ist.
Somit gilt:
(19 ⋅ 61) mod 4 ≡ (3 ⋅ 1) mod 4 ≡ 3 mod 4.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 38716 mod 643.
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. 387 -> x
2. mod(x²,643) -> 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: 3871=387
2: 3872=3871+1=3871⋅3871 ≡ 387⋅387=149769 ≡ 593 mod 643
4: 3874=3872+2=3872⋅3872 ≡ 593⋅593=351649 ≡ 571 mod 643
8: 3878=3874+4=3874⋅3874 ≡ 571⋅571=326041 ≡ 40 mod 643
16: 38716=3878+8=3878⋅3878 ≡ 40⋅40=1600 ≡ 314 mod 643
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 283143 mod 719.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 143 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 143 an und zerlegen 143 in eine Summer von 2er-Potenzen:
143 = 128+8+4+2+1
1: 2831=283
2: 2832=2831+1=2831⋅2831 ≡ 283⋅283=80089 ≡ 280 mod 719
4: 2834=2832+2=2832⋅2832 ≡ 280⋅280=78400 ≡ 29 mod 719
8: 2838=2834+4=2834⋅2834 ≡ 29⋅29=841 ≡ 122 mod 719
16: 28316=2838+8=2838⋅2838 ≡ 122⋅122=14884 ≡ 504 mod 719
32: 28332=28316+16=28316⋅28316 ≡ 504⋅504=254016 ≡ 209 mod 719
64: 28364=28332+32=28332⋅28332 ≡ 209⋅209=43681 ≡ 541 mod 719
128: 283128=28364+64=28364⋅28364 ≡ 541⋅541=292681 ≡ 48 mod 719
283143
= 283128+8+4+2+1
= 283128⋅2838⋅2834⋅2832⋅2831
≡ 48 ⋅ 122 ⋅ 29 ⋅ 280 ⋅ 283 mod 719
≡ 5856 ⋅ 29 ⋅ 280 ⋅ 283 mod 719 ≡ 104 ⋅ 29 ⋅ 280 ⋅ 283 mod 719
≡ 3016 ⋅ 280 ⋅ 283 mod 719 ≡ 140 ⋅ 280 ⋅ 283 mod 719
≡ 39200 ⋅ 283 mod 719 ≡ 374 ⋅ 283 mod 719
≡ 105842 mod 719 ≡ 149 mod 719
Es gilt also: 283143 ≡ 149 mod 719
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 25.
Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 25
| =>67 | = 2⋅25 + 17 |
| =>25 | = 1⋅17 + 8 |
| =>17 | = 2⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(67,25)=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= 17-2⋅8 | |||
| 8= 25-1⋅17 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅17 -2⋅(25 -1⋅ 17)
= 1⋅17 -2⋅25 +2⋅ 17) = -2⋅25 +3⋅ 17 (=1) |
| 17= 67-2⋅25 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅25 +3⋅(67 -2⋅ 25)
= -2⋅25 +3⋅67 -6⋅ 25) = 3⋅67 -8⋅ 25 (=1) |
Es gilt also: ggt(67,25)=1 = 3⋅67 -8⋅25
oder wenn man 3⋅67 auf die linke Seite bringt:
1 -3⋅67 = -8⋅25
-8⋅25 = -3⋅67 + 1 |+67⋅25
-8⋅25 + 67⋅25 = -3⋅67 + 67⋅25 + 1
(-8 + 67) ⋅ 25 = (-3 + 25) ⋅ 67 + 1
59⋅25 = 22⋅67 + 1
Es gilt also: 59⋅25 = 22⋅67 +1
Somit 59⋅25 = 1 mod 67
59 ist also das Inverse von 25 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 71 und q = 101. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
