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: (2001 + 400) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2001 + 400) mod 4 ≡ (2001 mod 4 + 400 mod 4) mod 4.
2001 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 2001
= 2000
400 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 400
= 400
Somit gilt:
(2001 + 400) mod 4 ≡ (1 + 0) mod 4 ≡ 1 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (22 ⋅ 75) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(22 ⋅ 75) mod 11 ≡ (22 mod 11 ⋅ 75 mod 11) mod 11.
22 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 22 = 22 + 0 = 2 ⋅ 11 + 0 ist.
75 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 75 = 66 + 9 = 6 ⋅ 11 + 9 ist.
Somit gilt:
(22 ⋅ 75) mod 11 ≡ (0 ⋅ 9) mod 11 ≡ 0 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 65616 mod 709.
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. 656 -> x
2. mod(x²,709) -> 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: 6561=656
2: 6562=6561+1=6561⋅6561 ≡ 656⋅656=430336 ≡ 682 mod 709
4: 6564=6562+2=6562⋅6562 ≡ 682⋅682=465124 ≡ 20 mod 709
8: 6568=6564+4=6564⋅6564 ≡ 20⋅20=400 ≡ 400 mod 709
16: 65616=6568+8=6568⋅6568 ≡ 400⋅400=160000 ≡ 475 mod 709
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 161153 mod 211.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 153 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 153 an und zerlegen 153 in eine Summer von 2er-Potenzen:
153 = 128+16+8+1
1: 1611=161
2: 1612=1611+1=1611⋅1611 ≡ 161⋅161=25921 ≡ 179 mod 211
4: 1614=1612+2=1612⋅1612 ≡ 179⋅179=32041 ≡ 180 mod 211
8: 1618=1614+4=1614⋅1614 ≡ 180⋅180=32400 ≡ 117 mod 211
16: 16116=1618+8=1618⋅1618 ≡ 117⋅117=13689 ≡ 185 mod 211
32: 16132=16116+16=16116⋅16116 ≡ 185⋅185=34225 ≡ 43 mod 211
64: 16164=16132+32=16132⋅16132 ≡ 43⋅43=1849 ≡ 161 mod 211
128: 161128=16164+64=16164⋅16164 ≡ 161⋅161=25921 ≡ 179 mod 211
161153
= 161128+16+8+1
= 161128⋅16116⋅1618⋅1611
≡ 179 ⋅ 185 ⋅ 117 ⋅ 161 mod 211
≡ 33115 ⋅ 117 ⋅ 161 mod 211 ≡ 199 ⋅ 117 ⋅ 161 mod 211
≡ 23283 ⋅ 161 mod 211 ≡ 73 ⋅ 161 mod 211
≡ 11753 mod 211 ≡ 148 mod 211
Es gilt also: 161153 ≡ 148 mod 211
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 82.
Also bestimme x, so dass 82 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 82
| =>101 | = 1⋅82 + 19 |
| =>82 | = 4⋅19 + 6 |
| =>19 | = 3⋅6 + 1 |
| =>6 | = 6⋅1 + 0 |
also gilt: ggt(101,82)=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= 19-3⋅6 | |||
| 6= 82-4⋅19 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅19 -3⋅(82 -4⋅ 19)
= 1⋅19 -3⋅82 +12⋅ 19) = -3⋅82 +13⋅ 19 (=1) |
| 19= 101-1⋅82 | eingesetzt in die Zeile drüber: | 1 |
= -3⋅82 +13⋅(101 -1⋅ 82)
= -3⋅82 +13⋅101 -13⋅ 82) = 13⋅101 -16⋅ 82 (=1) |
Es gilt also: ggt(101,82)=1 = 13⋅101 -16⋅82
oder wenn man 13⋅101 auf die linke Seite bringt:
1 -13⋅101 = -16⋅82
-16⋅82 = -13⋅101 + 1 |+101⋅82
-16⋅82 + 101⋅82 = -13⋅101 + 101⋅82 + 1
(-16 + 101) ⋅ 82 = (-13 + 82) ⋅ 101 + 1
85⋅82 = 69⋅101 + 1
Es gilt also: 85⋅82 = 69⋅101 +1
Somit 85⋅82 = 1 mod 101
85 ist also das Inverse von 82 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 73 und q = 101. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.