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: (21006 - 21000) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(21006 - 21000) mod 7 ≡ (21006 mod 7 - 21000 mod 7) mod 7.
21006 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 21006
= 21000
21000 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 21000
= 21000
Somit gilt:
(21006 - 21000) mod 7 ≡ (6 - 0) mod 7 ≡ 6 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (62 ⋅ 62) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(62 ⋅ 62) mod 11 ≡ (62 mod 11 ⋅ 62 mod 11) mod 11.
62 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 62 = 55 + 7 = 5 ⋅ 11 + 7 ist.
62 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 62 = 55 + 7 = 5 ⋅ 11 + 7 ist.
Somit gilt:
(62 ⋅ 62) mod 11 ≡ (7 ⋅ 7) mod 11 ≡ 49 mod 11 ≡ 5 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 161128 mod 269.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 161 -> x
2. mod(x²,269) -> 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: 1611=161
2: 1612=1611+1=1611⋅1611 ≡ 161⋅161=25921 ≡ 97 mod 269
4: 1614=1612+2=1612⋅1612 ≡ 97⋅97=9409 ≡ 263 mod 269
8: 1618=1614+4=1614⋅1614 ≡ 263⋅263=69169 ≡ 36 mod 269
16: 16116=1618+8=1618⋅1618 ≡ 36⋅36=1296 ≡ 220 mod 269
32: 16132=16116+16=16116⋅16116 ≡ 220⋅220=48400 ≡ 249 mod 269
64: 16164=16132+32=16132⋅16132 ≡ 249⋅249=62001 ≡ 131 mod 269
128: 161128=16164+64=16164⋅16164 ≡ 131⋅131=17161 ≡ 214 mod 269
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 295212 mod 307.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 212 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 212 an und zerlegen 212 in eine Summer von 2er-Potenzen:
212 = 128+64+16+4
1: 2951=295
2: 2952=2951+1=2951⋅2951 ≡ 295⋅295=87025 ≡ 144 mod 307
4: 2954=2952+2=2952⋅2952 ≡ 144⋅144=20736 ≡ 167 mod 307
8: 2958=2954+4=2954⋅2954 ≡ 167⋅167=27889 ≡ 259 mod 307
16: 29516=2958+8=2958⋅2958 ≡ 259⋅259=67081 ≡ 155 mod 307
32: 29532=29516+16=29516⋅29516 ≡ 155⋅155=24025 ≡ 79 mod 307
64: 29564=29532+32=29532⋅29532 ≡ 79⋅79=6241 ≡ 101 mod 307
128: 295128=29564+64=29564⋅29564 ≡ 101⋅101=10201 ≡ 70 mod 307
295212
= 295128+64+16+4
= 295128⋅29564⋅29516⋅2954
≡ 70 ⋅ 101 ⋅ 155 ⋅ 167 mod 307
≡ 7070 ⋅ 155 ⋅ 167 mod 307 ≡ 9 ⋅ 155 ⋅ 167 mod 307
≡ 1395 ⋅ 167 mod 307 ≡ 167 ⋅ 167 mod 307
≡ 27889 mod 307 ≡ 259 mod 307
Es gilt also: 295212 ≡ 259 mod 307
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-79-Inverse zur Zahl 68.
Also bestimme x, so dass 68 ⋅ x ≡ 1 mod 79 gilt:
Berechnung des größten gemeinsamen Teilers von 79 und 68
| =>79 | = 1⋅68 + 11 |
| =>68 | = 6⋅11 + 2 |
| =>11 | = 5⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(79,68)=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= 11-5⋅2 | |||
| 2= 68-6⋅11 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅11 -5⋅(68 -6⋅ 11)
= 1⋅11 -5⋅68 +30⋅ 11) = -5⋅68 +31⋅ 11 (=1) |
| 11= 79-1⋅68 | eingesetzt in die Zeile drüber: | 1 |
= -5⋅68 +31⋅(79 -1⋅ 68)
= -5⋅68 +31⋅79 -31⋅ 68) = 31⋅79 -36⋅ 68 (=1) |
Es gilt also: ggt(79,68)=1 = 31⋅79 -36⋅68
oder wenn man 31⋅79 auf die linke Seite bringt:
1 -31⋅79 = -36⋅68
-36⋅68 = -31⋅79 + 1 |+79⋅68
-36⋅68 + 79⋅68 = -31⋅79 + 79⋅68 + 1
(-36 + 79) ⋅ 68 = (-31 + 68) ⋅ 79 + 1
43⋅68 = 37⋅79 + 1
Es gilt also: 43⋅68 = 37⋅79 +1
Somit 43⋅68 = 1 mod 79
43 ist also das Inverse von 68 mod 79
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 59. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
