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: (796 + 16000) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(796 + 16000) mod 4 ≡ (796 mod 4 + 16000 mod 4) mod 4.
796 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 796
= 700
16000 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 16000
= 16000
Somit gilt:
(796 + 16000) mod 4 ≡ (0 + 0) mod 4 ≡ 0 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (16 ⋅ 80) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(16 ⋅ 80) mod 4 ≡ (16 mod 4 ⋅ 80 mod 4) mod 4.
16 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 16 = 16 + 0 = 4 ⋅ 4 + 0 ist.
80 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 80 = 80 + 0 = 20 ⋅ 4 + 0 ist.
Somit gilt:
(16 ⋅ 80) mod 4 ≡ (0 ⋅ 0) mod 4 ≡ 0 mod 4.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 19916 mod 331.
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. 199 -> x
2. mod(x²,331) -> 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: 1991=199
2: 1992=1991+1=1991⋅1991 ≡ 199⋅199=39601 ≡ 212 mod 331
4: 1994=1992+2=1992⋅1992 ≡ 212⋅212=44944 ≡ 259 mod 331
8: 1998=1994+4=1994⋅1994 ≡ 259⋅259=67081 ≡ 219 mod 331
16: 19916=1998+8=1998⋅1998 ≡ 219⋅219=47961 ≡ 297 mod 331
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 47863 mod 727.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 63 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 63 an und zerlegen 63 in eine Summer von 2er-Potenzen:
63 = 32+16+8+4+2+1
1: 4781=478
2: 4782=4781+1=4781⋅4781 ≡ 478⋅478=228484 ≡ 206 mod 727
4: 4784=4782+2=4782⋅4782 ≡ 206⋅206=42436 ≡ 270 mod 727
8: 4788=4784+4=4784⋅4784 ≡ 270⋅270=72900 ≡ 200 mod 727
16: 47816=4788+8=4788⋅4788 ≡ 200⋅200=40000 ≡ 15 mod 727
32: 47832=47816+16=47816⋅47816 ≡ 15⋅15=225 ≡ 225 mod 727
47863
= 47832+16+8+4+2+1
= 47832⋅47816⋅4788⋅4784⋅4782⋅4781
≡ 225 ⋅ 15 ⋅ 200 ⋅ 270 ⋅ 206 ⋅ 478 mod 727
≡ 3375 ⋅ 200 ⋅ 270 ⋅ 206 ⋅ 478 mod 727 ≡ 467 ⋅ 200 ⋅ 270 ⋅ 206 ⋅ 478 mod 727
≡ 93400 ⋅ 270 ⋅ 206 ⋅ 478 mod 727 ≡ 344 ⋅ 270 ⋅ 206 ⋅ 478 mod 727
≡ 92880 ⋅ 206 ⋅ 478 mod 727 ≡ 551 ⋅ 206 ⋅ 478 mod 727
≡ 113506 ⋅ 478 mod 727 ≡ 94 ⋅ 478 mod 727
≡ 44932 mod 727 ≡ 585 mod 727
Es gilt also: 47863 ≡ 585 mod 727
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 70.
Also bestimme x, so dass 70 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 70
| =>89 | = 1⋅70 + 19 |
| =>70 | = 3⋅19 + 13 |
| =>19 | = 1⋅13 + 6 |
| =>13 | = 2⋅6 + 1 |
| =>6 | = 6⋅1 + 0 |
also gilt: ggt(89,70)=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-2⋅6 | |||
| 6= 19-1⋅13 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅13 -2⋅(19 -1⋅ 13)
= 1⋅13 -2⋅19 +2⋅ 13) = -2⋅19 +3⋅ 13 (=1) |
| 13= 70-3⋅19 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅19 +3⋅(70 -3⋅ 19)
= -2⋅19 +3⋅70 -9⋅ 19) = 3⋅70 -11⋅ 19 (=1) |
| 19= 89-1⋅70 | eingesetzt in die Zeile drüber: | 1 |
= 3⋅70 -11⋅(89 -1⋅ 70)
= 3⋅70 -11⋅89 +11⋅ 70) = -11⋅89 +14⋅ 70 (=1) |
Es gilt also: ggt(89,70)=1 = -11⋅89 +14⋅70
oder wenn man -11⋅89 auf die linke Seite bringt:
1 +11⋅89 = +14⋅70
Es gilt also: 14⋅70 = 11⋅89 +1
Somit 14⋅70 = 1 mod 89
14 ist also das Inverse von 70 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 101 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
