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: (14996 + 14996) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(14996 + 14996) mod 5 ≡ (14996 mod 5 + 14996 mod 5) mod 5.
14996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 14996
= 14000
14996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 14996
= 14000
Somit gilt:
(14996 + 14996) mod 5 ≡ (1 + 1) mod 5 ≡ 2 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (93 ⋅ 99) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(93 ⋅ 99) mod 6 ≡ (93 mod 6 ⋅ 99 mod 6) mod 6.
93 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 93 = 90 + 3 = 15 ⋅ 6 + 3 ist.
99 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 99 = 96 + 3 = 16 ⋅ 6 + 3 ist.
Somit gilt:
(93 ⋅ 99) mod 6 ≡ (3 ⋅ 3) mod 6 ≡ 9 mod 6 ≡ 3 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 39816 mod 419.
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. 398 -> x
2. mod(x²,419) -> 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: 3981=398
2: 3982=3981+1=3981⋅3981 ≡ 398⋅398=158404 ≡ 22 mod 419
4: 3984=3982+2=3982⋅3982 ≡ 22⋅22=484 ≡ 65 mod 419
8: 3988=3984+4=3984⋅3984 ≡ 65⋅65=4225 ≡ 35 mod 419
16: 39816=3988+8=3988⋅3988 ≡ 35⋅35=1225 ≡ 387 mod 419
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 322236 mod 541.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 236 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 236 an und zerlegen 236 in eine Summer von 2er-Potenzen:
236 = 128+64+32+8+4
1: 3221=322
2: 3222=3221+1=3221⋅3221 ≡ 322⋅322=103684 ≡ 353 mod 541
4: 3224=3222+2=3222⋅3222 ≡ 353⋅353=124609 ≡ 179 mod 541
8: 3228=3224+4=3224⋅3224 ≡ 179⋅179=32041 ≡ 122 mod 541
16: 32216=3228+8=3228⋅3228 ≡ 122⋅122=14884 ≡ 277 mod 541
32: 32232=32216+16=32216⋅32216 ≡ 277⋅277=76729 ≡ 448 mod 541
64: 32264=32232+32=32232⋅32232 ≡ 448⋅448=200704 ≡ 534 mod 541
128: 322128=32264+64=32264⋅32264 ≡ 534⋅534=285156 ≡ 49 mod 541
322236
= 322128+64+32+8+4
= 322128⋅32264⋅32232⋅3228⋅3224
≡ 49 ⋅ 534 ⋅ 448 ⋅ 122 ⋅ 179 mod 541
≡ 26166 ⋅ 448 ⋅ 122 ⋅ 179 mod 541 ≡ 198 ⋅ 448 ⋅ 122 ⋅ 179 mod 541
≡ 88704 ⋅ 122 ⋅ 179 mod 541 ≡ 521 ⋅ 122 ⋅ 179 mod 541
≡ 63562 ⋅ 179 mod 541 ≡ 265 ⋅ 179 mod 541
≡ 47435 mod 541 ≡ 368 mod 541
Es gilt also: 322236 ≡ 368 mod 541
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 58.
Also bestimme x, so dass 58 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 58
| =>67 | = 1⋅58 + 9 |
| =>58 | = 6⋅9 + 4 |
| =>9 | = 2⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(67,58)=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= 58-6⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -2⋅(58 -6⋅ 9)
= 1⋅9 -2⋅58 +12⋅ 9) = -2⋅58 +13⋅ 9 (=1) |
| 9= 67-1⋅58 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅58 +13⋅(67 -1⋅ 58)
= -2⋅58 +13⋅67 -13⋅ 58) = 13⋅67 -15⋅ 58 (=1) |
Es gilt also: ggt(67,58)=1 = 13⋅67 -15⋅58
oder wenn man 13⋅67 auf die linke Seite bringt:
1 -13⋅67 = -15⋅58
-15⋅58 = -13⋅67 + 1 |+67⋅58
-15⋅58 + 67⋅58 = -13⋅67 + 67⋅58 + 1
(-15 + 67) ⋅ 58 = (-13 + 58) ⋅ 67 + 1
52⋅58 = 45⋅67 + 1
Es gilt also: 52⋅58 = 45⋅67 +1
Somit 52⋅58 = 1 mod 67
52 ist also das Inverse von 58 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 73 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
