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: (1200 + 76) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1200 + 76) mod 4 ≡ (1200 mod 4 + 76 mod 4) mod 4.
1200 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1200
= 1200
76 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 76
= 80
Somit gilt:
(1200 + 76) mod 4 ≡ (0 + 0) mod 4 ≡ 0 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (70 ⋅ 31) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(70 ⋅ 31) mod 11 ≡ (70 mod 11 ⋅ 31 mod 11) mod 11.
70 mod 11 ≡ 4 mod 11 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 6 ⋅ 11 + 4 ist.
31 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 31 = 22 + 9 = 2 ⋅ 11 + 9 ist.
Somit gilt:
(70 ⋅ 31) mod 11 ≡ (4 ⋅ 9) mod 11 ≡ 36 mod 11 ≡ 3 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 3958 mod 673.
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. 395 -> x
2. mod(x²,673) -> 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: 3951=395
2: 3952=3951+1=3951⋅3951 ≡ 395⋅395=156025 ≡ 562 mod 673
4: 3954=3952+2=3952⋅3952 ≡ 562⋅562=315844 ≡ 207 mod 673
8: 3958=3954+4=3954⋅3954 ≡ 207⋅207=42849 ≡ 450 mod 673
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 40183 mod 751.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 83 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 83 an und zerlegen 83 in eine Summer von 2er-Potenzen:
83 = 64+16+2+1
1: 4011=401
2: 4012=4011+1=4011⋅4011 ≡ 401⋅401=160801 ≡ 87 mod 751
4: 4014=4012+2=4012⋅4012 ≡ 87⋅87=7569 ≡ 59 mod 751
8: 4018=4014+4=4014⋅4014 ≡ 59⋅59=3481 ≡ 477 mod 751
16: 40116=4018+8=4018⋅4018 ≡ 477⋅477=227529 ≡ 727 mod 751
32: 40132=40116+16=40116⋅40116 ≡ 727⋅727=528529 ≡ 576 mod 751
64: 40164=40132+32=40132⋅40132 ≡ 576⋅576=331776 ≡ 585 mod 751
40183
= 40164+16+2+1
= 40164⋅40116⋅4012⋅4011
≡ 585 ⋅ 727 ⋅ 87 ⋅ 401 mod 751
≡ 425295 ⋅ 87 ⋅ 401 mod 751 ≡ 229 ⋅ 87 ⋅ 401 mod 751
≡ 19923 ⋅ 401 mod 751 ≡ 397 ⋅ 401 mod 751
≡ 159197 mod 751 ≡ 736 mod 751
Es gilt also: 40183 ≡ 736 mod 751
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-79-Inverse zur Zahl 27.
Also bestimme x, so dass 27 ⋅ x ≡ 1 mod 79 gilt:
Berechnung des größten gemeinsamen Teilers von 79 und 27
| =>79 | = 2⋅27 + 25 |
| =>27 | = 1⋅25 + 2 |
| =>25 | = 12⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(79,27)=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= 25-12⋅2 | |||
| 2= 27-1⋅25 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅25 -12⋅(27 -1⋅ 25)
= 1⋅25 -12⋅27 +12⋅ 25) = -12⋅27 +13⋅ 25 (=1) |
| 25= 79-2⋅27 | eingesetzt in die Zeile drüber: | 1 |
= -12⋅27 +13⋅(79 -2⋅ 27)
= -12⋅27 +13⋅79 -26⋅ 27) = 13⋅79 -38⋅ 27 (=1) |
Es gilt also: ggt(79,27)=1 = 13⋅79 -38⋅27
oder wenn man 13⋅79 auf die linke Seite bringt:
1 -13⋅79 = -38⋅27
-38⋅27 = -13⋅79 + 1 |+79⋅27
-38⋅27 + 79⋅27 = -13⋅79 + 79⋅27 + 1
(-38 + 79) ⋅ 27 = (-13 + 27) ⋅ 79 + 1
41⋅27 = 14⋅79 + 1
Es gilt also: 41⋅27 = 14⋅79 +1
Somit 41⋅27 = 1 mod 79
41 ist also das Inverse von 27 mod 79
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
