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: (71 - 2104) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(71 - 2104) mod 7 ≡ (71 mod 7 - 2104 mod 7) mod 7.
71 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 71
= 70
2104 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 2104
= 2100
Somit gilt:
(71 - 2104) mod 7 ≡ (1 - 4) mod 7 ≡ -3 mod 7 ≡ 4 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (58 ⋅ 81) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(58 ⋅ 81) mod 11 ≡ (58 mod 11 ⋅ 81 mod 11) mod 11.
58 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 58 = 55 + 3 = 5 ⋅ 11 + 3 ist.
81 mod 11 ≡ 4 mod 11 kann man relativ leicht bestimmen, weil ja 81 = 77 + 4 = 7 ⋅ 11 + 4 ist.
Somit gilt:
(58 ⋅ 81) mod 11 ≡ (3 ⋅ 4) mod 11 ≡ 12 mod 11 ≡ 1 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 34564 mod 613.
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. 345 -> x
2. mod(x²,613) -> 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: 3451=345
2: 3452=3451+1=3451⋅3451 ≡ 345⋅345=119025 ≡ 103 mod 613
4: 3454=3452+2=3452⋅3452 ≡ 103⋅103=10609 ≡ 188 mod 613
8: 3458=3454+4=3454⋅3454 ≡ 188⋅188=35344 ≡ 403 mod 613
16: 34516=3458+8=3458⋅3458 ≡ 403⋅403=162409 ≡ 577 mod 613
32: 34532=34516+16=34516⋅34516 ≡ 577⋅577=332929 ≡ 70 mod 613
64: 34564=34532+32=34532⋅34532 ≡ 70⋅70=4900 ≡ 609 mod 613
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 172148 mod 569.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 148 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 148 an und zerlegen 148 in eine Summer von 2er-Potenzen:
148 = 128+16+4
1: 1721=172
2: 1722=1721+1=1721⋅1721 ≡ 172⋅172=29584 ≡ 565 mod 569
4: 1724=1722+2=1722⋅1722 ≡ 565⋅565=319225 ≡ 16 mod 569
8: 1728=1724+4=1724⋅1724 ≡ 16⋅16=256 ≡ 256 mod 569
16: 17216=1728+8=1728⋅1728 ≡ 256⋅256=65536 ≡ 101 mod 569
32: 17232=17216+16=17216⋅17216 ≡ 101⋅101=10201 ≡ 528 mod 569
64: 17264=17232+32=17232⋅17232 ≡ 528⋅528=278784 ≡ 543 mod 569
128: 172128=17264+64=17264⋅17264 ≡ 543⋅543=294849 ≡ 107 mod 569
172148
= 172128+16+4
= 172128⋅17216⋅1724
≡ 107 ⋅ 101 ⋅ 16 mod 569
≡ 10807 ⋅ 16 mod 569 ≡ 565 ⋅ 16 mod 569
≡ 9040 mod 569 ≡ 505 mod 569
Es gilt also: 172148 ≡ 505 mod 569
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 36.
Also bestimme x, so dass 36 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 36
| =>101 | = 2⋅36 + 29 |
| =>36 | = 1⋅29 + 7 |
| =>29 | = 4⋅7 + 1 |
| =>7 | = 7⋅1 + 0 |
also gilt: ggt(101,36)=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-4⋅7 | |||
| 7= 36-1⋅29 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅29 -4⋅(36 -1⋅ 29)
= 1⋅29 -4⋅36 +4⋅ 29) = -4⋅36 +5⋅ 29 (=1) |
| 29= 101-2⋅36 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅36 +5⋅(101 -2⋅ 36)
= -4⋅36 +5⋅101 -10⋅ 36) = 5⋅101 -14⋅ 36 (=1) |
Es gilt also: ggt(101,36)=1 = 5⋅101 -14⋅36
oder wenn man 5⋅101 auf die linke Seite bringt:
1 -5⋅101 = -14⋅36
-14⋅36 = -5⋅101 + 1 |+101⋅36
-14⋅36 + 101⋅36 = -5⋅101 + 101⋅36 + 1
(-14 + 101) ⋅ 36 = (-5 + 36) ⋅ 101 + 1
87⋅36 = 31⋅101 + 1
Es gilt also: 87⋅36 = 31⋅101 +1
Somit 87⋅36 = 1 mod 101
87 ist also das Inverse von 36 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.