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: (802 + 203) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(802 + 203) mod 4 ≡ (802 mod 4 + 203 mod 4) mod 4.
802 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 802
= 800
203 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 203
= 200
Somit gilt:
(802 + 203) mod 4 ≡ (2 + 3) mod 4 ≡ 5 mod 4 ≡ 1 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (85 ⋅ 97) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(85 ⋅ 97) mod 7 ≡ (85 mod 7 ⋅ 97 mod 7) mod 7.
85 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 12 ⋅ 7 + 1 ist.
97 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 97 = 91 + 6 = 13 ⋅ 7 + 6 ist.
Somit gilt:
(85 ⋅ 97) mod 7 ≡ (1 ⋅ 6) mod 7 ≡ 6 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 42464 mod 953.
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. 424 -> x
2. mod(x²,953) -> 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: 4241=424
2: 4242=4241+1=4241⋅4241 ≡ 424⋅424=179776 ≡ 612 mod 953
4: 4244=4242+2=4242⋅4242 ≡ 612⋅612=374544 ≡ 15 mod 953
8: 4248=4244+4=4244⋅4244 ≡ 15⋅15=225 ≡ 225 mod 953
16: 42416=4248+8=4248⋅4248 ≡ 225⋅225=50625 ≡ 116 mod 953
32: 42432=42416+16=42416⋅42416 ≡ 116⋅116=13456 ≡ 114 mod 953
64: 42464=42432+32=42432⋅42432 ≡ 114⋅114=12996 ≡ 607 mod 953
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 22281 mod 593.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 81 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 81 an und zerlegen 81 in eine Summer von 2er-Potenzen:
81 = 64+16+1
1: 2221=222
2: 2222=2221+1=2221⋅2221 ≡ 222⋅222=49284 ≡ 65 mod 593
4: 2224=2222+2=2222⋅2222 ≡ 65⋅65=4225 ≡ 74 mod 593
8: 2228=2224+4=2224⋅2224 ≡ 74⋅74=5476 ≡ 139 mod 593
16: 22216=2228+8=2228⋅2228 ≡ 139⋅139=19321 ≡ 345 mod 593
32: 22232=22216+16=22216⋅22216 ≡ 345⋅345=119025 ≡ 425 mod 593
64: 22264=22232+32=22232⋅22232 ≡ 425⋅425=180625 ≡ 353 mod 593
22281
= 22264+16+1
= 22264⋅22216⋅2221
≡ 353 ⋅ 345 ⋅ 222 mod 593
≡ 121785 ⋅ 222 mod 593 ≡ 220 ⋅ 222 mod 593
≡ 48840 mod 593 ≡ 214 mod 593
Es gilt also: 22281 ≡ 214 mod 593
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 25.
Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 25
| =>67 | = 2⋅25 + 17 |
| =>25 | = 1⋅17 + 8 |
| =>17 | = 2⋅8 + 1 |
| =>8 | = 8⋅1 + 0 |
also gilt: ggt(67,25)=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= 17-2⋅8 | |||
| 8= 25-1⋅17 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅17 -2⋅(25 -1⋅ 17)
= 1⋅17 -2⋅25 +2⋅ 17) = -2⋅25 +3⋅ 17 (=1) |
| 17= 67-2⋅25 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅25 +3⋅(67 -2⋅ 25)
= -2⋅25 +3⋅67 -6⋅ 25) = 3⋅67 -8⋅ 25 (=1) |
Es gilt also: ggt(67,25)=1 = 3⋅67 -8⋅25
oder wenn man 3⋅67 auf die linke Seite bringt:
1 -3⋅67 = -8⋅25
-8⋅25 = -3⋅67 + 1 |+67⋅25
-8⋅25 + 67⋅25 = -3⋅67 + 67⋅25 + 1
(-8 + 67) ⋅ 25 = (-3 + 25) ⋅ 67 + 1
59⋅25 = 22⋅67 + 1
Es gilt also: 59⋅25 = 22⋅67 +1
Somit 59⋅25 = 1 mod 67
59 ist also das Inverse von 25 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.