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: (121 + 11996) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(121 + 11996) mod 4 ≡ (121 mod 4 + 11996 mod 4) mod 4.
121 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 121
= 120
11996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 11996
= 11000
Somit gilt:
(121 + 11996) mod 4 ≡ (1 + 0) mod 4 ≡ 1 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (82 ⋅ 76) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(82 ⋅ 76) mod 6 ≡ (82 mod 6 ⋅ 76 mod 6) mod 6.
82 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 82 = 78 + 4 = 13 ⋅ 6 + 4 ist.
76 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 76 = 72 + 4 = 12 ⋅ 6 + 4 ist.
Somit gilt:
(82 ⋅ 76) mod 6 ≡ (4 ⋅ 4) mod 6 ≡ 16 mod 6 ≡ 4 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 28564 mod 887.
Die 64 im Exponent ist ja ein reine 2er-Potenz (26).
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. 285 -> x
2. mod(x²,887) -> 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: 2851=285
2: 2852=2851+1=2851⋅2851 ≡ 285⋅285=81225 ≡ 508 mod 887
4: 2854=2852+2=2852⋅2852 ≡ 508⋅508=258064 ≡ 834 mod 887
8: 2858=2854+4=2854⋅2854 ≡ 834⋅834=695556 ≡ 148 mod 887
16: 28516=2858+8=2858⋅2858 ≡ 148⋅148=21904 ≡ 616 mod 887
32: 28532=28516+16=28516⋅28516 ≡ 616⋅616=379456 ≡ 707 mod 887
64: 28564=28532+32=28532⋅28532 ≡ 707⋅707=499849 ≡ 468 mod 887
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 237102 mod 431.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 102 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 102 an und zerlegen 102 in eine Summer von 2er-Potenzen:
102 = 64+32+4+2
1: 2371=237
2: 2372=2371+1=2371⋅2371 ≡ 237⋅237=56169 ≡ 139 mod 431
4: 2374=2372+2=2372⋅2372 ≡ 139⋅139=19321 ≡ 357 mod 431
8: 2378=2374+4=2374⋅2374 ≡ 357⋅357=127449 ≡ 304 mod 431
16: 23716=2378+8=2378⋅2378 ≡ 304⋅304=92416 ≡ 182 mod 431
32: 23732=23716+16=23716⋅23716 ≡ 182⋅182=33124 ≡ 368 mod 431
64: 23764=23732+32=23732⋅23732 ≡ 368⋅368=135424 ≡ 90 mod 431
237102
= 23764+32+4+2
= 23764⋅23732⋅2374⋅2372
≡ 90 ⋅ 368 ⋅ 357 ⋅ 139 mod 431
≡ 33120 ⋅ 357 ⋅ 139 mod 431 ≡ 364 ⋅ 357 ⋅ 139 mod 431
≡ 129948 ⋅ 139 mod 431 ≡ 217 ⋅ 139 mod 431
≡ 30163 mod 431 ≡ 424 mod 431
Es gilt also: 237102 ≡ 424 mod 431
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 39.
Also bestimme x, so dass 39 ⋅ x ≡ 1 mod 73 gilt:
Berechnung des größten gemeinsamen Teilers von 73 und 39
| =>73 | = 1⋅39 + 34 |
| =>39 | = 1⋅34 + 5 |
| =>34 | = 6⋅5 + 4 |
| =>5 | = 1⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(73,39)=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= 5-1⋅4 | |||
| 4= 34-6⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -1⋅(34 -6⋅ 5)
= 1⋅5 -1⋅34 +6⋅ 5) = -1⋅34 +7⋅ 5 (=1) |
| 5= 39-1⋅34 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅34 +7⋅(39 -1⋅ 34)
= -1⋅34 +7⋅39 -7⋅ 34) = 7⋅39 -8⋅ 34 (=1) |
| 34= 73-1⋅39 | eingesetzt in die Zeile drüber: | 1 |
= 7⋅39 -8⋅(73 -1⋅ 39)
= 7⋅39 -8⋅73 +8⋅ 39) = -8⋅73 +15⋅ 39 (=1) |
Es gilt also: ggt(73,39)=1 = -8⋅73 +15⋅39
oder wenn man -8⋅73 auf die linke Seite bringt:
1 +8⋅73 = +15⋅39
Es gilt also: 15⋅39 = 8⋅73 +1
Somit 15⋅39 = 1 mod 73
15 ist also das Inverse von 39 mod 73
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 41. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.