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: (701 + 2102) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(701 + 2102) mod 7 ≡ (701 mod 7 + 2102 mod 7) mod 7.
701 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 701
= 700
2102 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 2102
= 2100
Somit gilt:
(701 + 2102) mod 7 ≡ (1 + 2) mod 7 ≡ 3 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (64 ⋅ 88) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(64 ⋅ 88) mod 7 ≡ (64 mod 7 ⋅ 88 mod 7) mod 7.
64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 9 ⋅ 7 + 1 ist.
88 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 88 = 84 + 4 = 12 ⋅ 7 + 4 ist.
Somit gilt:
(64 ⋅ 88) mod 7 ≡ (1 ⋅ 4) mod 7 ≡ 4 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 41664 mod 617.
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. 416 -> x
2. mod(x²,617) -> 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: 4161=416
2: 4162=4161+1=4161⋅4161 ≡ 416⋅416=173056 ≡ 296 mod 617
4: 4164=4162+2=4162⋅4162 ≡ 296⋅296=87616 ≡ 2 mod 617
8: 4168=4164+4=4164⋅4164 ≡ 2⋅2=4 ≡ 4 mod 617
16: 41616=4168+8=4168⋅4168 ≡ 4⋅4=16 ≡ 16 mod 617
32: 41632=41616+16=41616⋅41616 ≡ 16⋅16=256 ≡ 256 mod 617
64: 41664=41632+32=41632⋅41632 ≡ 256⋅256=65536 ≡ 134 mod 617
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 369170 mod 839.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 170 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 170 an und zerlegen 170 in eine Summer von 2er-Potenzen:
170 = 128+32+8+2
1: 3691=369
2: 3692=3691+1=3691⋅3691 ≡ 369⋅369=136161 ≡ 243 mod 839
4: 3694=3692+2=3692⋅3692 ≡ 243⋅243=59049 ≡ 319 mod 839
8: 3698=3694+4=3694⋅3694 ≡ 319⋅319=101761 ≡ 242 mod 839
16: 36916=3698+8=3698⋅3698 ≡ 242⋅242=58564 ≡ 673 mod 839
32: 36932=36916+16=36916⋅36916 ≡ 673⋅673=452929 ≡ 708 mod 839
64: 36964=36932+32=36932⋅36932 ≡ 708⋅708=501264 ≡ 381 mod 839
128: 369128=36964+64=36964⋅36964 ≡ 381⋅381=145161 ≡ 14 mod 839
369170
= 369128+32+8+2
= 369128⋅36932⋅3698⋅3692
≡ 14 ⋅ 708 ⋅ 242 ⋅ 243 mod 839
≡ 9912 ⋅ 242 ⋅ 243 mod 839 ≡ 683 ⋅ 242 ⋅ 243 mod 839
≡ 165286 ⋅ 243 mod 839 ≡ 3 ⋅ 243 mod 839
≡ 729 mod 839
Es gilt also: 369170 ≡ 729 mod 839
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 59.
Also bestimme x, so dass 59 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 59
| =>101 | = 1⋅59 + 42 |
| =>59 | = 1⋅42 + 17 |
| =>42 | = 2⋅17 + 8 |
| =>17 | = 2⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(101,59)=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= 17-2⋅8 | |||
| 8= 42-2⋅17 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅17 -2⋅(42 -2⋅ 17)
= 1⋅17 -2⋅42 +4⋅ 17) = -2⋅42 +5⋅ 17 (=1) |
| 17= 59-1⋅42 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅42 +5⋅(59 -1⋅ 42)
= -2⋅42 +5⋅59 -5⋅ 42) = 5⋅59 -7⋅ 42 (=1) |
| 42= 101-1⋅59 | eingesetzt in die Zeile drüber: | 1 |
= 5⋅59 -7⋅(101 -1⋅ 59)
= 5⋅59 -7⋅101 +7⋅ 59) = -7⋅101 +12⋅ 59 (=1) |
Es gilt also: ggt(101,59)=1 = -7⋅101 +12⋅59
oder wenn man -7⋅101 auf die linke Seite bringt:
1 +7⋅101 = +12⋅59
Es gilt also: 12⋅59 = 7⋅101 +1
Somit 12⋅59 = 1 mod 101
12 ist also das Inverse von 59 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 59 und q = 53. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
