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: (347 + 3503) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(347 + 3503) mod 7 ≡ (347 mod 7 + 3503 mod 7) mod 7.
347 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 347
= 350
3503 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 3503
= 3500
Somit gilt:
(347 + 3503) mod 7 ≡ (4 + 3) mod 7 ≡ 7 mod 7 ≡ 0 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (31 ⋅ 23) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(31 ⋅ 23) mod 6 ≡ (31 mod 6 ⋅ 23 mod 6) mod 6.
31 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 31 = 30 + 1 = 5 ⋅ 6 + 1 ist.
23 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 23 = 18 + 5 = 3 ⋅ 6 + 5 ist.
Somit gilt:
(31 ⋅ 23) mod 6 ≡ (1 ⋅ 5) mod 6 ≡ 5 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 60816 mod 881.
Die 16 im Exponent ist ja ein reine 2er-Potenz (24).
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. 608 -> x
2. mod(x²,881) -> 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: 6081=608
2: 6082=6081+1=6081⋅6081 ≡ 608⋅608=369664 ≡ 525 mod 881
4: 6084=6082+2=6082⋅6082 ≡ 525⋅525=275625 ≡ 753 mod 881
8: 6088=6084+4=6084⋅6084 ≡ 753⋅753=567009 ≡ 526 mod 881
16: 60816=6088+8=6088⋅6088 ≡ 526⋅526=276676 ≡ 42 mod 881
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 188102 mod 463.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 102 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 102 an und zerlegen 102 in eine Summer von 2er-Potenzen:
102 = 64+32+4+2
1: 1881=188
2: 1882=1881+1=1881⋅1881 ≡ 188⋅188=35344 ≡ 156 mod 463
4: 1884=1882+2=1882⋅1882 ≡ 156⋅156=24336 ≡ 260 mod 463
8: 1888=1884+4=1884⋅1884 ≡ 260⋅260=67600 ≡ 2 mod 463
16: 18816=1888+8=1888⋅1888 ≡ 2⋅2=4 ≡ 4 mod 463
32: 18832=18816+16=18816⋅18816 ≡ 4⋅4=16 ≡ 16 mod 463
64: 18864=18832+32=18832⋅18832 ≡ 16⋅16=256 ≡ 256 mod 463
188102
= 18864+32+4+2
= 18864⋅18832⋅1884⋅1882
≡ 256 ⋅ 16 ⋅ 260 ⋅ 156 mod 463
≡ 4096 ⋅ 260 ⋅ 156 mod 463 ≡ 392 ⋅ 260 ⋅ 156 mod 463
≡ 101920 ⋅ 156 mod 463 ≡ 60 ⋅ 156 mod 463
≡ 9360 mod 463 ≡ 100 mod 463
Es gilt also: 188102 ≡ 100 mod 463
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 25.
Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 25
| =>67 | = 2⋅25 + 17 |
| =>25 | = 1⋅17 + 8 |
| =>17 | = 2⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(67,25)=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= 17-2⋅8 | |||
| 8= 25-1⋅17 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅17 -2⋅(25 -1⋅ 17)
= 1⋅17 -2⋅25 +2⋅ 17) = -2⋅25 +3⋅ 17 (=1) |
| 17= 67-2⋅25 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅25 +3⋅(67 -2⋅ 25)
= -2⋅25 +3⋅67 -6⋅ 25) = 3⋅67 -8⋅ 25 (=1) |
Es gilt also: ggt(67,25)=1 = 3⋅67 -8⋅25
oder wenn man 3⋅67 auf die linke Seite bringt:
1 -3⋅67 = -8⋅25
-8⋅25 = -3⋅67 + 1 |+67⋅25
-8⋅25 + 67⋅25 = -3⋅67 + 67⋅25 + 1
(-8 + 67) ⋅ 25 = (-3 + 25) ⋅ 67 + 1
59⋅25 = 22⋅67 + 1
Es gilt also: 59⋅25 = 22⋅67 +1
Somit 59⋅25 = 1 mod 67
59 ist also das Inverse von 25 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 47 und q = 71. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
