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: (1800 - 2693) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1800 - 2693) mod 9 ≡ (1800 mod 9 - 2693 mod 9) mod 9.
1800 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 1800
= 1800
2693 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 2693
= 2700
Somit gilt:
(1800 - 2693) mod 9 ≡ (0 - 2) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (57 ⋅ 67) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(57 ⋅ 67) mod 11 ≡ (57 mod 11 ⋅ 67 mod 11) mod 11.
57 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 57 = 55 + 2 = 5 ⋅ 11 + 2 ist.
67 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 67 = 66 + 1 = 6 ⋅ 11 + 1 ist.
Somit gilt:
(57 ⋅ 67) mod 11 ≡ (2 ⋅ 1) mod 11 ≡ 2 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 38416 mod 593.
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. 384 -> x
2. mod(x²,593) -> 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: 3841=384
2: 3842=3841+1=3841⋅3841 ≡ 384⋅384=147456 ≡ 392 mod 593
4: 3844=3842+2=3842⋅3842 ≡ 392⋅392=153664 ≡ 77 mod 593
8: 3848=3844+4=3844⋅3844 ≡ 77⋅77=5929 ≡ 592 mod 593
16: 38416=3848+8=3848⋅3848 ≡ 592⋅592=350464 ≡ 1 mod 593
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 115166 mod 229.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 166 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 166 an und zerlegen 166 in eine Summer von 2er-Potenzen:
166 = 128+32+4+2
1: 1151=115
2: 1152=1151+1=1151⋅1151 ≡ 115⋅115=13225 ≡ 172 mod 229
4: 1154=1152+2=1152⋅1152 ≡ 172⋅172=29584 ≡ 43 mod 229
8: 1158=1154+4=1154⋅1154 ≡ 43⋅43=1849 ≡ 17 mod 229
16: 11516=1158+8=1158⋅1158 ≡ 17⋅17=289 ≡ 60 mod 229
32: 11532=11516+16=11516⋅11516 ≡ 60⋅60=3600 ≡ 165 mod 229
64: 11564=11532+32=11532⋅11532 ≡ 165⋅165=27225 ≡ 203 mod 229
128: 115128=11564+64=11564⋅11564 ≡ 203⋅203=41209 ≡ 218 mod 229
115166
= 115128+32+4+2
= 115128⋅11532⋅1154⋅1152
≡ 218 ⋅ 165 ⋅ 43 ⋅ 172 mod 229
≡ 35970 ⋅ 43 ⋅ 172 mod 229 ≡ 17 ⋅ 43 ⋅ 172 mod 229
≡ 731 ⋅ 172 mod 229 ≡ 44 ⋅ 172 mod 229
≡ 7568 mod 229 ≡ 11 mod 229
Es gilt also: 115166 ≡ 11 mod 229
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 42.
Also bestimme x, so dass 42 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 42
| =>89 | = 2⋅42 + 5 |
| =>42 | = 8⋅5 + 2 |
| =>5 | = 2⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(89,42)=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= 5-2⋅2 | |||
| 2= 42-8⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -2⋅(42 -8⋅ 5)
= 1⋅5 -2⋅42 +16⋅ 5) = -2⋅42 +17⋅ 5 (=1) |
| 5= 89-2⋅42 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅42 +17⋅(89 -2⋅ 42)
= -2⋅42 +17⋅89 -34⋅ 42) = 17⋅89 -36⋅ 42 (=1) |
Es gilt also: ggt(89,42)=1 = 17⋅89 -36⋅42
oder wenn man 17⋅89 auf die linke Seite bringt:
1 -17⋅89 = -36⋅42
-36⋅42 = -17⋅89 + 1 |+89⋅42
-36⋅42 + 89⋅42 = -17⋅89 + 89⋅42 + 1
(-36 + 89) ⋅ 42 = (-17 + 42) ⋅ 89 + 1
53⋅42 = 25⋅89 + 1
Es gilt also: 53⋅42 = 25⋅89 +1
Somit 53⋅42 = 1 mod 89
53 ist also das Inverse von 42 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 97. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
