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: (1803 + 119) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1803 + 119) mod 6 ≡ (1803 mod 6 + 119 mod 6) mod 6.
1803 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 1803
= 1800
119 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 119
= 120
Somit gilt:
(1803 + 119) mod 6 ≡ (3 + 5) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (66 ⋅ 29) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(66 ⋅ 29) mod 11 ≡ (66 mod 11 ⋅ 29 mod 11) mod 11.
66 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 66 = 66 + 0 = 6 ⋅ 11 + 0 ist.
29 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 29 = 22 + 7 = 2 ⋅ 11 + 7 ist.
Somit gilt:
(66 ⋅ 29) mod 11 ≡ (0 ⋅ 7) mod 11 ≡ 0 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 11464 mod 229.
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. 114 -> x
2. mod(x²,229) -> 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: 1141=114
2: 1142=1141+1=1141⋅1141 ≡ 114⋅114=12996 ≡ 172 mod 229
4: 1144=1142+2=1142⋅1142 ≡ 172⋅172=29584 ≡ 43 mod 229
8: 1148=1144+4=1144⋅1144 ≡ 43⋅43=1849 ≡ 17 mod 229
16: 11416=1148+8=1148⋅1148 ≡ 17⋅17=289 ≡ 60 mod 229
32: 11432=11416+16=11416⋅11416 ≡ 60⋅60=3600 ≡ 165 mod 229
64: 11464=11432+32=11432⋅11432 ≡ 165⋅165=27225 ≡ 203 mod 229
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 208182 mod 281.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 182 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 182 an und zerlegen 182 in eine Summer von 2er-Potenzen:
182 = 128+32+16+4+2
1: 2081=208
2: 2082=2081+1=2081⋅2081 ≡ 208⋅208=43264 ≡ 271 mod 281
4: 2084=2082+2=2082⋅2082 ≡ 271⋅271=73441 ≡ 100 mod 281
8: 2088=2084+4=2084⋅2084 ≡ 100⋅100=10000 ≡ 165 mod 281
16: 20816=2088+8=2088⋅2088 ≡ 165⋅165=27225 ≡ 249 mod 281
32: 20832=20816+16=20816⋅20816 ≡ 249⋅249=62001 ≡ 181 mod 281
64: 20864=20832+32=20832⋅20832 ≡ 181⋅181=32761 ≡ 165 mod 281
128: 208128=20864+64=20864⋅20864 ≡ 165⋅165=27225 ≡ 249 mod 281
208182
= 208128+32+16+4+2
= 208128⋅20832⋅20816⋅2084⋅2082
≡ 249 ⋅ 181 ⋅ 249 ⋅ 100 ⋅ 271 mod 281
≡ 45069 ⋅ 249 ⋅ 100 ⋅ 271 mod 281 ≡ 109 ⋅ 249 ⋅ 100 ⋅ 271 mod 281
≡ 27141 ⋅ 100 ⋅ 271 mod 281 ≡ 165 ⋅ 100 ⋅ 271 mod 281
≡ 16500 ⋅ 271 mod 281 ≡ 202 ⋅ 271 mod 281
≡ 54742 mod 281 ≡ 228 mod 281
Es gilt also: 208182 ≡ 228 mod 281
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 27.
Also bestimme x, so dass 27 ⋅ x ≡ 1 mod 61 gilt:
Berechnung des größten gemeinsamen Teilers von 61 und 27
| =>61 | = 2⋅27 + 7 |
| =>27 | = 3⋅7 + 6 |
| =>7 | = 1⋅6 + 1 |
| =>6 | = 6⋅1 + 0 |
also gilt: ggt(61,27)=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= 7-1⋅6 | |||
| 6= 27-3⋅7 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅7 -1⋅(27 -3⋅ 7)
= 1⋅7 -1⋅27 +3⋅ 7) = -1⋅27 +4⋅ 7 (=1) |
| 7= 61-2⋅27 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅27 +4⋅(61 -2⋅ 27)
= -1⋅27 +4⋅61 -8⋅ 27) = 4⋅61 -9⋅ 27 (=1) |
Es gilt also: ggt(61,27)=1 = 4⋅61 -9⋅27
oder wenn man 4⋅61 auf die linke Seite bringt:
1 -4⋅61 = -9⋅27
-9⋅27 = -4⋅61 + 1 |+61⋅27
-9⋅27 + 61⋅27 = -4⋅61 + 61⋅27 + 1
(-9 + 61) ⋅ 27 = (-4 + 27) ⋅ 61 + 1
52⋅27 = 23⋅61 + 1
Es gilt also: 52⋅27 = 23⋅61 +1
Somit 52⋅27 = 1 mod 61
52 ist also das Inverse von 27 mod 61
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 67 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
