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: (3198 - 3200) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(3198 - 3200) mod 8 ≡ (3198 mod 8 - 3200 mod 8) mod 8.
3198 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 3198
= 3200
3200 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 3200
= 3200
Somit gilt:
(3198 - 3200) mod 8 ≡ (6 - 0) mod 8 ≡ 6 mod 8.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (73 ⋅ 47) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(73 ⋅ 47) mod 5 ≡ (73 mod 5 ⋅ 47 mod 5) mod 5.
73 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 73 = 70 + 3 = 14 ⋅ 5 + 3 ist.
47 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 47 = 45 + 2 = 9 ⋅ 5 + 2 ist.
Somit gilt:
(73 ⋅ 47) mod 5 ≡ (3 ⋅ 2) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 1378 mod 439.
Die 8 im Exponent ist ja ein reine 2er-Potenz (23).
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. 137 -> x
2. mod(x²,439) -> 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: 1371=137
2: 1372=1371+1=1371⋅1371 ≡ 137⋅137=18769 ≡ 331 mod 439
4: 1374=1372+2=1372⋅1372 ≡ 331⋅331=109561 ≡ 250 mod 439
8: 1378=1374+4=1374⋅1374 ≡ 250⋅250=62500 ≡ 162 mod 439
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 644181 mod 937.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 181 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 181 an und zerlegen 181 in eine Summer von 2er-Potenzen:
181 = 128+32+16+4+1
1: 6441=644
2: 6442=6441+1=6441⋅6441 ≡ 644⋅644=414736 ≡ 582 mod 937
4: 6444=6442+2=6442⋅6442 ≡ 582⋅582=338724 ≡ 467 mod 937
8: 6448=6444+4=6444⋅6444 ≡ 467⋅467=218089 ≡ 705 mod 937
16: 64416=6448+8=6448⋅6448 ≡ 705⋅705=497025 ≡ 415 mod 937
32: 64432=64416+16=64416⋅64416 ≡ 415⋅415=172225 ≡ 754 mod 937
64: 64464=64432+32=64432⋅64432 ≡ 754⋅754=568516 ≡ 694 mod 937
128: 644128=64464+64=64464⋅64464 ≡ 694⋅694=481636 ≡ 18 mod 937
644181
= 644128+32+16+4+1
= 644128⋅64432⋅64416⋅6444⋅6441
≡ 18 ⋅ 754 ⋅ 415 ⋅ 467 ⋅ 644 mod 937
≡ 13572 ⋅ 415 ⋅ 467 ⋅ 644 mod 937 ≡ 454 ⋅ 415 ⋅ 467 ⋅ 644 mod 937
≡ 188410 ⋅ 467 ⋅ 644 mod 937 ≡ 73 ⋅ 467 ⋅ 644 mod 937
≡ 34091 ⋅ 644 mod 937 ≡ 359 ⋅ 644 mod 937
≡ 231196 mod 937 ≡ 694 mod 937
Es gilt also: 644181 ≡ 694 mod 937
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-59-Inverse zur Zahl 24.
Also bestimme x, so dass 24 ⋅ x ≡ 1 mod 59 gilt:
Berechnung des größten gemeinsamen Teilers von 59 und 24
| =>59 | = 2⋅24 + 11 |
| =>24 | = 2⋅11 + 2 |
| =>11 | = 5⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(59,24)=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= 11-5⋅2 | |||
| 2= 24-2⋅11 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅11 -5⋅(24 -2⋅ 11)
= 1⋅11 -5⋅24 +10⋅ 11) = -5⋅24 +11⋅ 11 (=1) |
| 11= 59-2⋅24 | eingesetzt in die Zeile drüber: | 1 |
= -5⋅24 +11⋅(59 -2⋅ 24)
= -5⋅24 +11⋅59 -22⋅ 24) = 11⋅59 -27⋅ 24 (=1) |
Es gilt also: ggt(59,24)=1 = 11⋅59 -27⋅24
oder wenn man 11⋅59 auf die linke Seite bringt:
1 -11⋅59 = -27⋅24
-27⋅24 = -11⋅59 + 1 |+59⋅24
-27⋅24 + 59⋅24 = -11⋅59 + 59⋅24 + 1
(-27 + 59) ⋅ 24 = (-11 + 24) ⋅ 59 + 1
32⋅24 = 13⋅59 + 1
Es gilt also: 32⋅24 = 13⋅59 +1
Somit 32⋅24 = 1 mod 59
32 ist also das Inverse von 24 mod 59
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 37 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
