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: (232 + 1594) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(232 + 1594) mod 8 ≡ (232 mod 8 + 1594 mod 8) mod 8.
232 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 232
= 240
1594 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 1594
= 1600
Somit gilt:
(232 + 1594) mod 8 ≡ (0 + 2) mod 8 ≡ 2 mod 8.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (35 ⋅ 30) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(35 ⋅ 30) mod 11 ≡ (35 mod 11 ⋅ 30 mod 11) mod 11.
35 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 35 = 33 + 2 = 3 ⋅ 11 + 2 ist.
30 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 30 = 22 + 8 = 2 ⋅ 11 + 8 ist.
Somit gilt:
(35 ⋅ 30) mod 11 ≡ (2 ⋅ 8) mod 11 ≡ 16 mod 11 ≡ 5 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 39764 mod 857.
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. 397 -> x
2. mod(x²,857) -> 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: 3971=397
2: 3972=3971+1=3971⋅3971 ≡ 397⋅397=157609 ≡ 778 mod 857
4: 3974=3972+2=3972⋅3972 ≡ 778⋅778=605284 ≡ 242 mod 857
8: 3978=3974+4=3974⋅3974 ≡ 242⋅242=58564 ≡ 288 mod 857
16: 39716=3978+8=3978⋅3978 ≡ 288⋅288=82944 ≡ 672 mod 857
32: 39732=39716+16=39716⋅39716 ≡ 672⋅672=451584 ≡ 802 mod 857
64: 39764=39732+32=39732⋅39732 ≡ 802⋅802=643204 ≡ 454 mod 857
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 495116 mod 827.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 116 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 116 an und zerlegen 116 in eine Summer von 2er-Potenzen:
116 = 64+32+16+4
1: 4951=495
2: 4952=4951+1=4951⋅4951 ≡ 495⋅495=245025 ≡ 233 mod 827
4: 4954=4952+2=4952⋅4952 ≡ 233⋅233=54289 ≡ 534 mod 827
8: 4958=4954+4=4954⋅4954 ≡ 534⋅534=285156 ≡ 668 mod 827
16: 49516=4958+8=4958⋅4958 ≡ 668⋅668=446224 ≡ 471 mod 827
32: 49532=49516+16=49516⋅49516 ≡ 471⋅471=221841 ≡ 205 mod 827
64: 49564=49532+32=49532⋅49532 ≡ 205⋅205=42025 ≡ 675 mod 827
495116
= 49564+32+16+4
= 49564⋅49532⋅49516⋅4954
≡ 675 ⋅ 205 ⋅ 471 ⋅ 534 mod 827
≡ 138375 ⋅ 471 ⋅ 534 mod 827 ≡ 266 ⋅ 471 ⋅ 534 mod 827
≡ 125286 ⋅ 534 mod 827 ≡ 409 ⋅ 534 mod 827
≡ 218406 mod 827 ≡ 78 mod 827
Es gilt also: 495116 ≡ 78 mod 827
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 32.
Also bestimme x, so dass 32 ⋅ x ≡ 1 mod 73 gilt:
Berechnung des größten gemeinsamen Teilers von 73 und 32
| =>73 | = 2⋅32 + 9 |
| =>32 | = 3⋅9 + 5 |
| =>9 | = 1⋅5 + 4 |
| =>5 | = 1⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(73,32)=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= 5-1⋅4 | |||
| 4= 9-1⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -1⋅(9 -1⋅ 5)
= 1⋅5 -1⋅9 +1⋅ 5) = -1⋅9 +2⋅ 5 (=1) |
| 5= 32-3⋅9 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅9 +2⋅(32 -3⋅ 9)
= -1⋅9 +2⋅32 -6⋅ 9) = 2⋅32 -7⋅ 9 (=1) |
| 9= 73-2⋅32 | eingesetzt in die Zeile drüber: | 1 |
= 2⋅32 -7⋅(73 -2⋅ 32)
= 2⋅32 -7⋅73 +14⋅ 32) = -7⋅73 +16⋅ 32 (=1) |
Es gilt also: ggt(73,32)=1 = -7⋅73 +16⋅32
oder wenn man -7⋅73 auf die linke Seite bringt:
1 +7⋅73 = +16⋅32
Es gilt also: 16⋅32 = 7⋅73 +1
Somit 16⋅32 = 1 mod 73
16 ist also das Inverse von 32 mod 73
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 31 und q = 79. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.