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: (147 - 9998) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(147 - 9998) mod 5 ≡ (147 mod 5 - 9998 mod 5) mod 5.
147 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 147
= 140
9998 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 9998
= 9000
Somit gilt:
(147 - 9998) mod 5 ≡ (2 - 3) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (44 ⋅ 88) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(44 ⋅ 88) mod 9 ≡ (44 mod 9 ⋅ 88 mod 9) mod 9.
44 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 44 = 36 + 8 = 4 ⋅ 9 + 8 ist.
88 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 88 = 81 + 7 = 9 ⋅ 9 + 7 ist.
Somit gilt:
(44 ⋅ 88) mod 9 ≡ (8 ⋅ 7) mod 9 ≡ 56 mod 9 ≡ 2 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 51032 mod 647.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 510 -> x
2. mod(x²,647) -> 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: 5101=510
2: 5102=5101+1=5101⋅5101 ≡ 510⋅510=260100 ≡ 6 mod 647
4: 5104=5102+2=5102⋅5102 ≡ 6⋅6=36 ≡ 36 mod 647
8: 5108=5104+4=5104⋅5104 ≡ 36⋅36=1296 ≡ 2 mod 647
16: 51016=5108+8=5108⋅5108 ≡ 2⋅2=4 ≡ 4 mod 647
32: 51032=51016+16=51016⋅51016 ≡ 4⋅4=16 ≡ 16 mod 647
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 353163 mod 691.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 163 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 163 an und zerlegen 163 in eine Summer von 2er-Potenzen:
163 = 128+32+2+1
1: 3531=353
2: 3532=3531+1=3531⋅3531 ≡ 353⋅353=124609 ≡ 229 mod 691
4: 3534=3532+2=3532⋅3532 ≡ 229⋅229=52441 ≡ 616 mod 691
8: 3538=3534+4=3534⋅3534 ≡ 616⋅616=379456 ≡ 97 mod 691
16: 35316=3538+8=3538⋅3538 ≡ 97⋅97=9409 ≡ 426 mod 691
32: 35332=35316+16=35316⋅35316 ≡ 426⋅426=181476 ≡ 434 mod 691
64: 35364=35332+32=35332⋅35332 ≡ 434⋅434=188356 ≡ 404 mod 691
128: 353128=35364+64=35364⋅35364 ≡ 404⋅404=163216 ≡ 140 mod 691
353163
= 353128+32+2+1
= 353128⋅35332⋅3532⋅3531
≡ 140 ⋅ 434 ⋅ 229 ⋅ 353 mod 691
≡ 60760 ⋅ 229 ⋅ 353 mod 691 ≡ 643 ⋅ 229 ⋅ 353 mod 691
≡ 147247 ⋅ 353 mod 691 ≡ 64 ⋅ 353 mod 691
≡ 22592 mod 691 ≡ 480 mod 691
Es gilt also: 353163 ≡ 480 mod 691
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-53-Inverse zur Zahl 31.
Also bestimme x, so dass 31 ⋅ x ≡ 1 mod 53 gilt:
Berechnung des größten gemeinsamen Teilers von 53 und 31
| =>53 | = 1⋅31 + 22 |
| =>31 | = 1⋅22 + 9 |
| =>22 | = 2⋅9 + 4 |
| =>9 | = 2⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(53,31)=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= 22-2⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -2⋅(22 -2⋅ 9)
= 1⋅9 -2⋅22 +4⋅ 9) = -2⋅22 +5⋅ 9 (=1) |
| 9= 31-1⋅22 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅22 +5⋅(31 -1⋅ 22)
= -2⋅22 +5⋅31 -5⋅ 22) = 5⋅31 -7⋅ 22 (=1) |
| 22= 53-1⋅31 | eingesetzt in die Zeile drüber: | 1 |
= 5⋅31 -7⋅(53 -1⋅ 31)
= 5⋅31 -7⋅53 +7⋅ 31) = -7⋅53 +12⋅ 31 (=1) |
Es gilt also: ggt(53,31)=1 = -7⋅53 +12⋅31
oder wenn man -7⋅53 auf die linke Seite bringt:
1 +7⋅53 = +12⋅31
Es gilt also: 12⋅31 = 7⋅53 +1
Somit 12⋅31 = 1 mod 53
12 ist also das Inverse von 31 mod 53
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 43 und q = 101. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
