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: (20001 + 201) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(20001 + 201) mod 5 ≡ (20001 mod 5 + 201 mod 5) mod 5.
20001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 20001
= 20000
201 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 201
= 200
Somit gilt:
(20001 + 201) mod 5 ≡ (1 + 1) mod 5 ≡ 2 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (29 ⋅ 64) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(29 ⋅ 64) mod 9 ≡ (29 mod 9 ⋅ 64 mod 9) mod 9.
29 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 29 = 27 + 2 = 3 ⋅ 9 + 2 ist.
64 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 7 ⋅ 9 + 1 ist.
Somit gilt:
(29 ⋅ 64) mod 9 ≡ (2 ⋅ 1) mod 9 ≡ 2 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 32264 mod 643.
Die 64 im Exponent ist ja ein reine 2er-Potenz (26).
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. 322 -> x
2. mod(x²,643) -> 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: 3221=322
2: 3222=3221+1=3221⋅3221 ≡ 322⋅322=103684 ≡ 161 mod 643
4: 3224=3222+2=3222⋅3222 ≡ 161⋅161=25921 ≡ 201 mod 643
8: 3228=3224+4=3224⋅3224 ≡ 201⋅201=40401 ≡ 535 mod 643
16: 32216=3228+8=3228⋅3228 ≡ 535⋅535=286225 ≡ 90 mod 643
32: 32232=32216+16=32216⋅32216 ≡ 90⋅90=8100 ≡ 384 mod 643
64: 32264=32232+32=32232⋅32232 ≡ 384⋅384=147456 ≡ 209 mod 643
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 353212 mod 809.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 212 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 212 an und zerlegen 212 in eine Summer von 2er-Potenzen:
212 = 128+64+16+4
1: 3531=353
2: 3532=3531+1=3531⋅3531 ≡ 353⋅353=124609 ≡ 23 mod 809
4: 3534=3532+2=3532⋅3532 ≡ 23⋅23=529 ≡ 529 mod 809
8: 3538=3534+4=3534⋅3534 ≡ 529⋅529=279841 ≡ 736 mod 809
16: 35316=3538+8=3538⋅3538 ≡ 736⋅736=541696 ≡ 475 mod 809
32: 35332=35316+16=35316⋅35316 ≡ 475⋅475=225625 ≡ 723 mod 809
64: 35364=35332+32=35332⋅35332 ≡ 723⋅723=522729 ≡ 115 mod 809
128: 353128=35364+64=35364⋅35364 ≡ 115⋅115=13225 ≡ 281 mod 809
353212
= 353128+64+16+4
= 353128⋅35364⋅35316⋅3534
≡ 281 ⋅ 115 ⋅ 475 ⋅ 529 mod 809
≡ 32315 ⋅ 475 ⋅ 529 mod 809 ≡ 764 ⋅ 475 ⋅ 529 mod 809
≡ 362900 ⋅ 529 mod 809 ≡ 468 ⋅ 529 mod 809
≡ 247572 mod 809 ≡ 18 mod 809
Es gilt also: 353212 ≡ 18 mod 809
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 35.
Also bestimme x, so dass 35 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 35
| =>101 | = 2⋅35 + 31 |
| =>35 | = 1⋅31 + 4 |
| =>31 | = 7⋅4 + 3 |
| =>4 | = 1⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(101,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= 4-1⋅3 | |||
| 3= 31-7⋅4 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅4 -1⋅(31 -7⋅ 4)
= 1⋅4 -1⋅31 +7⋅ 4) = -1⋅31 +8⋅ 4 (=1) |
| 4= 35-1⋅31 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅31 +8⋅(35 -1⋅ 31)
= -1⋅31 +8⋅35 -8⋅ 31) = 8⋅35 -9⋅ 31 (=1) |
| 31= 101-2⋅35 | eingesetzt in die Zeile drüber: | 1 |
= 8⋅35 -9⋅(101 -2⋅ 35)
= 8⋅35 -9⋅101 +18⋅ 35) = -9⋅101 +26⋅ 35 (=1) |
Es gilt also: ggt(101,35)=1 = -9⋅101 +26⋅35
oder wenn man -9⋅101 auf die linke Seite bringt:
1 +9⋅101 = +26⋅35
Es gilt also: 26⋅35 = 9⋅101 +1
Somit 26⋅35 = 1 mod 101
26 ist also das Inverse von 35 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
