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: (3602 - 361) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(3602 - 361) mod 9 ≡ (3602 mod 9 - 361 mod 9) mod 9.
3602 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 3602
= 3600
361 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 361
= 360
Somit gilt:
(3602 - 361) mod 9 ≡ (2 - 1) mod 9 ≡ 1 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (67 ⋅ 45) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(67 ⋅ 45) mod 11 ≡ (67 mod 11 ⋅ 45 mod 11) mod 11.
67 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 67 = 66 + 1 = 6 ⋅ 11 + 1 ist.
45 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 45 = 44 + 1 = 4 ⋅ 11 + 1 ist.
Somit gilt:
(67 ⋅ 45) mod 11 ≡ (1 ⋅ 1) mod 11 ≡ 1 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 27216 mod 467.
Die 16 im Exponent ist ja ein reine 2er-Potenz (24).
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. 272 -> x
2. mod(x²,467) -> 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: 2721=272
2: 2722=2721+1=2721⋅2721 ≡ 272⋅272=73984 ≡ 198 mod 467
4: 2724=2722+2=2722⋅2722 ≡ 198⋅198=39204 ≡ 443 mod 467
8: 2728=2724+4=2724⋅2724 ≡ 443⋅443=196249 ≡ 109 mod 467
16: 27216=2728+8=2728⋅2728 ≡ 109⋅109=11881 ≡ 206 mod 467
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 214146 mod 233.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 146 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 146 an und zerlegen 146 in eine Summer von 2er-Potenzen:
146 = 128+16+2
1: 2141=214
2: 2142=2141+1=2141⋅2141 ≡ 214⋅214=45796 ≡ 128 mod 233
4: 2144=2142+2=2142⋅2142 ≡ 128⋅128=16384 ≡ 74 mod 233
8: 2148=2144+4=2144⋅2144 ≡ 74⋅74=5476 ≡ 117 mod 233
16: 21416=2148+8=2148⋅2148 ≡ 117⋅117=13689 ≡ 175 mod 233
32: 21432=21416+16=21416⋅21416 ≡ 175⋅175=30625 ≡ 102 mod 233
64: 21464=21432+32=21432⋅21432 ≡ 102⋅102=10404 ≡ 152 mod 233
128: 214128=21464+64=21464⋅21464 ≡ 152⋅152=23104 ≡ 37 mod 233
214146
= 214128+16+2
= 214128⋅21416⋅2142
≡ 37 ⋅ 175 ⋅ 128 mod 233
≡ 6475 ⋅ 128 mod 233 ≡ 184 ⋅ 128 mod 233
≡ 23552 mod 233 ≡ 19 mod 233
Es gilt also: 214146 ≡ 19 mod 233
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 43.
Also bestimme x, so dass 43 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 43
| =>101 | = 2⋅43 + 15 |
| =>43 | = 2⋅15 + 13 |
| =>15 | = 1⋅13 + 2 |
| =>13 | = 6⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(101,43)=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= 13-6⋅2 | |||
| 2= 15-1⋅13 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅13 -6⋅(15 -1⋅ 13)
= 1⋅13 -6⋅15 +6⋅ 13) = -6⋅15 +7⋅ 13 (=1) |
| 13= 43-2⋅15 | eingesetzt in die Zeile drüber: | 1 |
= -6⋅15 +7⋅(43 -2⋅ 15)
= -6⋅15 +7⋅43 -14⋅ 15) = 7⋅43 -20⋅ 15 (=1) |
| 15= 101-2⋅43 | eingesetzt in die Zeile drüber: | 1 |
= 7⋅43 -20⋅(101 -2⋅ 43)
= 7⋅43 -20⋅101 +40⋅ 43) = -20⋅101 +47⋅ 43 (=1) |
Es gilt also: ggt(101,43)=1 = -20⋅101 +47⋅43
oder wenn man -20⋅101 auf die linke Seite bringt:
1 +20⋅101 = +47⋅43
Es gilt also: 47⋅43 = 20⋅101 +1
Somit 47⋅43 = 1 mod 101
47 ist also das Inverse von 43 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 67 und q = 73. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
