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: (903 + 45001) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(903 + 45001) mod 9 ≡ (903 mod 9 + 45001 mod 9) mod 9.
903 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 903
= 900
45001 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 45001
= 45000
Somit gilt:
(903 + 45001) mod 9 ≡ (3 + 1) mod 9 ≡ 4 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (59 ⋅ 61) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(59 ⋅ 61) mod 9 ≡ (59 mod 9 ⋅ 61 mod 9) mod 9.
59 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 59 = 54 + 5 = 6 ⋅ 9 + 5 ist.
61 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 61 = 54 + 7 = 6 ⋅ 9 + 7 ist.
Somit gilt:
(59 ⋅ 61) mod 9 ≡ (5 ⋅ 7) mod 9 ≡ 35 mod 9 ≡ 8 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 13964 mod 233.
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. 139 -> x
2. mod(x²,233) -> 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: 1391=139
2: 1392=1391+1=1391⋅1391 ≡ 139⋅139=19321 ≡ 215 mod 233
4: 1394=1392+2=1392⋅1392 ≡ 215⋅215=46225 ≡ 91 mod 233
8: 1398=1394+4=1394⋅1394 ≡ 91⋅91=8281 ≡ 126 mod 233
16: 13916=1398+8=1398⋅1398 ≡ 126⋅126=15876 ≡ 32 mod 233
32: 13932=13916+16=13916⋅13916 ≡ 32⋅32=1024 ≡ 92 mod 233
64: 13964=13932+32=13932⋅13932 ≡ 92⋅92=8464 ≡ 76 mod 233
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 560130 mod 809.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 130 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 130 an und zerlegen 130 in eine Summer von 2er-Potenzen:
130 = 128+2
1: 5601=560
2: 5602=5601+1=5601⋅5601 ≡ 560⋅560=313600 ≡ 517 mod 809
4: 5604=5602+2=5602⋅5602 ≡ 517⋅517=267289 ≡ 319 mod 809
8: 5608=5604+4=5604⋅5604 ≡ 319⋅319=101761 ≡ 636 mod 809
16: 56016=5608+8=5608⋅5608 ≡ 636⋅636=404496 ≡ 805 mod 809
32: 56032=56016+16=56016⋅56016 ≡ 805⋅805=648025 ≡ 16 mod 809
64: 56064=56032+32=56032⋅56032 ≡ 16⋅16=256 ≡ 256 mod 809
128: 560128=56064+64=56064⋅56064 ≡ 256⋅256=65536 ≡ 7 mod 809
560130
= 560128+2
= 560128⋅5602
≡ 7 ⋅ 517 mod 809
≡ 3619 mod 809 ≡ 383 mod 809
Es gilt also: 560130 ≡ 383 mod 809
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 92.
Also bestimme x, so dass 92 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 92
| =>97 | = 1⋅92 + 5 |
| =>92 | = 18⋅5 + 2 |
| =>5 | = 2⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(97,92)=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= 5-2⋅2 | |||
| 2= 92-18⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -2⋅(92 -18⋅ 5)
= 1⋅5 -2⋅92 +36⋅ 5) = -2⋅92 +37⋅ 5 (=1) |
| 5= 97-1⋅92 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅92 +37⋅(97 -1⋅ 92)
= -2⋅92 +37⋅97 -37⋅ 92) = 37⋅97 -39⋅ 92 (=1) |
Es gilt also: ggt(97,92)=1 = 37⋅97 -39⋅92
oder wenn man 37⋅97 auf die linke Seite bringt:
1 -37⋅97 = -39⋅92
-39⋅92 = -37⋅97 + 1 |+97⋅92
-39⋅92 + 97⋅92 = -37⋅97 + 97⋅92 + 1
(-39 + 97) ⋅ 92 = (-37 + 92) ⋅ 97 + 1
58⋅92 = 55⋅97 + 1
Es gilt also: 58⋅92 = 55⋅97 +1
Somit 58⋅92 = 1 mod 97
58 ist also das Inverse von 92 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 41 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
