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 + 1500) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(147 + 1500) mod 3 ≡ (147 mod 3 + 1500 mod 3) mod 3.
147 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 147
= 150
1500 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1500
= 1500
Somit gilt:
(147 + 1500) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (54 ⋅ 61) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(54 ⋅ 61) mod 6 ≡ (54 mod 6 ⋅ 61 mod 6) mod 6.
54 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 54 = 54 + 0 = 9 ⋅ 6 + 0 ist.
61 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 10 ⋅ 6 + 1 ist.
Somit gilt:
(54 ⋅ 61) mod 6 ≡ (0 ⋅ 1) mod 6 ≡ 0 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 17732 mod 521.
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. 177 -> x
2. mod(x²,521) -> 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: 1771=177
2: 1772=1771+1=1771⋅1771 ≡ 177⋅177=31329 ≡ 69 mod 521
4: 1774=1772+2=1772⋅1772 ≡ 69⋅69=4761 ≡ 72 mod 521
8: 1778=1774+4=1774⋅1774 ≡ 72⋅72=5184 ≡ 495 mod 521
16: 17716=1778+8=1778⋅1778 ≡ 495⋅495=245025 ≡ 155 mod 521
32: 17732=17716+16=17716⋅17716 ≡ 155⋅155=24025 ≡ 59 mod 521
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 470154 mod 577.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 154 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 154 an und zerlegen 154 in eine Summer von 2er-Potenzen:
154 = 128+16+8+2
1: 4701=470
2: 4702=4701+1=4701⋅4701 ≡ 470⋅470=220900 ≡ 486 mod 577
4: 4704=4702+2=4702⋅4702 ≡ 486⋅486=236196 ≡ 203 mod 577
8: 4708=4704+4=4704⋅4704 ≡ 203⋅203=41209 ≡ 242 mod 577
16: 47016=4708+8=4708⋅4708 ≡ 242⋅242=58564 ≡ 287 mod 577
32: 47032=47016+16=47016⋅47016 ≡ 287⋅287=82369 ≡ 435 mod 577
64: 47064=47032+32=47032⋅47032 ≡ 435⋅435=189225 ≡ 546 mod 577
128: 470128=47064+64=47064⋅47064 ≡ 546⋅546=298116 ≡ 384 mod 577
470154
= 470128+16+8+2
= 470128⋅47016⋅4708⋅4702
≡ 384 ⋅ 287 ⋅ 242 ⋅ 486 mod 577
≡ 110208 ⋅ 242 ⋅ 486 mod 577 ≡ 1 ⋅ 242 ⋅ 486 mod 577
≡ 242 ⋅ 486 mod 577
≡ 117612 mod 577 ≡ 481 mod 577
Es gilt also: 470154 ≡ 481 mod 577
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 86.
Also bestimme x, so dass 86 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 86
| =>97 | = 1⋅86 + 11 |
| =>86 | = 7⋅11 + 9 |
| =>11 | = 1⋅9 + 2 |
| =>9 | = 4⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(97,86)=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-4⋅2 | |||
| 2= 11-1⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -4⋅(11 -1⋅ 9)
= 1⋅9 -4⋅11 +4⋅ 9) = -4⋅11 +5⋅ 9 (=1) |
| 9= 86-7⋅11 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅11 +5⋅(86 -7⋅ 11)
= -4⋅11 +5⋅86 -35⋅ 11) = 5⋅86 -39⋅ 11 (=1) |
| 11= 97-1⋅86 | eingesetzt in die Zeile drüber: | 1 |
= 5⋅86 -39⋅(97 -1⋅ 86)
= 5⋅86 -39⋅97 +39⋅ 86) = -39⋅97 +44⋅ 86 (=1) |
Es gilt also: ggt(97,86)=1 = -39⋅97 +44⋅86
oder wenn man -39⋅97 auf die linke Seite bringt:
1 +39⋅97 = +44⋅86
Es gilt also: 44⋅86 = 39⋅97 +1
Somit 44⋅86 = 1 mod 97
44 ist also das Inverse von 86 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 89 und q = 67. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.