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: (12003 + 31) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(12003 + 31) mod 3 ≡ (12003 mod 3 + 31 mod 3) mod 3.
12003 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 12003
= 12000
31 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 31
= 30
Somit gilt:
(12003 + 31) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (42 ⋅ 19) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(42 ⋅ 19) mod 9 ≡ (42 mod 9 ⋅ 19 mod 9) mod 9.
42 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 42 = 36 + 6 = 4 ⋅ 9 + 6 ist.
19 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 19 = 18 + 1 = 2 ⋅ 9 + 1 ist.
Somit gilt:
(42 ⋅ 19) mod 9 ≡ (6 ⋅ 1) mod 9 ≡ 6 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 292128 mod 367.
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. 292 -> x
2. mod(x²,367) -> 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: 2921=292
2: 2922=2921+1=2921⋅2921 ≡ 292⋅292=85264 ≡ 120 mod 367
4: 2924=2922+2=2922⋅2922 ≡ 120⋅120=14400 ≡ 87 mod 367
8: 2928=2924+4=2924⋅2924 ≡ 87⋅87=7569 ≡ 229 mod 367
16: 29216=2928+8=2928⋅2928 ≡ 229⋅229=52441 ≡ 327 mod 367
32: 29232=29216+16=29216⋅29216 ≡ 327⋅327=106929 ≡ 132 mod 367
64: 29264=29232+32=29232⋅29232 ≡ 132⋅132=17424 ≡ 175 mod 367
128: 292128=29264+64=29264⋅29264 ≡ 175⋅175=30625 ≡ 164 mod 367
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 29877 mod 389.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 77 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 77 an und zerlegen 77 in eine Summer von 2er-Potenzen:
77 = 64+8+4+1
1: 2981=298
2: 2982=2981+1=2981⋅2981 ≡ 298⋅298=88804 ≡ 112 mod 389
4: 2984=2982+2=2982⋅2982 ≡ 112⋅112=12544 ≡ 96 mod 389
8: 2988=2984+4=2984⋅2984 ≡ 96⋅96=9216 ≡ 269 mod 389
16: 29816=2988+8=2988⋅2988 ≡ 269⋅269=72361 ≡ 7 mod 389
32: 29832=29816+16=29816⋅29816 ≡ 7⋅7=49 ≡ 49 mod 389
64: 29864=29832+32=29832⋅29832 ≡ 49⋅49=2401 ≡ 67 mod 389
29877
= 29864+8+4+1
= 29864⋅2988⋅2984⋅2981
≡ 67 ⋅ 269 ⋅ 96 ⋅ 298 mod 389
≡ 18023 ⋅ 96 ⋅ 298 mod 389 ≡ 129 ⋅ 96 ⋅ 298 mod 389
≡ 12384 ⋅ 298 mod 389 ≡ 325 ⋅ 298 mod 389
≡ 96850 mod 389 ≡ 378 mod 389
Es gilt also: 29877 ≡ 378 mod 389
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 60.
Also bestimme x, so dass 60 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 60
| =>101 | = 1⋅60 + 41 |
| =>60 | = 1⋅41 + 19 |
| =>41 | = 2⋅19 + 3 |
| =>19 | = 6⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(101,60)=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= 19-6⋅3 | |||
| 3= 41-2⋅19 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅19 -6⋅(41 -2⋅ 19)
= 1⋅19 -6⋅41 +12⋅ 19) = -6⋅41 +13⋅ 19 (=1) |
| 19= 60-1⋅41 | eingesetzt in die Zeile drüber: | 1 |
= -6⋅41 +13⋅(60 -1⋅ 41)
= -6⋅41 +13⋅60 -13⋅ 41) = 13⋅60 -19⋅ 41 (=1) |
| 41= 101-1⋅60 | eingesetzt in die Zeile drüber: | 1 |
= 13⋅60 -19⋅(101 -1⋅ 60)
= 13⋅60 -19⋅101 +19⋅ 60) = -19⋅101 +32⋅ 60 (=1) |
Es gilt also: ggt(101,60)=1 = -19⋅101 +32⋅60
oder wenn man -19⋅101 auf die linke Seite bringt:
1 +19⋅101 = +32⋅60
Es gilt also: 32⋅60 = 19⋅101 +1
Somit 32⋅60 = 1 mod 101
32 ist also das Inverse von 60 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 89 und q = 97. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
