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: (2004 - 5004) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2004 - 5004) mod 5 ≡ (2004 mod 5 - 5004 mod 5) mod 5.
2004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 2004
= 2000
5004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 5004
= 5000
Somit gilt:
(2004 - 5004) mod 5 ≡ (4 - 4) mod 5 ≡ 0 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (81 ⋅ 73) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(81 ⋅ 73) mod 10 ≡ (81 mod 10 ⋅ 73 mod 10) mod 10.
81 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 8 ⋅ 10 + 1 ist.
73 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 73 = 70 + 3 = 7 ⋅ 10 + 3 ist.
Somit gilt:
(81 ⋅ 73) mod 10 ≡ (1 ⋅ 3) mod 10 ≡ 3 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 32716 mod 383.
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. 327 -> x
2. mod(x²,383) -> 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: 3271=327
2: 3272=3271+1=3271⋅3271 ≡ 327⋅327=106929 ≡ 72 mod 383
4: 3274=3272+2=3272⋅3272 ≡ 72⋅72=5184 ≡ 205 mod 383
8: 3278=3274+4=3274⋅3274 ≡ 205⋅205=42025 ≡ 278 mod 383
16: 32716=3278+8=3278⋅3278 ≡ 278⋅278=77284 ≡ 301 mod 383
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 400229 mod 743.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 229 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 229 an und zerlegen 229 in eine Summer von 2er-Potenzen:
229 = 128+64+32+4+1
1: 4001=400
2: 4002=4001+1=4001⋅4001 ≡ 400⋅400=160000 ≡ 255 mod 743
4: 4004=4002+2=4002⋅4002 ≡ 255⋅255=65025 ≡ 384 mod 743
8: 4008=4004+4=4004⋅4004 ≡ 384⋅384=147456 ≡ 342 mod 743
16: 40016=4008+8=4008⋅4008 ≡ 342⋅342=116964 ≡ 313 mod 743
32: 40032=40016+16=40016⋅40016 ≡ 313⋅313=97969 ≡ 636 mod 743
64: 40064=40032+32=40032⋅40032 ≡ 636⋅636=404496 ≡ 304 mod 743
128: 400128=40064+64=40064⋅40064 ≡ 304⋅304=92416 ≡ 284 mod 743
400229
= 400128+64+32+4+1
= 400128⋅40064⋅40032⋅4004⋅4001
≡ 284 ⋅ 304 ⋅ 636 ⋅ 384 ⋅ 400 mod 743
≡ 86336 ⋅ 636 ⋅ 384 ⋅ 400 mod 743 ≡ 148 ⋅ 636 ⋅ 384 ⋅ 400 mod 743
≡ 94128 ⋅ 384 ⋅ 400 mod 743 ≡ 510 ⋅ 384 ⋅ 400 mod 743
≡ 195840 ⋅ 400 mod 743 ≡ 431 ⋅ 400 mod 743
≡ 172400 mod 743 ≡ 24 mod 743
Es gilt also: 400229 ≡ 24 mod 743
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 39.
Also bestimme x, so dass 39 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 39
| =>83 | = 2⋅39 + 5 |
| =>39 | = 7⋅5 + 4 |
| =>5 | = 1⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(83,39)=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-1⋅4 | |||
| 4= 39-7⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -1⋅(39 -7⋅ 5)
= 1⋅5 -1⋅39 +7⋅ 5) = -1⋅39 +8⋅ 5 (=1) |
| 5= 83-2⋅39 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅39 +8⋅(83 -2⋅ 39)
= -1⋅39 +8⋅83 -16⋅ 39) = 8⋅83 -17⋅ 39 (=1) |
Es gilt also: ggt(83,39)=1 = 8⋅83 -17⋅39
oder wenn man 8⋅83 auf die linke Seite bringt:
1 -8⋅83 = -17⋅39
-17⋅39 = -8⋅83 + 1 |+83⋅39
-17⋅39 + 83⋅39 = -8⋅83 + 83⋅39 + 1
(-17 + 83) ⋅ 39 = (-8 + 39) ⋅ 83 + 1
66⋅39 = 31⋅83 + 1
Es gilt also: 66⋅39 = 31⋅83 +1
Somit 66⋅39 = 1 mod 83
66 ist also das Inverse von 39 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 31. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
