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: (60 - 32) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(60 - 32) mod 3 ≡ (60 mod 3 - 32 mod 3) mod 3.
60 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 60
= 60
32 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 32
= 30
Somit gilt:
(60 - 32) mod 3 ≡ (0 - 2) mod 3 ≡ -2 mod 3 ≡ 1 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (18 ⋅ 95) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(18 ⋅ 95) mod 10 ≡ (18 mod 10 ⋅ 95 mod 10) mod 10.
18 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 18 = 10 + 8 = 1 ⋅ 10 + 8 ist.
95 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 95 = 90 + 5 = 9 ⋅ 10 + 5 ist.
Somit gilt:
(18 ⋅ 95) mod 10 ≡ (8 ⋅ 5) mod 10 ≡ 40 mod 10 ≡ 0 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 605128 mod 929.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 605 -> x
2. mod(x²,929) -> 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: 6051=605
2: 6052=6051+1=6051⋅6051 ≡ 605⋅605=366025 ≡ 928 mod 929
4: 6054=6052+2=6052⋅6052 ≡ 928⋅928=861184 ≡ 1 mod 929
8: 6058=6054+4=6054⋅6054 ≡ 1⋅1=1 ≡ 1 mod 929
16: 60516=6058+8=6058⋅6058 ≡ 1⋅1=1 ≡ 1 mod 929
32: 60532=60516+16=60516⋅60516 ≡ 1⋅1=1 ≡ 1 mod 929
64: 60564=60532+32=60532⋅60532 ≡ 1⋅1=1 ≡ 1 mod 929
128: 605128=60564+64=60564⋅60564 ≡ 1⋅1=1 ≡ 1 mod 929
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 311201 mod 877.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 201 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 201 an und zerlegen 201 in eine Summer von 2er-Potenzen:
201 = 128+64+8+1
1: 3111=311
2: 3112=3111+1=3111⋅3111 ≡ 311⋅311=96721 ≡ 251 mod 877
4: 3114=3112+2=3112⋅3112 ≡ 251⋅251=63001 ≡ 734 mod 877
8: 3118=3114+4=3114⋅3114 ≡ 734⋅734=538756 ≡ 278 mod 877
16: 31116=3118+8=3118⋅3118 ≡ 278⋅278=77284 ≡ 108 mod 877
32: 31132=31116+16=31116⋅31116 ≡ 108⋅108=11664 ≡ 263 mod 877
64: 31164=31132+32=31132⋅31132 ≡ 263⋅263=69169 ≡ 763 mod 877
128: 311128=31164+64=31164⋅31164 ≡ 763⋅763=582169 ≡ 718 mod 877
311201
= 311128+64+8+1
= 311128⋅31164⋅3118⋅3111
≡ 718 ⋅ 763 ⋅ 278 ⋅ 311 mod 877
≡ 547834 ⋅ 278 ⋅ 311 mod 877 ≡ 586 ⋅ 278 ⋅ 311 mod 877
≡ 162908 ⋅ 311 mod 877 ≡ 663 ⋅ 311 mod 877
≡ 206193 mod 877 ≡ 98 mod 877
Es gilt also: 311201 ≡ 98 mod 877
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 72.
Also bestimme x, so dass 72 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 72
| =>89 | = 1⋅72 + 17 |
| =>72 | = 4⋅17 + 4 |
| =>17 | = 4⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(89,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= 17-4⋅4 | |||
| 4= 72-4⋅17 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅17 -4⋅(72 -4⋅ 17)
= 1⋅17 -4⋅72 +16⋅ 17) = -4⋅72 +17⋅ 17 (=1) |
| 17= 89-1⋅72 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅72 +17⋅(89 -1⋅ 72)
= -4⋅72 +17⋅89 -17⋅ 72) = 17⋅89 -21⋅ 72 (=1) |
Es gilt also: ggt(89,72)=1 = 17⋅89 -21⋅72
oder wenn man 17⋅89 auf die linke Seite bringt:
1 -17⋅89 = -21⋅72
-21⋅72 = -17⋅89 + 1 |+89⋅72
-21⋅72 + 89⋅72 = -17⋅89 + 89⋅72 + 1
(-21 + 89) ⋅ 72 = (-17 + 72) ⋅ 89 + 1
68⋅72 = 55⋅89 + 1
Es gilt also: 68⋅72 = 55⋅89 +1
Somit 68⋅72 = 1 mod 89
68 ist also das Inverse von 72 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 101 und q = 73. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
