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: (901 - 182) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(901 - 182) mod 9 ≡ (901 mod 9 - 182 mod 9) mod 9.
901 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 901
= 900
182 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 182
= 180
Somit gilt:
(901 - 182) mod 9 ≡ (1 - 2) mod 9 ≡ -1 mod 9 ≡ 8 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (59 ⋅ 75) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(59 ⋅ 75) mod 5 ≡ (59 mod 5 ⋅ 75 mod 5) mod 5.
59 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 59 = 55 + 4 = 11 ⋅ 5 + 4 ist.
75 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 75 = 75 + 0 = 15 ⋅ 5 + 0 ist.
Somit gilt:
(59 ⋅ 75) mod 5 ≡ (4 ⋅ 0) mod 5 ≡ 0 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 40032 mod 599.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 400 -> x
2. mod(x²,599) -> 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: 4001=400
2: 4002=4001+1=4001⋅4001 ≡ 400⋅400=160000 ≡ 67 mod 599
4: 4004=4002+2=4002⋅4002 ≡ 67⋅67=4489 ≡ 296 mod 599
8: 4008=4004+4=4004⋅4004 ≡ 296⋅296=87616 ≡ 162 mod 599
16: 40016=4008+8=4008⋅4008 ≡ 162⋅162=26244 ≡ 487 mod 599
32: 40032=40016+16=40016⋅40016 ≡ 487⋅487=237169 ≡ 564 mod 599
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 451125 mod 811.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 125 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 125 an und zerlegen 125 in eine Summer von 2er-Potenzen:
125 = 64+32+16+8+4+1
1: 4511=451
2: 4512=4511+1=4511⋅4511 ≡ 451⋅451=203401 ≡ 651 mod 811
4: 4514=4512+2=4512⋅4512 ≡ 651⋅651=423801 ≡ 459 mod 811
8: 4518=4514+4=4514⋅4514 ≡ 459⋅459=210681 ≡ 632 mod 811
16: 45116=4518+8=4518⋅4518 ≡ 632⋅632=399424 ≡ 412 mod 811
32: 45132=45116+16=45116⋅45116 ≡ 412⋅412=169744 ≡ 245 mod 811
64: 45164=45132+32=45132⋅45132 ≡ 245⋅245=60025 ≡ 11 mod 811
451125
= 45164+32+16+8+4+1
= 45164⋅45132⋅45116⋅4518⋅4514⋅4511
≡ 11 ⋅ 245 ⋅ 412 ⋅ 632 ⋅ 459 ⋅ 451 mod 811
≡ 2695 ⋅ 412 ⋅ 632 ⋅ 459 ⋅ 451 mod 811 ≡ 262 ⋅ 412 ⋅ 632 ⋅ 459 ⋅ 451 mod 811
≡ 107944 ⋅ 632 ⋅ 459 ⋅ 451 mod 811 ≡ 81 ⋅ 632 ⋅ 459 ⋅ 451 mod 811
≡ 51192 ⋅ 459 ⋅ 451 mod 811 ≡ 99 ⋅ 459 ⋅ 451 mod 811
≡ 45441 ⋅ 451 mod 811 ≡ 25 ⋅ 451 mod 811
≡ 11275 mod 811 ≡ 732 mod 811
Es gilt also: 451125 ≡ 732 mod 811
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 53.
Also bestimme x, so dass 53 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 53
| =>71 | = 1⋅53 + 18 |
| =>53 | = 2⋅18 + 17 |
| =>18 | = 1⋅17 + 1 |
| =>17 | = 17⋅1 + 0 |
also gilt: ggt(71,53)=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= 18-1⋅17 | |||
| 17= 53-2⋅18 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅18 -1⋅(53 -2⋅ 18)
= 1⋅18 -1⋅53 +2⋅ 18) = -1⋅53 +3⋅ 18 (=1) |
| 18= 71-1⋅53 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅53 +3⋅(71 -1⋅ 53)
= -1⋅53 +3⋅71 -3⋅ 53) = 3⋅71 -4⋅ 53 (=1) |
Es gilt also: ggt(71,53)=1 = 3⋅71 -4⋅53
oder wenn man 3⋅71 auf die linke Seite bringt:
1 -3⋅71 = -4⋅53
-4⋅53 = -3⋅71 + 1 |+71⋅53
-4⋅53 + 71⋅53 = -3⋅71 + 71⋅53 + 1
(-4 + 71) ⋅ 53 = (-3 + 53) ⋅ 71 + 1
67⋅53 = 50⋅71 + 1
Es gilt also: 67⋅53 = 50⋅71 +1
Somit 67⋅53 = 1 mod 71
67 ist also das Inverse von 53 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 41. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
