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: (313 - 239) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(313 - 239) mod 8 ≡ (313 mod 8 - 239 mod 8) mod 8.
313 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 313
= 320
239 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 239
= 240
Somit gilt:
(313 - 239) mod 8 ≡ (1 - 7) mod 8 ≡ -6 mod 8 ≡ 2 mod 8.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (57 ⋅ 81) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(57 ⋅ 81) mod 4 ≡ (57 mod 4 ⋅ 81 mod 4) mod 4.
57 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 57 = 56 + 1 = 14 ⋅ 4 + 1 ist.
81 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 20 ⋅ 4 + 1 ist.
Somit gilt:
(57 ⋅ 81) mod 4 ≡ (1 ⋅ 1) mod 4 ≡ 1 mod 4.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 296128 mod 547.
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. 296 -> x
2. mod(x²,547) -> 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: 2961=296
2: 2962=2961+1=2961⋅2961 ≡ 296⋅296=87616 ≡ 96 mod 547
4: 2964=2962+2=2962⋅2962 ≡ 96⋅96=9216 ≡ 464 mod 547
8: 2968=2964+4=2964⋅2964 ≡ 464⋅464=215296 ≡ 325 mod 547
16: 29616=2968+8=2968⋅2968 ≡ 325⋅325=105625 ≡ 54 mod 547
32: 29632=29616+16=29616⋅29616 ≡ 54⋅54=2916 ≡ 181 mod 547
64: 29664=29632+32=29632⋅29632 ≡ 181⋅181=32761 ≡ 488 mod 547
128: 296128=29664+64=29664⋅29664 ≡ 488⋅488=238144 ≡ 199 mod 547
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 31396 mod 971.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 96 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 96 an und zerlegen 96 in eine Summer von 2er-Potenzen:
96 = 64+32
1: 3131=313
2: 3132=3131+1=3131⋅3131 ≡ 313⋅313=97969 ≡ 869 mod 971
4: 3134=3132+2=3132⋅3132 ≡ 869⋅869=755161 ≡ 694 mod 971
8: 3138=3134+4=3134⋅3134 ≡ 694⋅694=481636 ≡ 20 mod 971
16: 31316=3138+8=3138⋅3138 ≡ 20⋅20=400 ≡ 400 mod 971
32: 31332=31316+16=31316⋅31316 ≡ 400⋅400=160000 ≡ 756 mod 971
64: 31364=31332+32=31332⋅31332 ≡ 756⋅756=571536 ≡ 588 mod 971
31396
= 31364+32
= 31364⋅31332
≡ 588 ⋅ 756 mod 971
≡ 444528 mod 971 ≡ 781 mod 971
Es gilt also: 31396 ≡ 781 mod 971
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 67.
Also bestimme x, so dass 67 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 67
| =>101 | = 1⋅67 + 34 |
| =>67 | = 1⋅34 + 33 |
| =>34 | = 1⋅33 + 1 |
| =>33 | = 33⋅1 + 0 |
also gilt: ggt(101,67)=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= 34-1⋅33 | |||
| 33= 67-1⋅34 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅34 -1⋅(67 -1⋅ 34)
= 1⋅34 -1⋅67 +1⋅ 34) = -1⋅67 +2⋅ 34 (=1) |
| 34= 101-1⋅67 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅67 +2⋅(101 -1⋅ 67)
= -1⋅67 +2⋅101 -2⋅ 67) = 2⋅101 -3⋅ 67 (=1) |
Es gilt also: ggt(101,67)=1 = 2⋅101 -3⋅67
oder wenn man 2⋅101 auf die linke Seite bringt:
1 -2⋅101 = -3⋅67
-3⋅67 = -2⋅101 + 1 |+101⋅67
-3⋅67 + 101⋅67 = -2⋅101 + 101⋅67 + 1
(-3 + 101) ⋅ 67 = (-2 + 67) ⋅ 101 + 1
98⋅67 = 65⋅101 + 1
Es gilt also: 98⋅67 = 65⋅101 +1
Somit 98⋅67 = 1 mod 101
98 ist also das Inverse von 67 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 59 und q = 79. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.