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 + 1200) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1598 + 1200) mod 4 ≡ (1598 mod 4 + 1200 mod 4) mod 4.
1598 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 1598
= 1500
1200 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1200
= 1200
Somit gilt:
(1598 + 1200) mod 4 ≡ (2 + 0) mod 4 ≡ 2 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (39 ⋅ 37) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(39 ⋅ 37) mod 6 ≡ (39 mod 6 ⋅ 37 mod 6) mod 6.
39 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 39 = 36 + 3 = 6 ⋅ 6 + 3 ist.
37 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 37 = 36 + 1 = 6 ⋅ 6 + 1 ist.
Somit gilt:
(39 ⋅ 37) mod 6 ≡ (3 ⋅ 1) mod 6 ≡ 3 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 1058 mod 251.
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. 105 -> x
2. mod(x²,251) -> 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: 1051=105
2: 1052=1051+1=1051⋅1051 ≡ 105⋅105=11025 ≡ 232 mod 251
4: 1054=1052+2=1052⋅1052 ≡ 232⋅232=53824 ≡ 110 mod 251
8: 1058=1054+4=1054⋅1054 ≡ 110⋅110=12100 ≡ 52 mod 251
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 49166 mod 569.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 66 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 66 an und zerlegen 66 in eine Summer von 2er-Potenzen:
66 = 64+2
1: 4911=491
2: 4912=4911+1=4911⋅4911 ≡ 491⋅491=241081 ≡ 394 mod 569
4: 4914=4912+2=4912⋅4912 ≡ 394⋅394=155236 ≡ 468 mod 569
8: 4918=4914+4=4914⋅4914 ≡ 468⋅468=219024 ≡ 528 mod 569
16: 49116=4918+8=4918⋅4918 ≡ 528⋅528=278784 ≡ 543 mod 569
32: 49132=49116+16=49116⋅49116 ≡ 543⋅543=294849 ≡ 107 mod 569
64: 49164=49132+32=49132⋅49132 ≡ 107⋅107=11449 ≡ 69 mod 569
49166
= 49164+2
= 49164⋅4912
≡ 69 ⋅ 394 mod 569
≡ 27186 mod 569 ≡ 443 mod 569
Es gilt also: 49166 ≡ 443 mod 569
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 90.
Also bestimme x, so dass 90 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 90
| =>97 | = 1⋅90 + 7 |
| =>90 | = 12⋅7 + 6 |
| =>7 | = 1⋅6 + 1 |
| =>6 | = 6⋅1 + 0 |
also gilt: ggt(97,90)=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= 7-1⋅6 | |||
| 6= 90-12⋅7 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅7 -1⋅(90 -12⋅ 7)
= 1⋅7 -1⋅90 +12⋅ 7) = -1⋅90 +13⋅ 7 (=1) |
| 7= 97-1⋅90 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅90 +13⋅(97 -1⋅ 90)
= -1⋅90 +13⋅97 -13⋅ 90) = 13⋅97 -14⋅ 90 (=1) |
Es gilt also: ggt(97,90)=1 = 13⋅97 -14⋅90
oder wenn man 13⋅97 auf die linke Seite bringt:
1 -13⋅97 = -14⋅90
-14⋅90 = -13⋅97 + 1 |+97⋅90
-14⋅90 + 97⋅90 = -13⋅97 + 97⋅90 + 1
(-14 + 97) ⋅ 90 = (-13 + 90) ⋅ 97 + 1
83⋅90 = 77⋅97 + 1
Es gilt also: 83⋅90 = 77⋅97 +1
Somit 83⋅90 = 1 mod 97
83 ist also das Inverse von 90 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 53. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
