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: (5997 - 88) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(5997 - 88) mod 3 ≡ (5997 mod 3 - 88 mod 3) mod 3.
5997 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 5997
= 6000
88 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 88
= 90
Somit gilt:
(5997 - 88) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (88 ⋅ 27) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(88 ⋅ 27) mod 3 ≡ (88 mod 3 ⋅ 27 mod 3) mod 3.
88 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 88 = 87 + 1 = 29 ⋅ 3 + 1 ist.
27 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 27 = 27 + 0 = 9 ⋅ 3 + 0 ist.
Somit gilt:
(88 ⋅ 27) mod 3 ≡ (1 ⋅ 0) mod 3 ≡ 0 mod 3.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 62632 mod 643.
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. 626 -> x
2. mod(x²,643) -> 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: 6261=626
2: 6262=6261+1=6261⋅6261 ≡ 626⋅626=391876 ≡ 289 mod 643
4: 6264=6262+2=6262⋅6262 ≡ 289⋅289=83521 ≡ 574 mod 643
8: 6268=6264+4=6264⋅6264 ≡ 574⋅574=329476 ≡ 260 mod 643
16: 62616=6268+8=6268⋅6268 ≡ 260⋅260=67600 ≡ 85 mod 643
32: 62632=62616+16=62616⋅62616 ≡ 85⋅85=7225 ≡ 152 mod 643
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 675101 mod 829.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 101 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 101 an und zerlegen 101 in eine Summer von 2er-Potenzen:
101 = 64+32+4+1
1: 6751=675
2: 6752=6751+1=6751⋅6751 ≡ 675⋅675=455625 ≡ 504 mod 829
4: 6754=6752+2=6752⋅6752 ≡ 504⋅504=254016 ≡ 342 mod 829
8: 6758=6754+4=6754⋅6754 ≡ 342⋅342=116964 ≡ 75 mod 829
16: 67516=6758+8=6758⋅6758 ≡ 75⋅75=5625 ≡ 651 mod 829
32: 67532=67516+16=67516⋅67516 ≡ 651⋅651=423801 ≡ 182 mod 829
64: 67564=67532+32=67532⋅67532 ≡ 182⋅182=33124 ≡ 793 mod 829
675101
= 67564+32+4+1
= 67564⋅67532⋅6754⋅6751
≡ 793 ⋅ 182 ⋅ 342 ⋅ 675 mod 829
≡ 144326 ⋅ 342 ⋅ 675 mod 829 ≡ 80 ⋅ 342 ⋅ 675 mod 829
≡ 27360 ⋅ 675 mod 829 ≡ 3 ⋅ 675 mod 829
≡ 2025 mod 829 ≡ 367 mod 829
Es gilt also: 675101 ≡ 367 mod 829
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 72.
Also bestimme x, so dass 72 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 72
| =>101 | = 1⋅72 + 29 |
| =>72 | = 2⋅29 + 14 |
| =>29 | = 2⋅14 + 1 |
| =>14 | = 14⋅1 + 0 |
also gilt: ggt(101,72)=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= 29-2⋅14 | |||
| 14= 72-2⋅29 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅29 -2⋅(72 -2⋅ 29)
= 1⋅29 -2⋅72 +4⋅ 29) = -2⋅72 +5⋅ 29 (=1) |
| 29= 101-1⋅72 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅72 +5⋅(101 -1⋅ 72)
= -2⋅72 +5⋅101 -5⋅ 72) = 5⋅101 -7⋅ 72 (=1) |
Es gilt also: ggt(101,72)=1 = 5⋅101 -7⋅72
oder wenn man 5⋅101 auf die linke Seite bringt:
1 -5⋅101 = -7⋅72
-7⋅72 = -5⋅101 + 1 |+101⋅72
-7⋅72 + 101⋅72 = -5⋅101 + 101⋅72 + 1
(-7 + 101) ⋅ 72 = (-5 + 72) ⋅ 101 + 1
94⋅72 = 67⋅101 + 1
Es gilt also: 94⋅72 = 67⋅101 +1
Somit 94⋅72 = 1 mod 101
94 ist also das Inverse von 72 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 71 und q = 53. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.