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: (1998 + 796) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1998 + 796) mod 4 ≡ (1998 mod 4 + 796 mod 4) mod 4.
1998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 1998
= 1900
796 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 796
= 700
Somit gilt:
(1998 + 796) mod 4 ≡ (2 + 0) mod 4 ≡ 2 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (92 ⋅ 47) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(92 ⋅ 47) mod 8 ≡ (92 mod 8 ⋅ 47 mod 8) mod 8.
92 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 92 = 88 + 4 = 11 ⋅ 8 + 4 ist.
47 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 47 = 40 + 7 = 5 ⋅ 8 + 7 ist.
Somit gilt:
(92 ⋅ 47) mod 8 ≡ (4 ⋅ 7) mod 8 ≡ 28 mod 8 ≡ 4 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 44232 mod 977.
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. 442 -> x
2. mod(x²,977) -> 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: 4421=442
2: 4422=4421+1=4421⋅4421 ≡ 442⋅442=195364 ≡ 941 mod 977
4: 4424=4422+2=4422⋅4422 ≡ 941⋅941=885481 ≡ 319 mod 977
8: 4428=4424+4=4424⋅4424 ≡ 319⋅319=101761 ≡ 153 mod 977
16: 44216=4428+8=4428⋅4428 ≡ 153⋅153=23409 ≡ 938 mod 977
32: 44232=44216+16=44216⋅44216 ≡ 938⋅938=879844 ≡ 544 mod 977
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 409224 mod 467.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 224 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 224 an und zerlegen 224 in eine Summer von 2er-Potenzen:
224 = 128+64+32
1: 4091=409
2: 4092=4091+1=4091⋅4091 ≡ 409⋅409=167281 ≡ 95 mod 467
4: 4094=4092+2=4092⋅4092 ≡ 95⋅95=9025 ≡ 152 mod 467
8: 4098=4094+4=4094⋅4094 ≡ 152⋅152=23104 ≡ 221 mod 467
16: 40916=4098+8=4098⋅4098 ≡ 221⋅221=48841 ≡ 273 mod 467
32: 40932=40916+16=40916⋅40916 ≡ 273⋅273=74529 ≡ 276 mod 467
64: 40964=40932+32=40932⋅40932 ≡ 276⋅276=76176 ≡ 55 mod 467
128: 409128=40964+64=40964⋅40964 ≡ 55⋅55=3025 ≡ 223 mod 467
409224
= 409128+64+32
= 409128⋅40964⋅40932
≡ 223 ⋅ 55 ⋅ 276 mod 467
≡ 12265 ⋅ 276 mod 467 ≡ 123 ⋅ 276 mod 467
≡ 33948 mod 467 ≡ 324 mod 467
Es gilt also: 409224 ≡ 324 mod 467
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-53-Inverse zur Zahl 31.
Also bestimme x, so dass 31 ⋅ x ≡ 1 mod 53 gilt:
Berechnung des größten gemeinsamen Teilers von 53 und 31
| =>53 | = 1⋅31 + 22 |
| =>31 | = 1⋅22 + 9 |
| =>22 | = 2⋅9 + 4 |
| =>9 | = 2⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(53,31)=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-2⋅4 | |||
| 4= 22-2⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -2⋅(22 -2⋅ 9)
= 1⋅9 -2⋅22 +4⋅ 9) = -2⋅22 +5⋅ 9 (=1) |
| 9= 31-1⋅22 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅22 +5⋅(31 -1⋅ 22)
= -2⋅22 +5⋅31 -5⋅ 22) = 5⋅31 -7⋅ 22 (=1) |
| 22= 53-1⋅31 | eingesetzt in die Zeile drüber: | 1 |
= 5⋅31 -7⋅(53 -1⋅ 31)
= 5⋅31 -7⋅53 +7⋅ 31) = -7⋅53 +12⋅ 31 (=1) |
Es gilt also: ggt(53,31)=1 = -7⋅53 +12⋅31
oder wenn man -7⋅53 auf die linke Seite bringt:
1 +7⋅53 = +12⋅31
Es gilt also: 12⋅31 = 7⋅53 +1
Somit 12⋅31 = 1 mod 53
12 ist also das Inverse von 31 mod 53
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
