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: (1197 + 18000) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1197 + 18000) mod 6 ≡ (1197 mod 6 + 18000 mod 6) mod 6.
1197 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 1197
= 1200
18000 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 18000
= 18000
Somit gilt:
(1197 + 18000) mod 6 ≡ (3 + 0) mod 6 ≡ 3 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (65 ⋅ 66) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(65 ⋅ 66) mod 6 ≡ (65 mod 6 ⋅ 66 mod 6) mod 6.
65 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 65 = 60 + 5 = 10 ⋅ 6 + 5 ist.
66 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 66 = 66 + 0 = 11 ⋅ 6 + 0 ist.
Somit gilt:
(65 ⋅ 66) mod 6 ≡ (5 ⋅ 0) mod 6 ≡ 0 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 2538 mod 727.
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. 253 -> x
2. mod(x²,727) -> 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: 2531=253
2: 2532=2531+1=2531⋅2531 ≡ 253⋅253=64009 ≡ 33 mod 727
4: 2534=2532+2=2532⋅2532 ≡ 33⋅33=1089 ≡ 362 mod 727
8: 2538=2534+4=2534⋅2534 ≡ 362⋅362=131044 ≡ 184 mod 727
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 95109 mod 251.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 109 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 109 an und zerlegen 109 in eine Summer von 2er-Potenzen:
109 = 64+32+8+4+1
1: 951=95
2: 952=951+1=951⋅951 ≡ 95⋅95=9025 ≡ 240 mod 251
4: 954=952+2=952⋅952 ≡ 240⋅240=57600 ≡ 121 mod 251
8: 958=954+4=954⋅954 ≡ 121⋅121=14641 ≡ 83 mod 251
16: 9516=958+8=958⋅958 ≡ 83⋅83=6889 ≡ 112 mod 251
32: 9532=9516+16=9516⋅9516 ≡ 112⋅112=12544 ≡ 245 mod 251
64: 9564=9532+32=9532⋅9532 ≡ 245⋅245=60025 ≡ 36 mod 251
95109
= 9564+32+8+4+1
= 9564⋅9532⋅958⋅954⋅951
≡ 36 ⋅ 245 ⋅ 83 ⋅ 121 ⋅ 95 mod 251
≡ 8820 ⋅ 83 ⋅ 121 ⋅ 95 mod 251 ≡ 35 ⋅ 83 ⋅ 121 ⋅ 95 mod 251
≡ 2905 ⋅ 121 ⋅ 95 mod 251 ≡ 144 ⋅ 121 ⋅ 95 mod 251
≡ 17424 ⋅ 95 mod 251 ≡ 105 ⋅ 95 mod 251
≡ 9975 mod 251 ≡ 186 mod 251
Es gilt also: 95109 ≡ 186 mod 251
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 59.
Also bestimme x, so dass 59 ⋅ x ≡ 1 mod 73 gilt:
Berechnung des größten gemeinsamen Teilers von 73 und 59
| =>73 | = 1⋅59 + 14 |
| =>59 | = 4⋅14 + 3 |
| =>14 | = 4⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(73,59)=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= 3-1⋅2 | |||
| 2= 14-4⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(14 -4⋅ 3)
= 1⋅3 -1⋅14 +4⋅ 3) = -1⋅14 +5⋅ 3 (=1) |
| 3= 59-4⋅14 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅14 +5⋅(59 -4⋅ 14)
= -1⋅14 +5⋅59 -20⋅ 14) = 5⋅59 -21⋅ 14 (=1) |
| 14= 73-1⋅59 | eingesetzt in die Zeile drüber: | 1 |
= 5⋅59 -21⋅(73 -1⋅ 59)
= 5⋅59 -21⋅73 +21⋅ 59) = -21⋅73 +26⋅ 59 (=1) |
Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59
oder wenn man -21⋅73 auf die linke Seite bringt:
1 +21⋅73 = +26⋅59
Es gilt also: 26⋅59 = 21⋅73 +1
Somit 26⋅59 = 1 mod 73
26 ist also das Inverse von 59 mod 73
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 47 und q = 59. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
