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: (133 + 146) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(133 + 146) mod 7 ≡ (133 mod 7 + 146 mod 7) mod 7.
133 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 133
= 140
146 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 146
= 140
Somit gilt:
(133 + 146) mod 7 ≡ (0 + 6) mod 7 ≡ 6 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (93 ⋅ 61) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(93 ⋅ 61) mod 6 ≡ (93 mod 6 ⋅ 61 mod 6) mod 6.
93 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 93 = 90 + 3 = 15 ⋅ 6 + 3 ist.
61 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 10 ⋅ 6 + 1 ist.
Somit gilt:
(93 ⋅ 61) mod 6 ≡ (3 ⋅ 1) mod 6 ≡ 3 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 336128 mod 353.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 336 -> x
2. mod(x²,353) -> 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: 3361=336
2: 3362=3361+1=3361⋅3361 ≡ 336⋅336=112896 ≡ 289 mod 353
4: 3364=3362+2=3362⋅3362 ≡ 289⋅289=83521 ≡ 213 mod 353
8: 3368=3364+4=3364⋅3364 ≡ 213⋅213=45369 ≡ 185 mod 353
16: 33616=3368+8=3368⋅3368 ≡ 185⋅185=34225 ≡ 337 mod 353
32: 33632=33616+16=33616⋅33616 ≡ 337⋅337=113569 ≡ 256 mod 353
64: 33664=33632+32=33632⋅33632 ≡ 256⋅256=65536 ≡ 231 mod 353
128: 336128=33664+64=33664⋅33664 ≡ 231⋅231=53361 ≡ 58 mod 353
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 29573 mod 967.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 73 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 73 an und zerlegen 73 in eine Summer von 2er-Potenzen:
73 = 64+8+1
1: 2951=295
2: 2952=2951+1=2951⋅2951 ≡ 295⋅295=87025 ≡ 962 mod 967
4: 2954=2952+2=2952⋅2952 ≡ 962⋅962=925444 ≡ 25 mod 967
8: 2958=2954+4=2954⋅2954 ≡ 25⋅25=625 ≡ 625 mod 967
16: 29516=2958+8=2958⋅2958 ≡ 625⋅625=390625 ≡ 924 mod 967
32: 29532=29516+16=29516⋅29516 ≡ 924⋅924=853776 ≡ 882 mod 967
64: 29564=29532+32=29532⋅29532 ≡ 882⋅882=777924 ≡ 456 mod 967
29573
= 29564+8+1
= 29564⋅2958⋅2951
≡ 456 ⋅ 625 ⋅ 295 mod 967
≡ 285000 ⋅ 295 mod 967 ≡ 702 ⋅ 295 mod 967
≡ 207090 mod 967 ≡ 152 mod 967
Es gilt also: 29573 ≡ 152 mod 967
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 55.
Also bestimme x, so dass 55 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 55
| =>71 | = 1⋅55 + 16 |
| =>55 | = 3⋅16 + 7 |
| =>16 | = 2⋅7 + 2 |
| =>7 | = 3⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(71,55)=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= 7-3⋅2 | |||
| 2= 16-2⋅7 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅7 -3⋅(16 -2⋅ 7)
= 1⋅7 -3⋅16 +6⋅ 7) = -3⋅16 +7⋅ 7 (=1) |
| 7= 55-3⋅16 | eingesetzt in die Zeile drüber: | 1 |
= -3⋅16 +7⋅(55 -3⋅ 16)
= -3⋅16 +7⋅55 -21⋅ 16) = 7⋅55 -24⋅ 16 (=1) |
| 16= 71-1⋅55 | eingesetzt in die Zeile drüber: | 1 |
= 7⋅55 -24⋅(71 -1⋅ 55)
= 7⋅55 -24⋅71 +24⋅ 55) = -24⋅71 +31⋅ 55 (=1) |
Es gilt also: ggt(71,55)=1 = -24⋅71 +31⋅55
oder wenn man -24⋅71 auf die linke Seite bringt:
1 +24⋅71 = +31⋅55
Es gilt also: 31⋅55 = 24⋅71 +1
Somit 31⋅55 = 1 mod 71
31 ist also das Inverse von 55 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 47 und q = 97. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
