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: (153 - 601) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(153 - 601) mod 3 ≡ (153 mod 3 - 601 mod 3) mod 3.
153 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 153
= 150
601 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 601
= 600
Somit gilt:
(153 - 601) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (89 ⋅ 79) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(89 ⋅ 79) mod 9 ≡ (89 mod 9 ⋅ 79 mod 9) mod 9.
89 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 89 = 81 + 8 = 9 ⋅ 9 + 8 ist.
79 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 79 = 72 + 7 = 8 ⋅ 9 + 7 ist.
Somit gilt:
(89 ⋅ 79) mod 9 ≡ (8 ⋅ 7) mod 9 ≡ 56 mod 9 ≡ 2 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 17764 mod 449.
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. 177 -> x
2. mod(x²,449) -> 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: 1771=177
2: 1772=1771+1=1771⋅1771 ≡ 177⋅177=31329 ≡ 348 mod 449
4: 1774=1772+2=1772⋅1772 ≡ 348⋅348=121104 ≡ 323 mod 449
8: 1778=1774+4=1774⋅1774 ≡ 323⋅323=104329 ≡ 161 mod 449
16: 17716=1778+8=1778⋅1778 ≡ 161⋅161=25921 ≡ 328 mod 449
32: 17732=17716+16=17716⋅17716 ≡ 328⋅328=107584 ≡ 273 mod 449
64: 17764=17732+32=17732⋅17732 ≡ 273⋅273=74529 ≡ 444 mod 449
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 611189 mod 857.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 189 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 189 an und zerlegen 189 in eine Summer von 2er-Potenzen:
189 = 128+32+16+8+4+1
1: 6111=611
2: 6112=6111+1=6111⋅6111 ≡ 611⋅611=373321 ≡ 526 mod 857
4: 6114=6112+2=6112⋅6112 ≡ 526⋅526=276676 ≡ 722 mod 857
8: 6118=6114+4=6114⋅6114 ≡ 722⋅722=521284 ≡ 228 mod 857
16: 61116=6118+8=6118⋅6118 ≡ 228⋅228=51984 ≡ 564 mod 857
32: 61132=61116+16=61116⋅61116 ≡ 564⋅564=318096 ≡ 149 mod 857
64: 61164=61132+32=61132⋅61132 ≡ 149⋅149=22201 ≡ 776 mod 857
128: 611128=61164+64=61164⋅61164 ≡ 776⋅776=602176 ≡ 562 mod 857
611189
= 611128+32+16+8+4+1
= 611128⋅61132⋅61116⋅6118⋅6114⋅6111
≡ 562 ⋅ 149 ⋅ 564 ⋅ 228 ⋅ 722 ⋅ 611 mod 857
≡ 83738 ⋅ 564 ⋅ 228 ⋅ 722 ⋅ 611 mod 857 ≡ 609 ⋅ 564 ⋅ 228 ⋅ 722 ⋅ 611 mod 857
≡ 343476 ⋅ 228 ⋅ 722 ⋅ 611 mod 857 ≡ 676 ⋅ 228 ⋅ 722 ⋅ 611 mod 857
≡ 154128 ⋅ 722 ⋅ 611 mod 857 ≡ 725 ⋅ 722 ⋅ 611 mod 857
≡ 523450 ⋅ 611 mod 857 ≡ 680 ⋅ 611 mod 857
≡ 415480 mod 857 ≡ 692 mod 857
Es gilt also: 611189 ≡ 692 mod 857
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 29.
Also bestimme x, so dass 29 ⋅ x ≡ 1 mod 61 gilt:
Berechnung des größten gemeinsamen Teilers von 61 und 29
| =>61 | = 2⋅29 + 3 |
| =>29 | = 9⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(61,29)=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= 29-9⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(29 -9⋅ 3)
= 1⋅3 -1⋅29 +9⋅ 3) = -1⋅29 +10⋅ 3 (=1) |
| 3= 61-2⋅29 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅29 +10⋅(61 -2⋅ 29)
= -1⋅29 +10⋅61 -20⋅ 29) = 10⋅61 -21⋅ 29 (=1) |
Es gilt also: ggt(61,29)=1 = 10⋅61 -21⋅29
oder wenn man 10⋅61 auf die linke Seite bringt:
1 -10⋅61 = -21⋅29
-21⋅29 = -10⋅61 + 1 |+61⋅29
-21⋅29 + 61⋅29 = -10⋅61 + 61⋅29 + 1
(-21 + 61) ⋅ 29 = (-10 + 29) ⋅ 61 + 1
40⋅29 = 19⋅61 + 1
Es gilt also: 40⋅29 = 19⋅61 +1
Somit 40⋅29 = 1 mod 61
40 ist also das Inverse von 29 mod 61
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 61 und q = 47. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
