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: (4998 - 1005) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(4998 - 1005) mod 5 ≡ (4998 mod 5 - 1005 mod 5) mod 5.
4998 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 4998
= 4000
1005 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1005
= 1000
Somit gilt:
(4998 - 1005) mod 5 ≡ (3 - 0) mod 5 ≡ 3 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (49 ⋅ 97) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(49 ⋅ 97) mod 5 ≡ (49 mod 5 ⋅ 97 mod 5) mod 5.
49 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 49 = 45 + 4 = 9 ⋅ 5 + 4 ist.
97 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 97 = 95 + 2 = 19 ⋅ 5 + 2 ist.
Somit gilt:
(49 ⋅ 97) mod 5 ≡ (4 ⋅ 2) mod 5 ≡ 8 mod 5 ≡ 3 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 45964 mod 613.
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. 459 -> x
2. mod(x²,613) -> 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: 4591=459
2: 4592=4591+1=4591⋅4591 ≡ 459⋅459=210681 ≡ 422 mod 613
4: 4594=4592+2=4592⋅4592 ≡ 422⋅422=178084 ≡ 314 mod 613
8: 4598=4594+4=4594⋅4594 ≡ 314⋅314=98596 ≡ 516 mod 613
16: 45916=4598+8=4598⋅4598 ≡ 516⋅516=266256 ≡ 214 mod 613
32: 45932=45916+16=45916⋅45916 ≡ 214⋅214=45796 ≡ 434 mod 613
64: 45964=45932+32=45932⋅45932 ≡ 434⋅434=188356 ≡ 165 mod 613
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 707157 mod 827.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 157 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 157 an und zerlegen 157 in eine Summer von 2er-Potenzen:
157 = 128+16+8+4+1
1: 7071=707
2: 7072=7071+1=7071⋅7071 ≡ 707⋅707=499849 ≡ 341 mod 827
4: 7074=7072+2=7072⋅7072 ≡ 341⋅341=116281 ≡ 501 mod 827
8: 7078=7074+4=7074⋅7074 ≡ 501⋅501=251001 ≡ 420 mod 827
16: 70716=7078+8=7078⋅7078 ≡ 420⋅420=176400 ≡ 249 mod 827
32: 70732=70716+16=70716⋅70716 ≡ 249⋅249=62001 ≡ 803 mod 827
64: 70764=70732+32=70732⋅70732 ≡ 803⋅803=644809 ≡ 576 mod 827
128: 707128=70764+64=70764⋅70764 ≡ 576⋅576=331776 ≡ 149 mod 827
707157
= 707128+16+8+4+1
= 707128⋅70716⋅7078⋅7074⋅7071
≡ 149 ⋅ 249 ⋅ 420 ⋅ 501 ⋅ 707 mod 827
≡ 37101 ⋅ 420 ⋅ 501 ⋅ 707 mod 827 ≡ 713 ⋅ 420 ⋅ 501 ⋅ 707 mod 827
≡ 299460 ⋅ 501 ⋅ 707 mod 827 ≡ 86 ⋅ 501 ⋅ 707 mod 827
≡ 43086 ⋅ 707 mod 827 ≡ 82 ⋅ 707 mod 827
≡ 57974 mod 827 ≡ 84 mod 827
Es gilt also: 707157 ≡ 84 mod 827
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 52.
Also bestimme x, so dass 52 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 52
| =>83 | = 1⋅52 + 31 |
| =>52 | = 1⋅31 + 21 |
| =>31 | = 1⋅21 + 10 |
| =>21 | = 2⋅10 + 1 |
| =>10 | = 10⋅1 + 0 |
also gilt: ggt(83,52)=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= 21-2⋅10 | |||
| 10= 31-1⋅21 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅21 -2⋅(31 -1⋅ 21)
= 1⋅21 -2⋅31 +2⋅ 21) = -2⋅31 +3⋅ 21 (=1) |
| 21= 52-1⋅31 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅31 +3⋅(52 -1⋅ 31)
= -2⋅31 +3⋅52 -3⋅ 31) = 3⋅52 -5⋅ 31 (=1) |
| 31= 83-1⋅52 | eingesetzt in die Zeile drüber: | 1 |
= 3⋅52 -5⋅(83 -1⋅ 52)
= 3⋅52 -5⋅83 +5⋅ 52) = -5⋅83 +8⋅ 52 (=1) |
Es gilt also: ggt(83,52)=1 = -5⋅83 +8⋅52
oder wenn man -5⋅83 auf die linke Seite bringt:
1 +5⋅83 = +8⋅52
Es gilt also: 8⋅52 = 5⋅83 +1
Somit 8⋅52 = 1 mod 83
8 ist also das Inverse von 52 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 83. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
