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: (12000 + 23999) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(12000 + 23999) mod 6 ≡ (12000 mod 6 + 23999 mod 6) mod 6.
12000 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 12000
= 12000
23999 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 23999
= 24000
Somit gilt:
(12000 + 23999) mod 6 ≡ (0 + 5) mod 6 ≡ 5 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (34 ⋅ 50) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(34 ⋅ 50) mod 6 ≡ (34 mod 6 ⋅ 50 mod 6) mod 6.
34 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 34 = 30 + 4 = 5 ⋅ 6 + 4 ist.
50 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 50 = 48 + 2 = 8 ⋅ 6 + 2 ist.
Somit gilt:
(34 ⋅ 50) mod 6 ≡ (4 ⋅ 2) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 59164 mod 691.
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. 591 -> 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: 5911=591
2: 5912=5911+1=5911⋅5911 ≡ 591⋅591=349281 ≡ 326 mod 691
4: 5914=5912+2=5912⋅5912 ≡ 326⋅326=106276 ≡ 553 mod 691
8: 5918=5914+4=5914⋅5914 ≡ 553⋅553=305809 ≡ 387 mod 691
16: 59116=5918+8=5918⋅5918 ≡ 387⋅387=149769 ≡ 513 mod 691
32: 59132=59116+16=59116⋅59116 ≡ 513⋅513=263169 ≡ 589 mod 691
64: 59164=59132+32=59132⋅59132 ≡ 589⋅589=346921 ≡ 39 mod 691
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 412230 mod 541.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 230 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 230 an und zerlegen 230 in eine Summer von 2er-Potenzen:
230 = 128+64+32+4+2
1: 4121=412
2: 4122=4121+1=4121⋅4121 ≡ 412⋅412=169744 ≡ 411 mod 541
4: 4124=4122+2=4122⋅4122 ≡ 411⋅411=168921 ≡ 129 mod 541
8: 4128=4124+4=4124⋅4124 ≡ 129⋅129=16641 ≡ 411 mod 541
16: 41216=4128+8=4128⋅4128 ≡ 411⋅411=168921 ≡ 129 mod 541
32: 41232=41216+16=41216⋅41216 ≡ 129⋅129=16641 ≡ 411 mod 541
64: 41264=41232+32=41232⋅41232 ≡ 411⋅411=168921 ≡ 129 mod 541
128: 412128=41264+64=41264⋅41264 ≡ 129⋅129=16641 ≡ 411 mod 541
412230
= 412128+64+32+4+2
= 412128⋅41264⋅41232⋅4124⋅4122
≡ 411 ⋅ 129 ⋅ 411 ⋅ 129 ⋅ 411 mod 541
≡ 53019 ⋅ 411 ⋅ 129 ⋅ 411 mod 541 ≡ 1 ⋅ 411 ⋅ 129 ⋅ 411 mod 541
≡ 411 ⋅ 129 ⋅ 411 mod 541
≡ 53019 ⋅ 411 mod 541 ≡ 1 ⋅ 411 mod 541
≡ 411 mod 541
Es gilt also: 412230 ≡ 411 mod 541
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 47.
Also bestimme x, so dass 47 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 47
| =>67 | = 1⋅47 + 20 |
| =>47 | = 2⋅20 + 7 |
| =>20 | = 2⋅7 + 6 |
| =>7 | = 1⋅6 + 1 |
| =>6 | = 6⋅1 + 0 |
also gilt: ggt(67,47)=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= 7-1⋅6 | |||
| 6= 20-2⋅7 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅7 -1⋅(20 -2⋅ 7)
= 1⋅7 -1⋅20 +2⋅ 7) = -1⋅20 +3⋅ 7 (=1) |
| 7= 47-2⋅20 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅20 +3⋅(47 -2⋅ 20)
= -1⋅20 +3⋅47 -6⋅ 20) = 3⋅47 -7⋅ 20 (=1) |
| 20= 67-1⋅47 | eingesetzt in die Zeile drüber: | 1 |
= 3⋅47 -7⋅(67 -1⋅ 47)
= 3⋅47 -7⋅67 +7⋅ 47) = -7⋅67 +10⋅ 47 (=1) |
Es gilt also: ggt(67,47)=1 = -7⋅67 +10⋅47
oder wenn man -7⋅67 auf die linke Seite bringt:
1 +7⋅67 = +10⋅47
Es gilt also: 10⋅47 = 7⋅67 +1
Somit 10⋅47 = 1 mod 67
10 ist also das Inverse von 47 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 101 und q = 67. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
