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: (1598 - 2000) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1598 - 2000) mod 4 ≡ (1598 mod 4 - 2000 mod 4) mod 4.
1598 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 1598
= 1500
2000 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 2000
= 2000
Somit gilt:
(1598 - 2000) mod 4 ≡ (2 - 0) mod 4 ≡ 2 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (87 ⋅ 24) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(87 ⋅ 24) mod 5 ≡ (87 mod 5 ⋅ 24 mod 5) mod 5.
87 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 87 = 85 + 2 = 17 ⋅ 5 + 2 ist.
24 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 24 = 20 + 4 = 4 ⋅ 5 + 4 ist.
Somit gilt:
(87 ⋅ 24) mod 5 ≡ (2 ⋅ 4) mod 5 ≡ 8 mod 5 ≡ 3 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 35564 mod 419.
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. 355 -> x
2. mod(x²,419) -> 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: 3551=355
2: 3552=3551+1=3551⋅3551 ≡ 355⋅355=126025 ≡ 325 mod 419
4: 3554=3552+2=3552⋅3552 ≡ 325⋅325=105625 ≡ 37 mod 419
8: 3558=3554+4=3554⋅3554 ≡ 37⋅37=1369 ≡ 112 mod 419
16: 35516=3558+8=3558⋅3558 ≡ 112⋅112=12544 ≡ 393 mod 419
32: 35532=35516+16=35516⋅35516 ≡ 393⋅393=154449 ≡ 257 mod 419
64: 35564=35532+32=35532⋅35532 ≡ 257⋅257=66049 ≡ 266 mod 419
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 251142 mod 673.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 142 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 142 an und zerlegen 142 in eine Summer von 2er-Potenzen:
142 = 128+8+4+2
1: 2511=251
2: 2512=2511+1=2511⋅2511 ≡ 251⋅251=63001 ≡ 412 mod 673
4: 2514=2512+2=2512⋅2512 ≡ 412⋅412=169744 ≡ 148 mod 673
8: 2518=2514+4=2514⋅2514 ≡ 148⋅148=21904 ≡ 368 mod 673
16: 25116=2518+8=2518⋅2518 ≡ 368⋅368=135424 ≡ 151 mod 673
32: 25132=25116+16=25116⋅25116 ≡ 151⋅151=22801 ≡ 592 mod 673
64: 25164=25132+32=25132⋅25132 ≡ 592⋅592=350464 ≡ 504 mod 673
128: 251128=25164+64=25164⋅25164 ≡ 504⋅504=254016 ≡ 295 mod 673
251142
= 251128+8+4+2
= 251128⋅2518⋅2514⋅2512
≡ 295 ⋅ 368 ⋅ 148 ⋅ 412 mod 673
≡ 108560 ⋅ 148 ⋅ 412 mod 673 ≡ 207 ⋅ 148 ⋅ 412 mod 673
≡ 30636 ⋅ 412 mod 673 ≡ 351 ⋅ 412 mod 673
≡ 144612 mod 673 ≡ 590 mod 673
Es gilt also: 251142 ≡ 590 mod 673
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-53-Inverse zur Zahl 44.
Also bestimme x, so dass 44 ⋅ x ≡ 1 mod 53 gilt:
Berechnung des größten gemeinsamen Teilers von 53 und 44
| =>53 | = 1⋅44 + 9 |
| =>44 | = 4⋅9 + 8 |
| =>9 | = 1⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(53,44)=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= 9-1⋅8 | |||
| 8= 44-4⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -1⋅(44 -4⋅ 9)
= 1⋅9 -1⋅44 +4⋅ 9) = -1⋅44 +5⋅ 9 (=1) |
| 9= 53-1⋅44 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅44 +5⋅(53 -1⋅ 44)
= -1⋅44 +5⋅53 -5⋅ 44) = 5⋅53 -6⋅ 44 (=1) |
Es gilt also: ggt(53,44)=1 = 5⋅53 -6⋅44
oder wenn man 5⋅53 auf die linke Seite bringt:
1 -5⋅53 = -6⋅44
-6⋅44 = -5⋅53 + 1 |+53⋅44
-6⋅44 + 53⋅44 = -5⋅53 + 53⋅44 + 1
(-6 + 53) ⋅ 44 = (-5 + 44) ⋅ 53 + 1
47⋅44 = 39⋅53 + 1
Es gilt also: 47⋅44 = 39⋅53 +1
Somit 47⋅44 = 1 mod 53
47 ist also das Inverse von 44 mod 53
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 61 und q = 71. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
