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: (3993 - 2394) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(3993 - 2394) mod 8 ≡ (3993 mod 8 - 2394 mod 8) mod 8.
3993 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 3993
= 4000
2394 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 2394
= 2400
Somit gilt:
(3993 - 2394) mod 8 ≡ (1 - 2) mod 8 ≡ -1 mod 8 ≡ 7 mod 8.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (36 ⋅ 34) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(36 ⋅ 34) mod 5 ≡ (36 mod 5 ⋅ 34 mod 5) mod 5.
36 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 36 = 35 + 1 = 7 ⋅ 5 + 1 ist.
34 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 34 = 30 + 4 = 6 ⋅ 5 + 4 ist.
Somit gilt:
(36 ⋅ 34) mod 5 ≡ (1 ⋅ 4) mod 5 ≡ 4 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 32964 mod 739.
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. 329 -> x
2. mod(x²,739) -> 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: 3291=329
2: 3292=3291+1=3291⋅3291 ≡ 329⋅329=108241 ≡ 347 mod 739
4: 3294=3292+2=3292⋅3292 ≡ 347⋅347=120409 ≡ 691 mod 739
8: 3298=3294+4=3294⋅3294 ≡ 691⋅691=477481 ≡ 87 mod 739
16: 32916=3298+8=3298⋅3298 ≡ 87⋅87=7569 ≡ 179 mod 739
32: 32932=32916+16=32916⋅32916 ≡ 179⋅179=32041 ≡ 264 mod 739
64: 32964=32932+32=32932⋅32932 ≡ 264⋅264=69696 ≡ 230 mod 739
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 219168 mod 683.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 168 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 168 an und zerlegen 168 in eine Summer von 2er-Potenzen:
168 = 128+32+8
1: 2191=219
2: 2192=2191+1=2191⋅2191 ≡ 219⋅219=47961 ≡ 151 mod 683
4: 2194=2192+2=2192⋅2192 ≡ 151⋅151=22801 ≡ 262 mod 683
8: 2198=2194+4=2194⋅2194 ≡ 262⋅262=68644 ≡ 344 mod 683
16: 21916=2198+8=2198⋅2198 ≡ 344⋅344=118336 ≡ 177 mod 683
32: 21932=21916+16=21916⋅21916 ≡ 177⋅177=31329 ≡ 594 mod 683
64: 21964=21932+32=21932⋅21932 ≡ 594⋅594=352836 ≡ 408 mod 683
128: 219128=21964+64=21964⋅21964 ≡ 408⋅408=166464 ≡ 495 mod 683
219168
= 219128+32+8
= 219128⋅21932⋅2198
≡ 495 ⋅ 594 ⋅ 344 mod 683
≡ 294030 ⋅ 344 mod 683 ≡ 340 ⋅ 344 mod 683
≡ 116960 mod 683 ≡ 167 mod 683
Es gilt also: 219168 ≡ 167 mod 683
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 56.
Also bestimme x, so dass 56 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 56
| =>101 | = 1⋅56 + 45 |
| =>56 | = 1⋅45 + 11 |
| =>45 | = 4⋅11 + 1 |
| =>11 | = 11⋅1 + 0 |
also gilt: ggt(101,56)=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= 45-4⋅11 | |||
| 11= 56-1⋅45 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅45 -4⋅(56 -1⋅ 45)
= 1⋅45 -4⋅56 +4⋅ 45) = -4⋅56 +5⋅ 45 (=1) |
| 45= 101-1⋅56 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅56 +5⋅(101 -1⋅ 56)
= -4⋅56 +5⋅101 -5⋅ 56) = 5⋅101 -9⋅ 56 (=1) |
Es gilt also: ggt(101,56)=1 = 5⋅101 -9⋅56
oder wenn man 5⋅101 auf die linke Seite bringt:
1 -5⋅101 = -9⋅56
-9⋅56 = -5⋅101 + 1 |+101⋅56
-9⋅56 + 101⋅56 = -5⋅101 + 101⋅56 + 1
(-9 + 101) ⋅ 56 = (-5 + 56) ⋅ 101 + 1
92⋅56 = 51⋅101 + 1
Es gilt also: 92⋅56 = 51⋅101 +1
Somit 92⋅56 = 1 mod 101
92 ist also das Inverse von 56 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 101 und q = 83. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.