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: (24005 + 29997) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(24005 + 29997) mod 6 ≡ (24005 mod 6 + 29997 mod 6) mod 6.
24005 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 24005
= 24000
29997 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 29997
= 30000
Somit gilt:
(24005 + 29997) mod 6 ≡ (5 + 3) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (79 ⋅ 33) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(79 ⋅ 33) mod 8 ≡ (79 mod 8 ⋅ 33 mod 8) mod 8.
79 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 79 = 72 + 7 = 9 ⋅ 8 + 7 ist.
33 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 33 = 32 + 1 = 4 ⋅ 8 + 1 ist.
Somit gilt:
(79 ⋅ 33) mod 8 ≡ (7 ⋅ 1) mod 8 ≡ 7 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 6858 mod 967.
Die 8 im Exponent ist ja ein reine 2er-Potenz (23).
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. 685 -> x
2. mod(x²,967) -> 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: 6851=685
2: 6852=6851+1=6851⋅6851 ≡ 685⋅685=469225 ≡ 230 mod 967
4: 6854=6852+2=6852⋅6852 ≡ 230⋅230=52900 ≡ 682 mod 967
8: 6858=6854+4=6854⋅6854 ≡ 682⋅682=465124 ≡ 964 mod 967
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 55476 mod 701.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 76 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 76 an und zerlegen 76 in eine Summer von 2er-Potenzen:
76 = 64+8+4
1: 5541=554
2: 5542=5541+1=5541⋅5541 ≡ 554⋅554=306916 ≡ 579 mod 701
4: 5544=5542+2=5542⋅5542 ≡ 579⋅579=335241 ≡ 163 mod 701
8: 5548=5544+4=5544⋅5544 ≡ 163⋅163=26569 ≡ 632 mod 701
16: 55416=5548+8=5548⋅5548 ≡ 632⋅632=399424 ≡ 555 mod 701
32: 55432=55416+16=55416⋅55416 ≡ 555⋅555=308025 ≡ 286 mod 701
64: 55464=55432+32=55432⋅55432 ≡ 286⋅286=81796 ≡ 480 mod 701
55476
= 55464+8+4
= 55464⋅5548⋅5544
≡ 480 ⋅ 632 ⋅ 163 mod 701
≡ 303360 ⋅ 163 mod 701 ≡ 528 ⋅ 163 mod 701
≡ 86064 mod 701 ≡ 542 mod 701
Es gilt also: 55476 ≡ 542 mod 701
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-53-Inverse zur Zahl 28.
Also bestimme x, so dass 28 ⋅ x ≡ 1 mod 53 gilt:
Berechnung des größten gemeinsamen Teilers von 53 und 28
| =>53 | = 1⋅28 + 25 |
| =>28 | = 1⋅25 + 3 |
| =>25 | = 8⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(53,28)=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= 25-8⋅3 | |||
| 3= 28-1⋅25 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅25 -8⋅(28 -1⋅ 25)
= 1⋅25 -8⋅28 +8⋅ 25) = -8⋅28 +9⋅ 25 (=1) |
| 25= 53-1⋅28 | eingesetzt in die Zeile drüber: | 1 |
= -8⋅28 +9⋅(53 -1⋅ 28)
= -8⋅28 +9⋅53 -9⋅ 28) = 9⋅53 -17⋅ 28 (=1) |
Es gilt also: ggt(53,28)=1 = 9⋅53 -17⋅28
oder wenn man 9⋅53 auf die linke Seite bringt:
1 -9⋅53 = -17⋅28
-17⋅28 = -9⋅53 + 1 |+53⋅28
-17⋅28 + 53⋅28 = -9⋅53 + 53⋅28 + 1
(-17 + 53) ⋅ 28 = (-9 + 28) ⋅ 53 + 1
36⋅28 = 19⋅53 + 1
Es gilt also: 36⋅28 = 19⋅53 +1
Somit 36⋅28 = 1 mod 53
36 ist also das Inverse von 28 mod 53
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 59. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.