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: (2498 - 505) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2498 - 505) mod 5 ≡ (2498 mod 5 - 505 mod 5) mod 5.
2498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2498
= 2400
505 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 505
= 500
Somit gilt:
(2498 - 505) mod 5 ≡ (3 - 0) mod 5 ≡ 3 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (27 ⋅ 19) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(27 ⋅ 19) mod 10 ≡ (27 mod 10 ⋅ 19 mod 10) mod 10.
27 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 27 = 20 + 7 = 2 ⋅ 10 + 7 ist.
19 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 19 = 10 + 9 = 1 ⋅ 10 + 9 ist.
Somit gilt:
(27 ⋅ 19) mod 10 ≡ (7 ⋅ 9) mod 10 ≡ 63 mod 10 ≡ 3 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 7748 mod 823.
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. 774 -> x
2. mod(x²,823) -> 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: 7741=774
2: 7742=7741+1=7741⋅7741 ≡ 774⋅774=599076 ≡ 755 mod 823
4: 7744=7742+2=7742⋅7742 ≡ 755⋅755=570025 ≡ 509 mod 823
8: 7748=7744+4=7744⋅7744 ≡ 509⋅509=259081 ≡ 659 mod 823
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 476171 mod 499.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 171 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 171 an und zerlegen 171 in eine Summer von 2er-Potenzen:
171 = 128+32+8+2+1
1: 4761=476
2: 4762=4761+1=4761⋅4761 ≡ 476⋅476=226576 ≡ 30 mod 499
4: 4764=4762+2=4762⋅4762 ≡ 30⋅30=900 ≡ 401 mod 499
8: 4768=4764+4=4764⋅4764 ≡ 401⋅401=160801 ≡ 123 mod 499
16: 47616=4768+8=4768⋅4768 ≡ 123⋅123=15129 ≡ 159 mod 499
32: 47632=47616+16=47616⋅47616 ≡ 159⋅159=25281 ≡ 331 mod 499
64: 47664=47632+32=47632⋅47632 ≡ 331⋅331=109561 ≡ 280 mod 499
128: 476128=47664+64=47664⋅47664 ≡ 280⋅280=78400 ≡ 57 mod 499
476171
= 476128+32+8+2+1
= 476128⋅47632⋅4768⋅4762⋅4761
≡ 57 ⋅ 331 ⋅ 123 ⋅ 30 ⋅ 476 mod 499
≡ 18867 ⋅ 123 ⋅ 30 ⋅ 476 mod 499 ≡ 404 ⋅ 123 ⋅ 30 ⋅ 476 mod 499
≡ 49692 ⋅ 30 ⋅ 476 mod 499 ≡ 291 ⋅ 30 ⋅ 476 mod 499
≡ 8730 ⋅ 476 mod 499 ≡ 247 ⋅ 476 mod 499
≡ 117572 mod 499 ≡ 307 mod 499
Es gilt also: 476171 ≡ 307 mod 499
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 62.
Also bestimme x, so dass 62 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 62
| =>71 | = 1⋅62 + 9 |
| =>62 | = 6⋅9 + 8 |
| =>9 | = 1⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(71,62)=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= 9-1⋅8 | |||
| 8= 62-6⋅9 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅9 -1⋅(62 -6⋅ 9)
= 1⋅9 -1⋅62 +6⋅ 9) = -1⋅62 +7⋅ 9 (=1) |
| 9= 71-1⋅62 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅62 +7⋅(71 -1⋅ 62)
= -1⋅62 +7⋅71 -7⋅ 62) = 7⋅71 -8⋅ 62 (=1) |
Es gilt also: ggt(71,62)=1 = 7⋅71 -8⋅62
oder wenn man 7⋅71 auf die linke Seite bringt:
1 -7⋅71 = -8⋅62
-8⋅62 = -7⋅71 + 1 |+71⋅62
-8⋅62 + 71⋅62 = -7⋅71 + 71⋅62 + 1
(-8 + 71) ⋅ 62 = (-7 + 62) ⋅ 71 + 1
63⋅62 = 55⋅71 + 1
Es gilt also: 63⋅62 = 55⋅71 +1
Somit 63⋅62 = 1 mod 71
63 ist also das Inverse von 62 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 43 und q = 37. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
