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: (1500 + 53) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1500 + 53) mod 5 ≡ (1500 mod 5 + 53 mod 5) mod 5.
1500 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1500
= 1500
53 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 53
= 50
Somit gilt:
(1500 + 53) mod 5 ≡ (0 + 3) mod 5 ≡ 3 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (55 ⋅ 97) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(55 ⋅ 97) mod 7 ≡ (55 mod 7 ⋅ 97 mod 7) mod 7.
55 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 55 = 49 + 6 = 7 ⋅ 7 + 6 ist.
97 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 97 = 91 + 6 = 13 ⋅ 7 + 6 ist.
Somit gilt:
(55 ⋅ 97) mod 7 ≡ (6 ⋅ 6) mod 7 ≡ 36 mod 7 ≡ 1 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 6558 mod 691.
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. 655 -> x
2. mod(x²,691) -> 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: 6551=655
2: 6552=6551+1=6551⋅6551 ≡ 655⋅655=429025 ≡ 605 mod 691
4: 6554=6552+2=6552⋅6552 ≡ 605⋅605=366025 ≡ 486 mod 691
8: 6558=6554+4=6554⋅6554 ≡ 486⋅486=236196 ≡ 565 mod 691
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 359117 mod 643.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 117 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 117 an und zerlegen 117 in eine Summer von 2er-Potenzen:
117 = 64+32+16+4+1
1: 3591=359
2: 3592=3591+1=3591⋅3591 ≡ 359⋅359=128881 ≡ 281 mod 643
4: 3594=3592+2=3592⋅3592 ≡ 281⋅281=78961 ≡ 515 mod 643
8: 3598=3594+4=3594⋅3594 ≡ 515⋅515=265225 ≡ 309 mod 643
16: 35916=3598+8=3598⋅3598 ≡ 309⋅309=95481 ≡ 317 mod 643
32: 35932=35916+16=35916⋅35916 ≡ 317⋅317=100489 ≡ 181 mod 643
64: 35964=35932+32=35932⋅35932 ≡ 181⋅181=32761 ≡ 611 mod 643
359117
= 35964+32+16+4+1
= 35964⋅35932⋅35916⋅3594⋅3591
≡ 611 ⋅ 181 ⋅ 317 ⋅ 515 ⋅ 359 mod 643
≡ 110591 ⋅ 317 ⋅ 515 ⋅ 359 mod 643 ≡ 638 ⋅ 317 ⋅ 515 ⋅ 359 mod 643
≡ 202246 ⋅ 515 ⋅ 359 mod 643 ≡ 344 ⋅ 515 ⋅ 359 mod 643
≡ 177160 ⋅ 359 mod 643 ≡ 335 ⋅ 359 mod 643
≡ 120265 mod 643 ≡ 24 mod 643
Es gilt also: 359117 ≡ 24 mod 643
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 35.
Also bestimme x, so dass 35 ⋅ x ≡ 1 mod 73 gilt:
Berechnung des größten gemeinsamen Teilers von 73 und 35
| =>73 | = 2⋅35 + 3 |
| =>35 | = 11⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(73,35)=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= 3-1⋅2 | |||
| 2= 35-11⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(35 -11⋅ 3)
= 1⋅3 -1⋅35 +11⋅ 3) = -1⋅35 +12⋅ 3 (=1) |
| 3= 73-2⋅35 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅35 +12⋅(73 -2⋅ 35)
= -1⋅35 +12⋅73 -24⋅ 35) = 12⋅73 -25⋅ 35 (=1) |
Es gilt also: ggt(73,35)=1 = 12⋅73 -25⋅35
oder wenn man 12⋅73 auf die linke Seite bringt:
1 -12⋅73 = -25⋅35
-25⋅35 = -12⋅73 + 1 |+73⋅35
-25⋅35 + 73⋅35 = -12⋅73 + 73⋅35 + 1
(-25 + 73) ⋅ 35 = (-12 + 35) ⋅ 73 + 1
48⋅35 = 23⋅73 + 1
Es gilt also: 48⋅35 = 23⋅73 +1
Somit 48⋅35 = 1 mod 73
48 ist also das Inverse von 35 mod 73
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 61 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.