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: (2001 - 503) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2001 - 503) mod 5 ≡ (2001 mod 5 - 503 mod 5) mod 5.
2001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 2001
= 2000
503 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 503
= 500
Somit gilt:
(2001 - 503) mod 5 ≡ (1 - 3) mod 5 ≡ -2 mod 5 ≡ 3 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (70 ⋅ 100) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(70 ⋅ 100) mod 10 ≡ (70 mod 10 ⋅ 100 mod 10) mod 10.
70 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 70 = 70 + 0 = 7 ⋅ 10 + 0 ist.
100 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 100 = 100 + 0 = 10 ⋅ 10 + 0 ist.
Somit gilt:
(70 ⋅ 100) mod 10 ≡ (0 ⋅ 0) mod 10 ≡ 0 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 64416 mod 733.
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. 644 -> x
2. mod(x²,733) -> 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: 6441=644
2: 6442=6441+1=6441⋅6441 ≡ 644⋅644=414736 ≡ 591 mod 733
4: 6444=6442+2=6442⋅6442 ≡ 591⋅591=349281 ≡ 373 mod 733
8: 6448=6444+4=6444⋅6444 ≡ 373⋅373=139129 ≡ 592 mod 733
16: 64416=6448+8=6448⋅6448 ≡ 592⋅592=350464 ≡ 90 mod 733
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 422176 mod 929.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 176 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 176 an und zerlegen 176 in eine Summer von 2er-Potenzen:
176 = 128+32+16
1: 4221=422
2: 4222=4221+1=4221⋅4221 ≡ 422⋅422=178084 ≡ 645 mod 929
4: 4224=4222+2=4222⋅4222 ≡ 645⋅645=416025 ≡ 762 mod 929
8: 4228=4224+4=4224⋅4224 ≡ 762⋅762=580644 ≡ 19 mod 929
16: 42216=4228+8=4228⋅4228 ≡ 19⋅19=361 ≡ 361 mod 929
32: 42232=42216+16=42216⋅42216 ≡ 361⋅361=130321 ≡ 261 mod 929
64: 42264=42232+32=42232⋅42232 ≡ 261⋅261=68121 ≡ 304 mod 929
128: 422128=42264+64=42264⋅42264 ≡ 304⋅304=92416 ≡ 445 mod 929
422176
= 422128+32+16
= 422128⋅42232⋅42216
≡ 445 ⋅ 261 ⋅ 361 mod 929
≡ 116145 ⋅ 361 mod 929 ≡ 20 ⋅ 361 mod 929
≡ 7220 mod 929 ≡ 717 mod 929
Es gilt also: 422176 ≡ 717 mod 929
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 62.
Also bestimme x, so dass 62 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 62
| =>83 | = 1⋅62 + 21 |
| =>62 | = 2⋅21 + 20 |
| =>21 | = 1⋅20 + 1 |
| =>20 | = 20⋅1 + 0 |
also gilt: ggt(83,62)=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= 21-1⋅20 | |||
| 20= 62-2⋅21 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅21 -1⋅(62 -2⋅ 21)
= 1⋅21 -1⋅62 +2⋅ 21) = -1⋅62 +3⋅ 21 (=1) |
| 21= 83-1⋅62 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅62 +3⋅(83 -1⋅ 62)
= -1⋅62 +3⋅83 -3⋅ 62) = 3⋅83 -4⋅ 62 (=1) |
Es gilt also: ggt(83,62)=1 = 3⋅83 -4⋅62
oder wenn man 3⋅83 auf die linke Seite bringt:
1 -3⋅83 = -4⋅62
-4⋅62 = -3⋅83 + 1 |+83⋅62
-4⋅62 + 83⋅62 = -3⋅83 + 83⋅62 + 1
(-4 + 83) ⋅ 62 = (-3 + 62) ⋅ 83 + 1
79⋅62 = 59⋅83 + 1
Es gilt also: 79⋅62 = 59⋅83 +1
Somit 79⋅62 = 1 mod 83
79 ist also das Inverse von 62 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 31 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.