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: (20000 + 397) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(20000 + 397) mod 4 ≡ (20000 mod 4 + 397 mod 4) mod 4.
20000 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 20000
= 20000
397 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 397
= 300
Somit gilt:
(20000 + 397) mod 4 ≡ (0 + 1) mod 4 ≡ 1 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (47 ⋅ 45) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(47 ⋅ 45) mod 11 ≡ (47 mod 11 ⋅ 45 mod 11) mod 11.
47 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 47 = 44 + 3 = 4 ⋅ 11 + 3 ist.
45 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 45 = 44 + 1 = 4 ⋅ 11 + 1 ist.
Somit gilt:
(47 ⋅ 45) mod 11 ≡ (3 ⋅ 1) mod 11 ≡ 3 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 23632 mod 593.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 236 -> 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: 2361=236
2: 2362=2361+1=2361⋅2361 ≡ 236⋅236=55696 ≡ 547 mod 593
4: 2364=2362+2=2362⋅2362 ≡ 547⋅547=299209 ≡ 337 mod 593
8: 2368=2364+4=2364⋅2364 ≡ 337⋅337=113569 ≡ 306 mod 593
16: 23616=2368+8=2368⋅2368 ≡ 306⋅306=93636 ≡ 535 mod 593
32: 23632=23616+16=23616⋅23616 ≡ 535⋅535=286225 ≡ 399 mod 593
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 197223 mod 619.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 223 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 223 an und zerlegen 223 in eine Summer von 2er-Potenzen:
223 = 128+64+16+8+4+2+1
1: 1971=197
2: 1972=1971+1=1971⋅1971 ≡ 197⋅197=38809 ≡ 431 mod 619
4: 1974=1972+2=1972⋅1972 ≡ 431⋅431=185761 ≡ 61 mod 619
8: 1978=1974+4=1974⋅1974 ≡ 61⋅61=3721 ≡ 7 mod 619
16: 19716=1978+8=1978⋅1978 ≡ 7⋅7=49 ≡ 49 mod 619
32: 19732=19716+16=19716⋅19716 ≡ 49⋅49=2401 ≡ 544 mod 619
64: 19764=19732+32=19732⋅19732 ≡ 544⋅544=295936 ≡ 54 mod 619
128: 197128=19764+64=19764⋅19764 ≡ 54⋅54=2916 ≡ 440 mod 619
197223
= 197128+64+16+8+4+2+1
= 197128⋅19764⋅19716⋅1978⋅1974⋅1972⋅1971
≡ 440 ⋅ 54 ⋅ 49 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 23760 ⋅ 49 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619 ≡ 238 ⋅ 49 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 11662 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619 ≡ 520 ⋅ 7 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 3640 ⋅ 61 ⋅ 431 ⋅ 197 mod 619 ≡ 545 ⋅ 61 ⋅ 431 ⋅ 197 mod 619
≡ 33245 ⋅ 431 ⋅ 197 mod 619 ≡ 438 ⋅ 431 ⋅ 197 mod 619
≡ 188778 ⋅ 197 mod 619 ≡ 602 ⋅ 197 mod 619
≡ 118594 mod 619 ≡ 365 mod 619
Es gilt also: 197223 ≡ 365 mod 619
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-53-Inverse zur Zahl 22.
Also bestimme x, so dass 22 ⋅ x ≡ 1 mod 53 gilt:
Berechnung des größten gemeinsamen Teilers von 53 und 22
| =>53 | = 2⋅22 + 9 |
| =>22 | = 2⋅9 + 4 |
| =>9 | = 2⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(53,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= 9-2⋅4 | |||
| 4= 22-2⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -2⋅(22 -2⋅ 9)
= 1⋅9 -2⋅22 +4⋅ 9) = -2⋅22 +5⋅ 9 (=1) |
| 9= 53-2⋅22 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅22 +5⋅(53 -2⋅ 22)
= -2⋅22 +5⋅53 -10⋅ 22) = 5⋅53 -12⋅ 22 (=1) |
Es gilt also: ggt(53,22)=1 = 5⋅53 -12⋅22
oder wenn man 5⋅53 auf die linke Seite bringt:
1 -5⋅53 = -12⋅22
-12⋅22 = -5⋅53 + 1 |+53⋅22
-12⋅22 + 53⋅22 = -5⋅53 + 53⋅22 + 1
(-12 + 53) ⋅ 22 = (-5 + 22) ⋅ 53 + 1
41⋅22 = 17⋅53 + 1
Es gilt also: 41⋅22 = 17⋅53 +1
Somit 41⋅22 = 1 mod 53
41 ist also das Inverse von 22 mod 53
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 73 und q = 97. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
