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: (121 + 81) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(121 + 81) mod 4 ≡ (121 mod 4 + 81 mod 4) mod 4.
121 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 121
= 120
81 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 81
= 80
Somit gilt:
(121 + 81) mod 4 ≡ (1 + 1) mod 4 ≡ 2 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (39 ⋅ 51) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(39 ⋅ 51) mod 3 ≡ (39 mod 3 ⋅ 51 mod 3) mod 3.
39 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 39 = 39 + 0 = 13 ⋅ 3 + 0 ist.
51 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 51 = 51 + 0 = 17 ⋅ 3 + 0 ist.
Somit gilt:
(39 ⋅ 51) mod 3 ≡ (0 ⋅ 0) mod 3 ≡ 0 mod 3.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 14532 mod 421.
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. 145 -> x
2. mod(x²,421) -> 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: 1451=145
2: 1452=1451+1=1451⋅1451 ≡ 145⋅145=21025 ≡ 396 mod 421
4: 1454=1452+2=1452⋅1452 ≡ 396⋅396=156816 ≡ 204 mod 421
8: 1458=1454+4=1454⋅1454 ≡ 204⋅204=41616 ≡ 358 mod 421
16: 14516=1458+8=1458⋅1458 ≡ 358⋅358=128164 ≡ 180 mod 421
32: 14532=14516+16=14516⋅14516 ≡ 180⋅180=32400 ≡ 404 mod 421
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 369209 mod 607.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 209 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 209 an und zerlegen 209 in eine Summer von 2er-Potenzen:
209 = 128+64+16+1
1: 3691=369
2: 3692=3691+1=3691⋅3691 ≡ 369⋅369=136161 ≡ 193 mod 607
4: 3694=3692+2=3692⋅3692 ≡ 193⋅193=37249 ≡ 222 mod 607
8: 3698=3694+4=3694⋅3694 ≡ 222⋅222=49284 ≡ 117 mod 607
16: 36916=3698+8=3698⋅3698 ≡ 117⋅117=13689 ≡ 335 mod 607
32: 36932=36916+16=36916⋅36916 ≡ 335⋅335=112225 ≡ 537 mod 607
64: 36964=36932+32=36932⋅36932 ≡ 537⋅537=288369 ≡ 44 mod 607
128: 369128=36964+64=36964⋅36964 ≡ 44⋅44=1936 ≡ 115 mod 607
369209
= 369128+64+16+1
= 369128⋅36964⋅36916⋅3691
≡ 115 ⋅ 44 ⋅ 335 ⋅ 369 mod 607
≡ 5060 ⋅ 335 ⋅ 369 mod 607 ≡ 204 ⋅ 335 ⋅ 369 mod 607
≡ 68340 ⋅ 369 mod 607 ≡ 356 ⋅ 369 mod 607
≡ 131364 mod 607 ≡ 252 mod 607
Es gilt also: 369209 ≡ 252 mod 607
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 72.
Also bestimme x, so dass 72 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 72
| =>97 | = 1⋅72 + 25 |
| =>72 | = 2⋅25 + 22 |
| =>25 | = 1⋅22 + 3 |
| =>22 | = 7⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(97,72)=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= 22-7⋅3 | |||
| 3= 25-1⋅22 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅22 -7⋅(25 -1⋅ 22)
= 1⋅22 -7⋅25 +7⋅ 22) = -7⋅25 +8⋅ 22 (=1) |
| 22= 72-2⋅25 | eingesetzt in die Zeile drüber: | 1 |
= -7⋅25 +8⋅(72 -2⋅ 25)
= -7⋅25 +8⋅72 -16⋅ 25) = 8⋅72 -23⋅ 25 (=1) |
| 25= 97-1⋅72 | eingesetzt in die Zeile drüber: | 1 |
= 8⋅72 -23⋅(97 -1⋅ 72)
= 8⋅72 -23⋅97 +23⋅ 72) = -23⋅97 +31⋅ 72 (=1) |
Es gilt also: ggt(97,72)=1 = -23⋅97 +31⋅72
oder wenn man -23⋅97 auf die linke Seite bringt:
1 +23⋅97 = +31⋅72
Es gilt also: 31⋅72 = 23⋅97 +1
Somit 31⋅72 = 1 mod 97
31 ist also das Inverse von 72 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 37 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
