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: (4004 - 11996) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(4004 - 11996) mod 4 ≡ (4004 mod 4 - 11996 mod 4) mod 4.
4004 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 4004
= 4000
11996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 11996
= 11000
Somit gilt:
(4004 - 11996) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (95 ⋅ 21) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(95 ⋅ 21) mod 5 ≡ (95 mod 5 ⋅ 21 mod 5) mod 5.
95 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 95 = 95 + 0 = 19 ⋅ 5 + 0 ist.
21 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 21 = 20 + 1 = 4 ⋅ 5 + 1 ist.
Somit gilt:
(95 ⋅ 21) mod 5 ≡ (0 ⋅ 1) mod 5 ≡ 0 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 7968 mod 877.
Die 8 im Exponent ist ja ein reine 2er-Potenz (23).
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. 796 -> x
2. mod(x²,877) -> 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: 7961=796
2: 7962=7961+1=7961⋅7961 ≡ 796⋅796=633616 ≡ 422 mod 877
4: 7964=7962+2=7962⋅7962 ≡ 422⋅422=178084 ≡ 53 mod 877
8: 7968=7964+4=7964⋅7964 ≡ 53⋅53=2809 ≡ 178 mod 877
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 72788 mod 769.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 88 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 88 an und zerlegen 88 in eine Summer von 2er-Potenzen:
88 = 64+16+8
1: 7271=727
2: 7272=7271+1=7271⋅7271 ≡ 727⋅727=528529 ≡ 226 mod 769
4: 7274=7272+2=7272⋅7272 ≡ 226⋅226=51076 ≡ 322 mod 769
8: 7278=7274+4=7274⋅7274 ≡ 322⋅322=103684 ≡ 638 mod 769
16: 72716=7278+8=7278⋅7278 ≡ 638⋅638=407044 ≡ 243 mod 769
32: 72732=72716+16=72716⋅72716 ≡ 243⋅243=59049 ≡ 605 mod 769
64: 72764=72732+32=72732⋅72732 ≡ 605⋅605=366025 ≡ 750 mod 769
72788
= 72764+16+8
= 72764⋅72716⋅7278
≡ 750 ⋅ 243 ⋅ 638 mod 769
≡ 182250 ⋅ 638 mod 769 ≡ 766 ⋅ 638 mod 769
≡ 488708 mod 769 ≡ 393 mod 769
Es gilt also: 72788 ≡ 393 mod 769
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 73.
Also bestimme x, so dass 73 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 73
| =>83 | = 1⋅73 + 10 |
| =>73 | = 7⋅10 + 3 |
| =>10 | = 3⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(83,73)=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-3⋅3 | |||
| 3= 73-7⋅10 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅10 -3⋅(73 -7⋅ 10)
= 1⋅10 -3⋅73 +21⋅ 10) = -3⋅73 +22⋅ 10 (=1) |
| 10= 83-1⋅73 | eingesetzt in die Zeile drüber: | 1 |
= -3⋅73 +22⋅(83 -1⋅ 73)
= -3⋅73 +22⋅83 -22⋅ 73) = 22⋅83 -25⋅ 73 (=1) |
Es gilt also: ggt(83,73)=1 = 22⋅83 -25⋅73
oder wenn man 22⋅83 auf die linke Seite bringt:
1 -22⋅83 = -25⋅73
-25⋅73 = -22⋅83 + 1 |+83⋅73
-25⋅73 + 83⋅73 = -22⋅83 + 83⋅73 + 1
(-25 + 83) ⋅ 73 = (-22 + 73) ⋅ 83 + 1
58⋅73 = 51⋅83 + 1
Es gilt also: 58⋅73 = 51⋅83 +1
Somit 58⋅73 = 1 mod 83
58 ist also das Inverse von 73 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 97. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.