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: (252 + 999) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(252 + 999) mod 5 ≡ (252 mod 5 + 999 mod 5) mod 5.
252 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 252
= 250
999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 999
= 900
Somit gilt:
(252 + 999) mod 5 ≡ (2 + 4) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (65 ⋅ 49) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(65 ⋅ 49) mod 5 ≡ (65 mod 5 ⋅ 49 mod 5) mod 5.
65 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 65 = 65 + 0 = 13 ⋅ 5 + 0 ist.
49 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 49 = 45 + 4 = 9 ⋅ 5 + 4 ist.
Somit gilt:
(65 ⋅ 49) mod 5 ≡ (0 ⋅ 4) mod 5 ≡ 0 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 31364 mod 709.
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. 313 -> 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: 3131=313
2: 3132=3131+1=3131⋅3131 ≡ 313⋅313=97969 ≡ 127 mod 709
4: 3134=3132+2=3132⋅3132 ≡ 127⋅127=16129 ≡ 531 mod 709
8: 3138=3134+4=3134⋅3134 ≡ 531⋅531=281961 ≡ 488 mod 709
16: 31316=3138+8=3138⋅3138 ≡ 488⋅488=238144 ≡ 629 mod 709
32: 31332=31316+16=31316⋅31316 ≡ 629⋅629=395641 ≡ 19 mod 709
64: 31364=31332+32=31332⋅31332 ≡ 19⋅19=361 ≡ 361 mod 709
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 521147 mod 607.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 147 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 147 an und zerlegen 147 in eine Summer von 2er-Potenzen:
147 = 128+16+2+1
1: 5211=521
2: 5212=5211+1=5211⋅5211 ≡ 521⋅521=271441 ≡ 112 mod 607
4: 5214=5212+2=5212⋅5212 ≡ 112⋅112=12544 ≡ 404 mod 607
8: 5218=5214+4=5214⋅5214 ≡ 404⋅404=163216 ≡ 540 mod 607
16: 52116=5218+8=5218⋅5218 ≡ 540⋅540=291600 ≡ 240 mod 607
32: 52132=52116+16=52116⋅52116 ≡ 240⋅240=57600 ≡ 542 mod 607
64: 52164=52132+32=52132⋅52132 ≡ 542⋅542=293764 ≡ 583 mod 607
128: 521128=52164+64=52164⋅52164 ≡ 583⋅583=339889 ≡ 576 mod 607
521147
= 521128+16+2+1
= 521128⋅52116⋅5212⋅5211
≡ 576 ⋅ 240 ⋅ 112 ⋅ 521 mod 607
≡ 138240 ⋅ 112 ⋅ 521 mod 607 ≡ 451 ⋅ 112 ⋅ 521 mod 607
≡ 50512 ⋅ 521 mod 607 ≡ 131 ⋅ 521 mod 607
≡ 68251 mod 607 ≡ 267 mod 607
Es gilt also: 521147 ≡ 267 mod 607
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 86.
Also bestimme x, so dass 86 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 86
| =>89 | = 1⋅86 + 3 |
| =>86 | = 28⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(89,86)=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= 3-1⋅2 | |||
| 2= 86-28⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(86 -28⋅ 3)
= 1⋅3 -1⋅86 +28⋅ 3) = -1⋅86 +29⋅ 3 (=1) |
| 3= 89-1⋅86 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅86 +29⋅(89 -1⋅ 86)
= -1⋅86 +29⋅89 -29⋅ 86) = 29⋅89 -30⋅ 86 (=1) |
Es gilt also: ggt(89,86)=1 = 29⋅89 -30⋅86
oder wenn man 29⋅89 auf die linke Seite bringt:
1 -29⋅89 = -30⋅86
-30⋅86 = -29⋅89 + 1 |+89⋅86
-30⋅86 + 89⋅86 = -29⋅89 + 89⋅86 + 1
(-30 + 89) ⋅ 86 = (-29 + 86) ⋅ 89 + 1
59⋅86 = 57⋅89 + 1
Es gilt also: 59⋅86 = 57⋅89 +1
Somit 59⋅86 = 1 mod 89
59 ist also das Inverse von 86 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 47 und q = 59. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
