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: (348 - 211) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(348 - 211) mod 7 ≡ (348 mod 7 - 211 mod 7) mod 7.
348 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 348
= 350
211 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 211
= 210
Somit gilt:
(348 - 211) mod 7 ≡ (5 - 1) mod 7 ≡ 4 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (15 ⋅ 98) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(15 ⋅ 98) mod 9 ≡ (15 mod 9 ⋅ 98 mod 9) mod 9.
15 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 15 = 9 + 6 = 1 ⋅ 9 + 6 ist.
98 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 98 = 90 + 8 = 10 ⋅ 9 + 8 ist.
Somit gilt:
(15 ⋅ 98) mod 9 ≡ (6 ⋅ 8) mod 9 ≡ 48 mod 9 ≡ 3 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 45864 mod 859.
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. 458 -> x
2. mod(x²,859) -> 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: 4581=458
2: 4582=4581+1=4581⋅4581 ≡ 458⋅458=209764 ≡ 168 mod 859
4: 4584=4582+2=4582⋅4582 ≡ 168⋅168=28224 ≡ 736 mod 859
8: 4588=4584+4=4584⋅4584 ≡ 736⋅736=541696 ≡ 526 mod 859
16: 45816=4588+8=4588⋅4588 ≡ 526⋅526=276676 ≡ 78 mod 859
32: 45832=45816+16=45816⋅45816 ≡ 78⋅78=6084 ≡ 71 mod 859
64: 45864=45832+32=45832⋅45832 ≡ 71⋅71=5041 ≡ 746 mod 859
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 316168 mod 877.
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: 3161=316
2: 3162=3161+1=3161⋅3161 ≡ 316⋅316=99856 ≡ 755 mod 877
4: 3164=3162+2=3162⋅3162 ≡ 755⋅755=570025 ≡ 852 mod 877
8: 3168=3164+4=3164⋅3164 ≡ 852⋅852=725904 ≡ 625 mod 877
16: 31616=3168+8=3168⋅3168 ≡ 625⋅625=390625 ≡ 360 mod 877
32: 31632=31616+16=31616⋅31616 ≡ 360⋅360=129600 ≡ 681 mod 877
64: 31664=31632+32=31632⋅31632 ≡ 681⋅681=463761 ≡ 705 mod 877
128: 316128=31664+64=31664⋅31664 ≡ 705⋅705=497025 ≡ 643 mod 877
316168
= 316128+32+8
= 316128⋅31632⋅3168
≡ 643 ⋅ 681 ⋅ 625 mod 877
≡ 437883 ⋅ 625 mod 877 ≡ 260 ⋅ 625 mod 877
≡ 162500 mod 877 ≡ 255 mod 877
Es gilt also: 316168 ≡ 255 mod 877
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 43.
Also bestimme x, so dass 43 ⋅ x ≡ 1 mod 73 gilt:
Berechnung des größten gemeinsamen Teilers von 73 und 43
| =>73 | = 1⋅43 + 30 |
| =>43 | = 1⋅30 + 13 |
| =>30 | = 2⋅13 + 4 |
| =>13 | = 3⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(73,43)=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= 13-3⋅4 | |||
| 4= 30-2⋅13 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅13 -3⋅(30 -2⋅ 13)
= 1⋅13 -3⋅30 +6⋅ 13) = -3⋅30 +7⋅ 13 (=1) |
| 13= 43-1⋅30 | eingesetzt in die Zeile drüber: | 1 |
= -3⋅30 +7⋅(43 -1⋅ 30)
= -3⋅30 +7⋅43 -7⋅ 30) = 7⋅43 -10⋅ 30 (=1) |
| 30= 73-1⋅43 | eingesetzt in die Zeile drüber: | 1 |
= 7⋅43 -10⋅(73 -1⋅ 43)
= 7⋅43 -10⋅73 +10⋅ 43) = -10⋅73 +17⋅ 43 (=1) |
Es gilt also: ggt(73,43)=1 = -10⋅73 +17⋅43
oder wenn man -10⋅73 auf die linke Seite bringt:
1 +10⋅73 = +17⋅43
Es gilt also: 17⋅43 = 10⋅73 +1
Somit 17⋅43 = 1 mod 73
17 ist also das Inverse von 43 mod 73
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 73. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
