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: (2498 - 148) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2498 - 148) mod 5 ≡ (2498 mod 5 - 148 mod 5) mod 5.
2498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2498
= 2400
148 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 148
= 140
Somit gilt:
(2498 - 148) mod 5 ≡ (3 - 3) mod 5 ≡ 0 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (53 ⋅ 24) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(53 ⋅ 24) mod 10 ≡ (53 mod 10 ⋅ 24 mod 10) mod 10.
53 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 53 = 50 + 3 = 5 ⋅ 10 + 3 ist.
24 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 24 = 20 + 4 = 2 ⋅ 10 + 4 ist.
Somit gilt:
(53 ⋅ 24) mod 10 ≡ (3 ⋅ 4) mod 10 ≡ 12 mod 10 ≡ 2 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 20416 mod 313.
Die 16 im Exponent ist ja ein reine 2er-Potenz (24).
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. 204 -> x
2. mod(x²,313) -> 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: 2041=204
2: 2042=2041+1=2041⋅2041 ≡ 204⋅204=41616 ≡ 300 mod 313
4: 2044=2042+2=2042⋅2042 ≡ 300⋅300=90000 ≡ 169 mod 313
8: 2048=2044+4=2044⋅2044 ≡ 169⋅169=28561 ≡ 78 mod 313
16: 20416=2048+8=2048⋅2048 ≡ 78⋅78=6084 ≡ 137 mod 313
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 62861 mod 733.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 61 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 61 an und zerlegen 61 in eine Summer von 2er-Potenzen:
61 = 32+16+8+4+1
1: 6281=628
2: 6282=6281+1=6281⋅6281 ≡ 628⋅628=394384 ≡ 30 mod 733
4: 6284=6282+2=6282⋅6282 ≡ 30⋅30=900 ≡ 167 mod 733
8: 6288=6284+4=6284⋅6284 ≡ 167⋅167=27889 ≡ 35 mod 733
16: 62816=6288+8=6288⋅6288 ≡ 35⋅35=1225 ≡ 492 mod 733
32: 62832=62816+16=62816⋅62816 ≡ 492⋅492=242064 ≡ 174 mod 733
62861
= 62832+16+8+4+1
= 62832⋅62816⋅6288⋅6284⋅6281
≡ 174 ⋅ 492 ⋅ 35 ⋅ 167 ⋅ 628 mod 733
≡ 85608 ⋅ 35 ⋅ 167 ⋅ 628 mod 733 ≡ 580 ⋅ 35 ⋅ 167 ⋅ 628 mod 733
≡ 20300 ⋅ 167 ⋅ 628 mod 733 ≡ 509 ⋅ 167 ⋅ 628 mod 733
≡ 85003 ⋅ 628 mod 733 ≡ 708 ⋅ 628 mod 733
≡ 444624 mod 733 ≡ 426 mod 733
Es gilt also: 62861 ≡ 426 mod 733
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 55.
Also bestimme x, so dass 55 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 55
| =>83 | = 1⋅55 + 28 |
| =>55 | = 1⋅28 + 27 |
| =>28 | = 1⋅27 + 1 |
| =>27 | = 27⋅1 + 0 |
also gilt: ggt(83,55)=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= 28-1⋅27 | |||
| 27= 55-1⋅28 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅28 -1⋅(55 -1⋅ 28)
= 1⋅28 -1⋅55 +1⋅ 28) = -1⋅55 +2⋅ 28 (=1) |
| 28= 83-1⋅55 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅55 +2⋅(83 -1⋅ 55)
= -1⋅55 +2⋅83 -2⋅ 55) = 2⋅83 -3⋅ 55 (=1) |
Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55
oder wenn man 2⋅83 auf die linke Seite bringt:
1 -2⋅83 = -3⋅55
-3⋅55 = -2⋅83 + 1 |+83⋅55
-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1
(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1
80⋅55 = 53⋅83 + 1
Es gilt also: 80⋅55 = 53⋅83 +1
Somit 80⋅55 = 1 mod 83
80 ist also das Inverse von 55 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 101 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
