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: (282 + 209) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(282 + 209) mod 7 ≡ (282 mod 7 + 209 mod 7) mod 7.
282 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 282
= 280
209 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 209
= 210
Somit gilt:
(282 + 209) mod 7 ≡ (2 + 6) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (15 ⋅ 74) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(15 ⋅ 74) mod 4 ≡ (15 mod 4 ⋅ 74 mod 4) mod 4.
15 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 15 = 12 + 3 = 3 ⋅ 4 + 3 ist.
74 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 18 ⋅ 4 + 2 ist.
Somit gilt:
(15 ⋅ 74) mod 4 ≡ (3 ⋅ 2) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 14864 mod 241.
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. 148 -> x
2. mod(x²,241) -> 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: 1481=148
2: 1482=1481+1=1481⋅1481 ≡ 148⋅148=21904 ≡ 214 mod 241
4: 1484=1482+2=1482⋅1482 ≡ 214⋅214=45796 ≡ 6 mod 241
8: 1488=1484+4=1484⋅1484 ≡ 6⋅6=36 ≡ 36 mod 241
16: 14816=1488+8=1488⋅1488 ≡ 36⋅36=1296 ≡ 91 mod 241
32: 14832=14816+16=14816⋅14816 ≡ 91⋅91=8281 ≡ 87 mod 241
64: 14864=14832+32=14832⋅14832 ≡ 87⋅87=7569 ≡ 98 mod 241
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 673252 mod 773.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 252 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 252 an und zerlegen 252 in eine Summer von 2er-Potenzen:
252 = 128+64+32+16+8+4
1: 6731=673
2: 6732=6731+1=6731⋅6731 ≡ 673⋅673=452929 ≡ 724 mod 773
4: 6734=6732+2=6732⋅6732 ≡ 724⋅724=524176 ≡ 82 mod 773
8: 6738=6734+4=6734⋅6734 ≡ 82⋅82=6724 ≡ 540 mod 773
16: 67316=6738+8=6738⋅6738 ≡ 540⋅540=291600 ≡ 179 mod 773
32: 67332=67316+16=67316⋅67316 ≡ 179⋅179=32041 ≡ 348 mod 773
64: 67364=67332+32=67332⋅67332 ≡ 348⋅348=121104 ≡ 516 mod 773
128: 673128=67364+64=67364⋅67364 ≡ 516⋅516=266256 ≡ 344 mod 773
673252
= 673128+64+32+16+8+4
= 673128⋅67364⋅67332⋅67316⋅6738⋅6734
≡ 344 ⋅ 516 ⋅ 348 ⋅ 179 ⋅ 540 ⋅ 82 mod 773
≡ 177504 ⋅ 348 ⋅ 179 ⋅ 540 ⋅ 82 mod 773 ≡ 487 ⋅ 348 ⋅ 179 ⋅ 540 ⋅ 82 mod 773
≡ 169476 ⋅ 179 ⋅ 540 ⋅ 82 mod 773 ≡ 189 ⋅ 179 ⋅ 540 ⋅ 82 mod 773
≡ 33831 ⋅ 540 ⋅ 82 mod 773 ≡ 592 ⋅ 540 ⋅ 82 mod 773
≡ 319680 ⋅ 82 mod 773 ≡ 431 ⋅ 82 mod 773
≡ 35342 mod 773 ≡ 557 mod 773
Es gilt also: 673252 ≡ 557 mod 773
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-79-Inverse zur Zahl 69.
Also bestimme x, so dass 69 ⋅ x ≡ 1 mod 79 gilt:
Berechnung des größten gemeinsamen Teilers von 79 und 69
| =>79 | = 1⋅69 + 10 |
| =>69 | = 6⋅10 + 9 |
| =>10 | = 1⋅9 + 1 |
| =>9 | = 9⋅1 + 0 |
also gilt: ggt(79,69)=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= 10-1⋅9 | |||
| 9= 69-6⋅10 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅10 -1⋅(69 -6⋅ 10)
= 1⋅10 -1⋅69 +6⋅ 10) = -1⋅69 +7⋅ 10 (=1) |
| 10= 79-1⋅69 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅69 +7⋅(79 -1⋅ 69)
= -1⋅69 +7⋅79 -7⋅ 69) = 7⋅79 -8⋅ 69 (=1) |
Es gilt also: ggt(79,69)=1 = 7⋅79 -8⋅69
oder wenn man 7⋅79 auf die linke Seite bringt:
1 -7⋅79 = -8⋅69
-8⋅69 = -7⋅79 + 1 |+79⋅69
-8⋅69 + 79⋅69 = -7⋅79 + 79⋅69 + 1
(-8 + 79) ⋅ 69 = (-7 + 69) ⋅ 79 + 1
71⋅69 = 62⋅79 + 1
Es gilt also: 71⋅69 = 62⋅79 +1
Somit 71⋅69 = 1 mod 79
71 ist also das Inverse von 69 mod 79
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 47 und q = 79. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
