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: (26994 + 86) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(26994 + 86) mod 9 ≡ (26994 mod 9 + 86 mod 9) mod 9.
26994 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 26994
= 27000
86 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 86
= 90
Somit gilt:
(26994 + 86) mod 9 ≡ (3 + 5) mod 9 ≡ 8 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (98 ⋅ 91) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(98 ⋅ 91) mod 6 ≡ (98 mod 6 ⋅ 91 mod 6) mod 6.
98 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 98 = 96 + 2 = 16 ⋅ 6 + 2 ist.
91 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 91 = 90 + 1 = 15 ⋅ 6 + 1 ist.
Somit gilt:
(98 ⋅ 91) mod 6 ≡ (2 ⋅ 1) mod 6 ≡ 2 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 26532 mod 311.
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. 265 -> x
2. mod(x²,311) -> 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: 2651=265
2: 2652=2651+1=2651⋅2651 ≡ 265⋅265=70225 ≡ 250 mod 311
4: 2654=2652+2=2652⋅2652 ≡ 250⋅250=62500 ≡ 300 mod 311
8: 2658=2654+4=2654⋅2654 ≡ 300⋅300=90000 ≡ 121 mod 311
16: 26516=2658+8=2658⋅2658 ≡ 121⋅121=14641 ≡ 24 mod 311
32: 26532=26516+16=26516⋅26516 ≡ 24⋅24=576 ≡ 265 mod 311
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 793223 mod 919.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 223 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 223 an und zerlegen 223 in eine Summer von 2er-Potenzen:
223 = 128+64+16+8+4+2+1
1: 7931=793
2: 7932=7931+1=7931⋅7931 ≡ 793⋅793=628849 ≡ 253 mod 919
4: 7934=7932+2=7932⋅7932 ≡ 253⋅253=64009 ≡ 598 mod 919
8: 7938=7934+4=7934⋅7934 ≡ 598⋅598=357604 ≡ 113 mod 919
16: 79316=7938+8=7938⋅7938 ≡ 113⋅113=12769 ≡ 822 mod 919
32: 79332=79316+16=79316⋅79316 ≡ 822⋅822=675684 ≡ 219 mod 919
64: 79364=79332+32=79332⋅79332 ≡ 219⋅219=47961 ≡ 173 mod 919
128: 793128=79364+64=79364⋅79364 ≡ 173⋅173=29929 ≡ 521 mod 919
793223
= 793128+64+16+8+4+2+1
= 793128⋅79364⋅79316⋅7938⋅7934⋅7932⋅7931
≡ 521 ⋅ 173 ⋅ 822 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 90133 ⋅ 822 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919 ≡ 71 ⋅ 822 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 58362 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919 ≡ 465 ⋅ 113 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 52545 ⋅ 598 ⋅ 253 ⋅ 793 mod 919 ≡ 162 ⋅ 598 ⋅ 253 ⋅ 793 mod 919
≡ 96876 ⋅ 253 ⋅ 793 mod 919 ≡ 381 ⋅ 253 ⋅ 793 mod 919
≡ 96393 ⋅ 793 mod 919 ≡ 817 ⋅ 793 mod 919
≡ 647881 mod 919 ≡ 905 mod 919
Es gilt also: 793223 ≡ 905 mod 919
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 62.
Also bestimme x, so dass 62 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 62
| =>71 | = 1⋅62 + 9 |
| =>62 | = 6⋅9 + 8 |
| =>9 | = 1⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(71,62)=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= 9-1⋅8 | |||
| 8= 62-6⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -1⋅(62 -6⋅ 9)
= 1⋅9 -1⋅62 +6⋅ 9) = -1⋅62 +7⋅ 9 (=1) |
| 9= 71-1⋅62 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅62 +7⋅(71 -1⋅ 62)
= -1⋅62 +7⋅71 -7⋅ 62) = 7⋅71 -8⋅ 62 (=1) |
Es gilt also: ggt(71,62)=1 = 7⋅71 -8⋅62
oder wenn man 7⋅71 auf die linke Seite bringt:
1 -7⋅71 = -8⋅62
-8⋅62 = -7⋅71 + 1 |+71⋅62
-8⋅62 + 71⋅62 = -7⋅71 + 71⋅62 + 1
(-8 + 71) ⋅ 62 = (-7 + 62) ⋅ 71 + 1
63⋅62 = 55⋅71 + 1
Es gilt also: 63⋅62 = 55⋅71 +1
Somit 63⋅62 = 1 mod 71
63 ist also das Inverse von 62 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 79. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
