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: (99 - 10000) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(99 - 10000) mod 5 ≡ (99 mod 5 - 10000 mod 5) mod 5.
99 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 99
= 90
10000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 10000
= 10000
Somit gilt:
(99 - 10000) mod 5 ≡ (4 - 0) mod 5 ≡ 4 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (58 ⋅ 17) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(58 ⋅ 17) mod 10 ≡ (58 mod 10 ⋅ 17 mod 10) mod 10.
58 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 58 = 50 + 8 = 5 ⋅ 10 + 8 ist.
17 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 17 = 10 + 7 = 1 ⋅ 10 + 7 ist.
Somit gilt:
(58 ⋅ 17) mod 10 ≡ (8 ⋅ 7) mod 10 ≡ 56 mod 10 ≡ 6 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 51432 mod 677.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 514 -> x
2. mod(x²,677) -> 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: 5141=514
2: 5142=5141+1=5141⋅5141 ≡ 514⋅514=264196 ≡ 166 mod 677
4: 5144=5142+2=5142⋅5142 ≡ 166⋅166=27556 ≡ 476 mod 677
8: 5148=5144+4=5144⋅5144 ≡ 476⋅476=226576 ≡ 458 mod 677
16: 51416=5148+8=5148⋅5148 ≡ 458⋅458=209764 ≡ 571 mod 677
32: 51432=51416+16=51416⋅51416 ≡ 571⋅571=326041 ≡ 404 mod 677
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 206116 mod 313.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 116 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 116 an und zerlegen 116 in eine Summer von 2er-Potenzen:
116 = 64+32+16+4
1: 2061=206
2: 2062=2061+1=2061⋅2061 ≡ 206⋅206=42436 ≡ 181 mod 313
4: 2064=2062+2=2062⋅2062 ≡ 181⋅181=32761 ≡ 209 mod 313
8: 2068=2064+4=2064⋅2064 ≡ 209⋅209=43681 ≡ 174 mod 313
16: 20616=2068+8=2068⋅2068 ≡ 174⋅174=30276 ≡ 228 mod 313
32: 20632=20616+16=20616⋅20616 ≡ 228⋅228=51984 ≡ 26 mod 313
64: 20664=20632+32=20632⋅20632 ≡ 26⋅26=676 ≡ 50 mod 313
206116
= 20664+32+16+4
= 20664⋅20632⋅20616⋅2064
≡ 50 ⋅ 26 ⋅ 228 ⋅ 209 mod 313
≡ 1300 ⋅ 228 ⋅ 209 mod 313 ≡ 48 ⋅ 228 ⋅ 209 mod 313
≡ 10944 ⋅ 209 mod 313 ≡ 302 ⋅ 209 mod 313
≡ 63118 mod 313 ≡ 205 mod 313
Es gilt also: 206116 ≡ 205 mod 313
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 77.
Also bestimme x, so dass 77 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 77
| =>83 | = 1⋅77 + 6 |
| =>77 | = 12⋅6 + 5 |
| =>6 | = 1⋅5 + 1 |
| =>5 | = 5⋅1 + 0 |
also gilt: ggt(83,77)=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= 6-1⋅5 | |||
| 5= 77-12⋅6 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅6 -1⋅(77 -12⋅ 6)
= 1⋅6 -1⋅77 +12⋅ 6) = -1⋅77 +13⋅ 6 (=1) |
| 6= 83-1⋅77 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅77 +13⋅(83 -1⋅ 77)
= -1⋅77 +13⋅83 -13⋅ 77) = 13⋅83 -14⋅ 77 (=1) |
Es gilt also: ggt(83,77)=1 = 13⋅83 -14⋅77
oder wenn man 13⋅83 auf die linke Seite bringt:
1 -13⋅83 = -14⋅77
-14⋅77 = -13⋅83 + 1 |+83⋅77
-14⋅77 + 83⋅77 = -13⋅83 + 83⋅77 + 1
(-14 + 83) ⋅ 77 = (-13 + 77) ⋅ 83 + 1
69⋅77 = 64⋅83 + 1
Es gilt also: 69⋅77 = 64⋅83 +1
Somit 69⋅77 = 1 mod 83
69 ist also das Inverse von 77 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 37 und q = 31. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
