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: (1996 - 122) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1996 - 122) mod 4 ≡ (1996 mod 4 - 122 mod 4) mod 4.
1996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1996
= 1900
122 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 122
= 120
Somit gilt:
(1996 - 122) mod 4 ≡ (0 - 2) mod 4 ≡ -2 mod 4 ≡ 2 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (69 ⋅ 49) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(69 ⋅ 49) mod 6 ≡ (69 mod 6 ⋅ 49 mod 6) mod 6.
69 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 69 = 66 + 3 = 11 ⋅ 6 + 3 ist.
49 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 49 = 48 + 1 = 8 ⋅ 6 + 1 ist.
Somit gilt:
(69 ⋅ 49) mod 6 ≡ (3 ⋅ 1) mod 6 ≡ 3 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 603128 mod 761.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 603 -> x
2. mod(x²,761) -> 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: 6031=603
2: 6032=6031+1=6031⋅6031 ≡ 603⋅603=363609 ≡ 612 mod 761
4: 6034=6032+2=6032⋅6032 ≡ 612⋅612=374544 ≡ 132 mod 761
8: 6038=6034+4=6034⋅6034 ≡ 132⋅132=17424 ≡ 682 mod 761
16: 60316=6038+8=6038⋅6038 ≡ 682⋅682=465124 ≡ 153 mod 761
32: 60332=60316+16=60316⋅60316 ≡ 153⋅153=23409 ≡ 579 mod 761
64: 60364=60332+32=60332⋅60332 ≡ 579⋅579=335241 ≡ 401 mod 761
128: 603128=60364+64=60364⋅60364 ≡ 401⋅401=160801 ≡ 230 mod 761
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 316200 mod 929.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 200 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 200 an und zerlegen 200 in eine Summer von 2er-Potenzen:
200 = 128+64+8
1: 3161=316
2: 3162=3161+1=3161⋅3161 ≡ 316⋅316=99856 ≡ 453 mod 929
4: 3164=3162+2=3162⋅3162 ≡ 453⋅453=205209 ≡ 829 mod 929
8: 3168=3164+4=3164⋅3164 ≡ 829⋅829=687241 ≡ 710 mod 929
16: 31616=3168+8=3168⋅3168 ≡ 710⋅710=504100 ≡ 582 mod 929
32: 31632=31616+16=31616⋅31616 ≡ 582⋅582=338724 ≡ 568 mod 929
64: 31664=31632+32=31632⋅31632 ≡ 568⋅568=322624 ≡ 261 mod 929
128: 316128=31664+64=31664⋅31664 ≡ 261⋅261=68121 ≡ 304 mod 929
316200
= 316128+64+8
= 316128⋅31664⋅3168
≡ 304 ⋅ 261 ⋅ 710 mod 929
≡ 79344 ⋅ 710 mod 929 ≡ 379 ⋅ 710 mod 929
≡ 269090 mod 929 ≡ 609 mod 929
Es gilt also: 316200 ≡ 609 mod 929
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 22.
Also bestimme x, so dass 22 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 22
| =>71 | = 3⋅22 + 5 |
| =>22 | = 4⋅5 + 2 |
| =>5 | = 2⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(71,22)=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= 22-4⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -2⋅(22 -4⋅ 5)
= 1⋅5 -2⋅22 +8⋅ 5) = -2⋅22 +9⋅ 5 (=1) |
| 5= 71-3⋅22 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅22 +9⋅(71 -3⋅ 22)
= -2⋅22 +9⋅71 -27⋅ 22) = 9⋅71 -29⋅ 22 (=1) |
Es gilt also: ggt(71,22)=1 = 9⋅71 -29⋅22
oder wenn man 9⋅71 auf die linke Seite bringt:
1 -9⋅71 = -29⋅22
-29⋅22 = -9⋅71 + 1 |+71⋅22
-29⋅22 + 71⋅22 = -9⋅71 + 71⋅22 + 1
(-29 + 71) ⋅ 22 = (-9 + 22) ⋅ 71 + 1
42⋅22 = 13⋅71 + 1
Es gilt also: 42⋅22 = 13⋅71 +1
Somit 42⋅22 = 1 mod 71
42 ist also das Inverse von 22 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 101 und q = 47. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
