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: (363 + 1795) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(363 + 1795) mod 9 ≡ (363 mod 9 + 1795 mod 9) mod 9.
363 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 363
= 360
1795 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 1795
= 1800
Somit gilt:
(363 + 1795) mod 9 ≡ (3 + 4) mod 9 ≡ 7 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (94 ⋅ 42) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(94 ⋅ 42) mod 5 ≡ (94 mod 5 ⋅ 42 mod 5) mod 5.
94 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 94 = 90 + 4 = 18 ⋅ 5 + 4 ist.
42 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 42 = 40 + 2 = 8 ⋅ 5 + 2 ist.
Somit gilt:
(94 ⋅ 42) mod 5 ≡ (4 ⋅ 2) mod 5 ≡ 8 mod 5 ≡ 3 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 92416 mod 967.
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. 924 -> x
2. mod(x²,967) -> 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: 9241=924
2: 9242=9241+1=9241⋅9241 ≡ 924⋅924=853776 ≡ 882 mod 967
4: 9244=9242+2=9242⋅9242 ≡ 882⋅882=777924 ≡ 456 mod 967
8: 9248=9244+4=9244⋅9244 ≡ 456⋅456=207936 ≡ 31 mod 967
16: 92416=9248+8=9248⋅9248 ≡ 31⋅31=961 ≡ 961 mod 967
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 105161 mod 347.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 161 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 161 an und zerlegen 161 in eine Summer von 2er-Potenzen:
161 = 128+32+1
1: 1051=105
2: 1052=1051+1=1051⋅1051 ≡ 105⋅105=11025 ≡ 268 mod 347
4: 1054=1052+2=1052⋅1052 ≡ 268⋅268=71824 ≡ 342 mod 347
8: 1058=1054+4=1054⋅1054 ≡ 342⋅342=116964 ≡ 25 mod 347
16: 10516=1058+8=1058⋅1058 ≡ 25⋅25=625 ≡ 278 mod 347
32: 10532=10516+16=10516⋅10516 ≡ 278⋅278=77284 ≡ 250 mod 347
64: 10564=10532+32=10532⋅10532 ≡ 250⋅250=62500 ≡ 40 mod 347
128: 105128=10564+64=10564⋅10564 ≡ 40⋅40=1600 ≡ 212 mod 347
105161
= 105128+32+1
= 105128⋅10532⋅1051
≡ 212 ⋅ 250 ⋅ 105 mod 347
≡ 53000 ⋅ 105 mod 347 ≡ 256 ⋅ 105 mod 347
≡ 26880 mod 347 ≡ 161 mod 347
Es gilt also: 105161 ≡ 161 mod 347
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-53-Inverse zur Zahl 21.
Also bestimme x, so dass 21 ⋅ x ≡ 1 mod 53 gilt:
Berechnung des größten gemeinsamen Teilers von 53 und 21
| =>53 | = 2⋅21 + 11 |
| =>21 | = 1⋅11 + 10 |
| =>11 | = 1⋅10 + 1 |
| =>10 | = 10⋅1 + 0 |
also gilt: ggt(53,21)=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= 11-1⋅10 | |||
| 10= 21-1⋅11 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅11 -1⋅(21 -1⋅ 11)
= 1⋅11 -1⋅21 +1⋅ 11) = -1⋅21 +2⋅ 11 (=1) |
| 11= 53-2⋅21 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅21 +2⋅(53 -2⋅ 21)
= -1⋅21 +2⋅53 -4⋅ 21) = 2⋅53 -5⋅ 21 (=1) |
Es gilt also: ggt(53,21)=1 = 2⋅53 -5⋅21
oder wenn man 2⋅53 auf die linke Seite bringt:
1 -2⋅53 = -5⋅21
-5⋅21 = -2⋅53 + 1 |+53⋅21
-5⋅21 + 53⋅21 = -2⋅53 + 53⋅21 + 1
(-5 + 53) ⋅ 21 = (-2 + 21) ⋅ 53 + 1
48⋅21 = 19⋅53 + 1
Es gilt also: 48⋅21 = 19⋅53 +1
Somit 48⋅21 = 1 mod 53
48 ist also das Inverse von 21 mod 53
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 73. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.