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: (28006 + 695) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(28006 + 695) mod 7 ≡ (28006 mod 7 + 695 mod 7) mod 7.
28006 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 28006
= 28000
695 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 695
= 700
Somit gilt:
(28006 + 695) mod 7 ≡ (6 + 2) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (97 ⋅ 56) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(97 ⋅ 56) mod 5 ≡ (97 mod 5 ⋅ 56 mod 5) mod 5.
97 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 97 = 95 + 2 = 19 ⋅ 5 + 2 ist.
56 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 56 = 55 + 1 = 11 ⋅ 5 + 1 ist.
Somit gilt:
(97 ⋅ 56) mod 5 ≡ (2 ⋅ 1) mod 5 ≡ 2 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 724128 mod 911.
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. 724 -> x
2. mod(x²,911) -> 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: 7241=724
2: 7242=7241+1=7241⋅7241 ≡ 724⋅724=524176 ≡ 351 mod 911
4: 7244=7242+2=7242⋅7242 ≡ 351⋅351=123201 ≡ 216 mod 911
8: 7248=7244+4=7244⋅7244 ≡ 216⋅216=46656 ≡ 195 mod 911
16: 72416=7248+8=7248⋅7248 ≡ 195⋅195=38025 ≡ 674 mod 911
32: 72432=72416+16=72416⋅72416 ≡ 674⋅674=454276 ≡ 598 mod 911
64: 72464=72432+32=72432⋅72432 ≡ 598⋅598=357604 ≡ 492 mod 911
128: 724128=72464+64=72464⋅72464 ≡ 492⋅492=242064 ≡ 649 mod 911
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 25466 mod 499.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 66 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 66 an und zerlegen 66 in eine Summer von 2er-Potenzen:
66 = 64+2
1: 2541=254
2: 2542=2541+1=2541⋅2541 ≡ 254⋅254=64516 ≡ 145 mod 499
4: 2544=2542+2=2542⋅2542 ≡ 145⋅145=21025 ≡ 67 mod 499
8: 2548=2544+4=2544⋅2544 ≡ 67⋅67=4489 ≡ 497 mod 499
16: 25416=2548+8=2548⋅2548 ≡ 497⋅497=247009 ≡ 4 mod 499
32: 25432=25416+16=25416⋅25416 ≡ 4⋅4=16 ≡ 16 mod 499
64: 25464=25432+32=25432⋅25432 ≡ 16⋅16=256 ≡ 256 mod 499
25466
= 25464+2
= 25464⋅2542
≡ 256 ⋅ 145 mod 499
≡ 37120 mod 499 ≡ 194 mod 499
Es gilt also: 25466 ≡ 194 mod 499
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 48.
Also bestimme x, so dass 48 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 48
| =>71 | = 1⋅48 + 23 |
| =>48 | = 2⋅23 + 2 |
| =>23 | = 11⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(71,48)=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= 23-11⋅2 | |||
| 2= 48-2⋅23 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅23 -11⋅(48 -2⋅ 23)
= 1⋅23 -11⋅48 +22⋅ 23) = -11⋅48 +23⋅ 23 (=1) |
| 23= 71-1⋅48 | eingesetzt in die Zeile drüber: | 1 |
= -11⋅48 +23⋅(71 -1⋅ 48)
= -11⋅48 +23⋅71 -23⋅ 48) = 23⋅71 -34⋅ 48 (=1) |
Es gilt also: ggt(71,48)=1 = 23⋅71 -34⋅48
oder wenn man 23⋅71 auf die linke Seite bringt:
1 -23⋅71 = -34⋅48
-34⋅48 = -23⋅71 + 1 |+71⋅48
-34⋅48 + 71⋅48 = -23⋅71 + 71⋅48 + 1
(-34 + 71) ⋅ 48 = (-23 + 48) ⋅ 71 + 1
37⋅48 = 25⋅71 + 1
Es gilt also: 37⋅48 = 25⋅71 +1
Somit 37⋅48 = 1 mod 71
37 ist also das Inverse von 48 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 31 und q = 101. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.