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: (15996 - 164) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(15996 - 164) mod 4 ≡ (15996 mod 4 - 164 mod 4) mod 4.
15996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 15996
= 15000
164 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 164
= 160
Somit gilt:
(15996 - 164) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (48 ⋅ 25) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(48 ⋅ 25) mod 7 ≡ (48 mod 7 ⋅ 25 mod 7) mod 7.
48 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 48 = 42 + 6 = 6 ⋅ 7 + 6 ist.
25 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 25 = 21 + 4 = 3 ⋅ 7 + 4 ist.
Somit gilt:
(48 ⋅ 25) mod 7 ≡ (6 ⋅ 4) mod 7 ≡ 24 mod 7 ≡ 3 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 5568 mod 761.
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. 556 -> x
2. mod(x²,761) -> 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: 5561=556
2: 5562=5561+1=5561⋅5561 ≡ 556⋅556=309136 ≡ 170 mod 761
4: 5564=5562+2=5562⋅5562 ≡ 170⋅170=28900 ≡ 743 mod 761
8: 5568=5564+4=5564⋅5564 ≡ 743⋅743=552049 ≡ 324 mod 761
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 386249 mod 887.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 249 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 249 an und zerlegen 249 in eine Summer von 2er-Potenzen:
249 = 128+64+32+16+8+1
1: 3861=386
2: 3862=3861+1=3861⋅3861 ≡ 386⋅386=148996 ≡ 867 mod 887
4: 3864=3862+2=3862⋅3862 ≡ 867⋅867=751689 ≡ 400 mod 887
8: 3868=3864+4=3864⋅3864 ≡ 400⋅400=160000 ≡ 340 mod 887
16: 38616=3868+8=3868⋅3868 ≡ 340⋅340=115600 ≡ 290 mod 887
32: 38632=38616+16=38616⋅38616 ≡ 290⋅290=84100 ≡ 722 mod 887
64: 38664=38632+32=38632⋅38632 ≡ 722⋅722=521284 ≡ 615 mod 887
128: 386128=38664+64=38664⋅38664 ≡ 615⋅615=378225 ≡ 363 mod 887
386249
= 386128+64+32+16+8+1
= 386128⋅38664⋅38632⋅38616⋅3868⋅3861
≡ 363 ⋅ 615 ⋅ 722 ⋅ 290 ⋅ 340 ⋅ 386 mod 887
≡ 223245 ⋅ 722 ⋅ 290 ⋅ 340 ⋅ 386 mod 887 ≡ 608 ⋅ 722 ⋅ 290 ⋅ 340 ⋅ 386 mod 887
≡ 438976 ⋅ 290 ⋅ 340 ⋅ 386 mod 887 ≡ 798 ⋅ 290 ⋅ 340 ⋅ 386 mod 887
≡ 231420 ⋅ 340 ⋅ 386 mod 887 ≡ 800 ⋅ 340 ⋅ 386 mod 887
≡ 272000 ⋅ 386 mod 887 ≡ 578 ⋅ 386 mod 887
≡ 223108 mod 887 ≡ 471 mod 887
Es gilt also: 386249 ≡ 471 mod 887
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 46.
Also bestimme x, so dass 46 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 46
| =>83 | = 1⋅46 + 37 |
| =>46 | = 1⋅37 + 9 |
| =>37 | = 4⋅9 + 1 |
| =>9 | = 9⋅1 + 0 |
also gilt: ggt(83,46)=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= 37-4⋅9 | |||
| 9= 46-1⋅37 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅37 -4⋅(46 -1⋅ 37)
= 1⋅37 -4⋅46 +4⋅ 37) = -4⋅46 +5⋅ 37 (=1) |
| 37= 83-1⋅46 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅46 +5⋅(83 -1⋅ 46)
= -4⋅46 +5⋅83 -5⋅ 46) = 5⋅83 -9⋅ 46 (=1) |
Es gilt also: ggt(83,46)=1 = 5⋅83 -9⋅46
oder wenn man 5⋅83 auf die linke Seite bringt:
1 -5⋅83 = -9⋅46
-9⋅46 = -5⋅83 + 1 |+83⋅46
-9⋅46 + 83⋅46 = -5⋅83 + 83⋅46 + 1
(-9 + 83) ⋅ 46 = (-5 + 46) ⋅ 83 + 1
74⋅46 = 41⋅83 + 1
Es gilt also: 74⋅46 = 41⋅83 +1
Somit 74⋅46 = 1 mod 83
74 ist also das Inverse von 46 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 61 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
