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: (124 - 119) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(124 - 119) mod 4 ≡ (124 mod 4 - 119 mod 4) mod 4.
124 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 124
= 120
119 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 119
= 120
Somit gilt:
(124 - 119) mod 4 ≡ (0 - 3) mod 4 ≡ -3 mod 4 ≡ 1 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (82 ⋅ 98) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(82 ⋅ 98) mod 7 ≡ (82 mod 7 ⋅ 98 mod 7) mod 7.
82 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 82 = 77 + 5 = 11 ⋅ 7 + 5 ist.
98 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 98 = 98 + 0 = 14 ⋅ 7 + 0 ist.
Somit gilt:
(82 ⋅ 98) mod 7 ≡ (5 ⋅ 0) mod 7 ≡ 0 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 228128 mod 619.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 228 -> x
2. mod(x²,619) -> 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: 2281=228
2: 2282=2281+1=2281⋅2281 ≡ 228⋅228=51984 ≡ 607 mod 619
4: 2284=2282+2=2282⋅2282 ≡ 607⋅607=368449 ≡ 144 mod 619
8: 2288=2284+4=2284⋅2284 ≡ 144⋅144=20736 ≡ 309 mod 619
16: 22816=2288+8=2288⋅2288 ≡ 309⋅309=95481 ≡ 155 mod 619
32: 22832=22816+16=22816⋅22816 ≡ 155⋅155=24025 ≡ 503 mod 619
64: 22864=22832+32=22832⋅22832 ≡ 503⋅503=253009 ≡ 457 mod 619
128: 228128=22864+64=22864⋅22864 ≡ 457⋅457=208849 ≡ 246 mod 619
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 25181 mod 827.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 81 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 81 an und zerlegen 81 in eine Summer von 2er-Potenzen:
81 = 64+16+1
1: 2511=251
2: 2512=2511+1=2511⋅2511 ≡ 251⋅251=63001 ≡ 149 mod 827
4: 2514=2512+2=2512⋅2512 ≡ 149⋅149=22201 ≡ 699 mod 827
8: 2518=2514+4=2514⋅2514 ≡ 699⋅699=488601 ≡ 671 mod 827
16: 25116=2518+8=2518⋅2518 ≡ 671⋅671=450241 ≡ 353 mod 827
32: 25132=25116+16=25116⋅25116 ≡ 353⋅353=124609 ≡ 559 mod 827
64: 25164=25132+32=25132⋅25132 ≡ 559⋅559=312481 ≡ 702 mod 827
25181
= 25164+16+1
= 25164⋅25116⋅2511
≡ 702 ⋅ 353 ⋅ 251 mod 827
≡ 247806 ⋅ 251 mod 827 ≡ 533 ⋅ 251 mod 827
≡ 133783 mod 827 ≡ 636 mod 827
Es gilt also: 25181 ≡ 636 mod 827
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 54.
Also bestimme x, so dass 54 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 54
| =>67 | = 1⋅54 + 13 |
| =>54 | = 4⋅13 + 2 |
| =>13 | = 6⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(67,54)=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-6⋅2 | |||
| 2= 54-4⋅13 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅13 -6⋅(54 -4⋅ 13)
= 1⋅13 -6⋅54 +24⋅ 13) = -6⋅54 +25⋅ 13 (=1) |
| 13= 67-1⋅54 | eingesetzt in die Zeile drüber: | 1 |
= -6⋅54 +25⋅(67 -1⋅ 54)
= -6⋅54 +25⋅67 -25⋅ 54) = 25⋅67 -31⋅ 54 (=1) |
Es gilt also: ggt(67,54)=1 = 25⋅67 -31⋅54
oder wenn man 25⋅67 auf die linke Seite bringt:
1 -25⋅67 = -31⋅54
-31⋅54 = -25⋅67 + 1 |+67⋅54
-31⋅54 + 67⋅54 = -25⋅67 + 67⋅54 + 1
(-31 + 67) ⋅ 54 = (-25 + 54) ⋅ 67 + 1
36⋅54 = 29⋅67 + 1
Es gilt also: 36⋅54 = 29⋅67 +1
Somit 36⋅54 = 1 mod 67
36 ist also das Inverse von 54 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 61 und q = 67. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
