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: (1500 - 20004) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1500 - 20004) mod 5 ≡ (1500 mod 5 - 20004 mod 5) mod 5.
1500 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1500
= 1500
20004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 20004
= 20000
Somit gilt:
(1500 - 20004) mod 5 ≡ (0 - 4) mod 5 ≡ -4 mod 5 ≡ 1 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (55 ⋅ 56) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(55 ⋅ 56) mod 10 ≡ (55 mod 10 ⋅ 56 mod 10) mod 10.
55 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 55 = 50 + 5 = 5 ⋅ 10 + 5 ist.
56 mod 10 ≡ 6 mod 10 kann man relativ leicht bestimmen, weil ja 56 = 50 + 6 = 5 ⋅ 10 + 6 ist.
Somit gilt:
(55 ⋅ 56) mod 10 ≡ (5 ⋅ 6) mod 10 ≡ 30 mod 10 ≡ 0 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 42564 mod 827.
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. 425 -> x
2. mod(x²,827) -> 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: 4251=425
2: 4252=4251+1=4251⋅4251 ≡ 425⋅425=180625 ≡ 339 mod 827
4: 4254=4252+2=4252⋅4252 ≡ 339⋅339=114921 ≡ 795 mod 827
8: 4258=4254+4=4254⋅4254 ≡ 795⋅795=632025 ≡ 197 mod 827
16: 42516=4258+8=4258⋅4258 ≡ 197⋅197=38809 ≡ 767 mod 827
32: 42532=42516+16=42516⋅42516 ≡ 767⋅767=588289 ≡ 292 mod 827
64: 42564=42532+32=42532⋅42532 ≡ 292⋅292=85264 ≡ 83 mod 827
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 504106 mod 827.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 106 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 106 an und zerlegen 106 in eine Summer von 2er-Potenzen:
106 = 64+32+8+2
1: 5041=504
2: 5042=5041+1=5041⋅5041 ≡ 504⋅504=254016 ≡ 127 mod 827
4: 5044=5042+2=5042⋅5042 ≡ 127⋅127=16129 ≡ 416 mod 827
8: 5048=5044+4=5044⋅5044 ≡ 416⋅416=173056 ≡ 213 mod 827
16: 50416=5048+8=5048⋅5048 ≡ 213⋅213=45369 ≡ 711 mod 827
32: 50432=50416+16=50416⋅50416 ≡ 711⋅711=505521 ≡ 224 mod 827
64: 50464=50432+32=50432⋅50432 ≡ 224⋅224=50176 ≡ 556 mod 827
504106
= 50464+32+8+2
= 50464⋅50432⋅5048⋅5042
≡ 556 ⋅ 224 ⋅ 213 ⋅ 127 mod 827
≡ 124544 ⋅ 213 ⋅ 127 mod 827 ≡ 494 ⋅ 213 ⋅ 127 mod 827
≡ 105222 ⋅ 127 mod 827 ≡ 193 ⋅ 127 mod 827
≡ 24511 mod 827 ≡ 528 mod 827
Es gilt also: 504106 ≡ 528 mod 827
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 30.
Also bestimme x, so dass 30 ⋅ x ≡ 1 mod 73 gilt:
Berechnung des größten gemeinsamen Teilers von 73 und 30
| =>73 | = 2⋅30 + 13 |
| =>30 | = 2⋅13 + 4 |
| =>13 | = 3⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(73,30)=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= 13-3⋅4 | |||
| 4= 30-2⋅13 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅13 -3⋅(30 -2⋅ 13)
= 1⋅13 -3⋅30 +6⋅ 13) = -3⋅30 +7⋅ 13 (=1) |
| 13= 73-2⋅30 | eingesetzt in die Zeile drüber: | 1 |
= -3⋅30 +7⋅(73 -2⋅ 30)
= -3⋅30 +7⋅73 -14⋅ 30) = 7⋅73 -17⋅ 30 (=1) |
Es gilt also: ggt(73,30)=1 = 7⋅73 -17⋅30
oder wenn man 7⋅73 auf die linke Seite bringt:
1 -7⋅73 = -17⋅30
-17⋅30 = -7⋅73 + 1 |+73⋅30
-17⋅30 + 73⋅30 = -7⋅73 + 73⋅30 + 1
(-17 + 73) ⋅ 30 = (-7 + 30) ⋅ 73 + 1
56⋅30 = 23⋅73 + 1
Es gilt also: 56⋅30 = 23⋅73 +1
Somit 56⋅30 = 1 mod 73
56 ist also das Inverse von 30 mod 73
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 89 und q = 59. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.