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: (3000 - 600) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(3000 - 600) mod 3 ≡ (3000 mod 3 - 600 mod 3) mod 3.
3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000
= 3000
600 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 600
= 600
Somit gilt:
(3000 - 600) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (68 ⋅ 85) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(68 ⋅ 85) mod 7 ≡ (68 mod 7 ⋅ 85 mod 7) mod 7.
68 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 68 = 63 + 5 = 9 ⋅ 7 + 5 ist.
85 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 12 ⋅ 7 + 1 ist.
Somit gilt:
(68 ⋅ 85) mod 7 ≡ (5 ⋅ 1) mod 7 ≡ 5 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 36364 mod 397.
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. 363 -> x
2. mod(x²,397) -> 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: 3631=363
2: 3632=3631+1=3631⋅3631 ≡ 363⋅363=131769 ≡ 362 mod 397
4: 3634=3632+2=3632⋅3632 ≡ 362⋅362=131044 ≡ 34 mod 397
8: 3638=3634+4=3634⋅3634 ≡ 34⋅34=1156 ≡ 362 mod 397
16: 36316=3638+8=3638⋅3638 ≡ 362⋅362=131044 ≡ 34 mod 397
32: 36332=36316+16=36316⋅36316 ≡ 34⋅34=1156 ≡ 362 mod 397
64: 36364=36332+32=36332⋅36332 ≡ 362⋅362=131044 ≡ 34 mod 397
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 487235 mod 619.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 235 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 235 an und zerlegen 235 in eine Summer von 2er-Potenzen:
235 = 128+64+32+8+2+1
1: 4871=487
2: 4872=4871+1=4871⋅4871 ≡ 487⋅487=237169 ≡ 92 mod 619
4: 4874=4872+2=4872⋅4872 ≡ 92⋅92=8464 ≡ 417 mod 619
8: 4878=4874+4=4874⋅4874 ≡ 417⋅417=173889 ≡ 569 mod 619
16: 48716=4878+8=4878⋅4878 ≡ 569⋅569=323761 ≡ 24 mod 619
32: 48732=48716+16=48716⋅48716 ≡ 24⋅24=576 ≡ 576 mod 619
64: 48764=48732+32=48732⋅48732 ≡ 576⋅576=331776 ≡ 611 mod 619
128: 487128=48764+64=48764⋅48764 ≡ 611⋅611=373321 ≡ 64 mod 619
487235
= 487128+64+32+8+2+1
= 487128⋅48764⋅48732⋅4878⋅4872⋅4871
≡ 64 ⋅ 611 ⋅ 576 ⋅ 569 ⋅ 92 ⋅ 487 mod 619
≡ 39104 ⋅ 576 ⋅ 569 ⋅ 92 ⋅ 487 mod 619 ≡ 107 ⋅ 576 ⋅ 569 ⋅ 92 ⋅ 487 mod 619
≡ 61632 ⋅ 569 ⋅ 92 ⋅ 487 mod 619 ≡ 351 ⋅ 569 ⋅ 92 ⋅ 487 mod 619
≡ 199719 ⋅ 92 ⋅ 487 mod 619 ≡ 401 ⋅ 92 ⋅ 487 mod 619
≡ 36892 ⋅ 487 mod 619 ≡ 371 ⋅ 487 mod 619
≡ 180677 mod 619 ≡ 548 mod 619
Es gilt also: 487235 ≡ 548 mod 619
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-59-Inverse zur Zahl 46.
Also bestimme x, so dass 46 ⋅ x ≡ 1 mod 59 gilt:
Berechnung des größten gemeinsamen Teilers von 59 und 46
| =>59 | = 1⋅46 + 13 |
| =>46 | = 3⋅13 + 7 |
| =>13 | = 1⋅7 + 6 |
| =>7 | = 1⋅6 + 1 |
| =>6 | = 6⋅1 + 0 |
also gilt: ggt(59,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= 7-1⋅6 | |||
| 6= 13-1⋅7 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅7 -1⋅(13 -1⋅ 7)
= 1⋅7 -1⋅13 +1⋅ 7) = -1⋅13 +2⋅ 7 (=1) |
| 7= 46-3⋅13 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅13 +2⋅(46 -3⋅ 13)
= -1⋅13 +2⋅46 -6⋅ 13) = 2⋅46 -7⋅ 13 (=1) |
| 13= 59-1⋅46 | eingesetzt in die Zeile drüber: | 1 |
= 2⋅46 -7⋅(59 -1⋅ 46)
= 2⋅46 -7⋅59 +7⋅ 46) = -7⋅59 +9⋅ 46 (=1) |
Es gilt also: ggt(59,46)=1 = -7⋅59 +9⋅46
oder wenn man -7⋅59 auf die linke Seite bringt:
1 +7⋅59 = +9⋅46
Es gilt also: 9⋅46 = 7⋅59 +1
Somit 9⋅46 = 1 mod 59
9 ist also das Inverse von 46 mod 59
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 37 und q = 47. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
