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: (216 + 77) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(216 + 77) mod 7 ≡ (216 mod 7 + 77 mod 7) mod 7.
216 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 216
= 210
77 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 77
= 70
Somit gilt:
(216 + 77) mod 7 ≡ (6 + 0) mod 7 ≡ 6 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (62 ⋅ 76) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(62 ⋅ 76) mod 11 ≡ (62 mod 11 ⋅ 76 mod 11) mod 11.
62 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 62 = 55 + 7 = 5 ⋅ 11 + 7 ist.
76 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 76 = 66 + 10 = 6 ⋅ 11 + 10 ist.
Somit gilt:
(62 ⋅ 76) mod 11 ≡ (7 ⋅ 10) mod 11 ≡ 70 mod 11 ≡ 4 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 2848 mod 353.
Die 8 im Exponent ist ja ein reine 2er-Potenz (23).
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. 284 -> x
2. mod(x²,353) -> 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: 2841=284
2: 2842=2841+1=2841⋅2841 ≡ 284⋅284=80656 ≡ 172 mod 353
4: 2844=2842+2=2842⋅2842 ≡ 172⋅172=29584 ≡ 285 mod 353
8: 2848=2844+4=2844⋅2844 ≡ 285⋅285=81225 ≡ 35 mod 353
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 518205 mod 701.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 205 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 205 an und zerlegen 205 in eine Summer von 2er-Potenzen:
205 = 128+64+8+4+1
1: 5181=518
2: 5182=5181+1=5181⋅5181 ≡ 518⋅518=268324 ≡ 542 mod 701
4: 5184=5182+2=5182⋅5182 ≡ 542⋅542=293764 ≡ 45 mod 701
8: 5188=5184+4=5184⋅5184 ≡ 45⋅45=2025 ≡ 623 mod 701
16: 51816=5188+8=5188⋅5188 ≡ 623⋅623=388129 ≡ 476 mod 701
32: 51832=51816+16=51816⋅51816 ≡ 476⋅476=226576 ≡ 153 mod 701
64: 51864=51832+32=51832⋅51832 ≡ 153⋅153=23409 ≡ 276 mod 701
128: 518128=51864+64=51864⋅51864 ≡ 276⋅276=76176 ≡ 468 mod 701
518205
= 518128+64+8+4+1
= 518128⋅51864⋅5188⋅5184⋅5181
≡ 468 ⋅ 276 ⋅ 623 ⋅ 45 ⋅ 518 mod 701
≡ 129168 ⋅ 623 ⋅ 45 ⋅ 518 mod 701 ≡ 184 ⋅ 623 ⋅ 45 ⋅ 518 mod 701
≡ 114632 ⋅ 45 ⋅ 518 mod 701 ≡ 369 ⋅ 45 ⋅ 518 mod 701
≡ 16605 ⋅ 518 mod 701 ≡ 482 ⋅ 518 mod 701
≡ 249676 mod 701 ≡ 120 mod 701
Es gilt also: 518205 ≡ 120 mod 701
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 68.
Also bestimme x, so dass 68 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 68
| =>83 | = 1⋅68 + 15 |
| =>68 | = 4⋅15 + 8 |
| =>15 | = 1⋅8 + 7 |
| =>8 | = 1⋅7 + 1 |
| =>7 | = 7⋅1 + 0 |
also gilt: ggt(83,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= 8-1⋅7 | |||
| 7= 15-1⋅8 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅8 -1⋅(15 -1⋅ 8)
= 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1) |
| 8= 68-4⋅15 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅15 +2⋅(68 -4⋅ 15)
= -1⋅15 +2⋅68 -8⋅ 15) = 2⋅68 -9⋅ 15 (=1) |
| 15= 83-1⋅68 | eingesetzt in die Zeile drüber: | 1 |
= 2⋅68 -9⋅(83 -1⋅ 68)
= 2⋅68 -9⋅83 +9⋅ 68) = -9⋅83 +11⋅ 68 (=1) |
Es gilt also: ggt(83,68)=1 = -9⋅83 +11⋅68
oder wenn man -9⋅83 auf die linke Seite bringt:
1 +9⋅83 = +11⋅68
Es gilt also: 11⋅68 = 9⋅83 +1
Somit 11⋅68 = 1 mod 83
11 ist also das Inverse von 68 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 89 und q = 83. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.