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: (251 - 1495) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(251 - 1495) mod 5 ≡ (251 mod 5 - 1495 mod 5) mod 5.
251 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 251
= 250
1495 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1495
= 1400
Somit gilt:
(251 - 1495) mod 5 ≡ (1 - 0) mod 5 ≡ 1 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (19 ⋅ 97) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(19 ⋅ 97) mod 11 ≡ (19 mod 11 ⋅ 97 mod 11) mod 11.
19 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 19 = 11 + 8 = 1 ⋅ 11 + 8 ist.
97 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 97 = 88 + 9 = 8 ⋅ 11 + 9 ist.
Somit gilt:
(19 ⋅ 97) mod 11 ≡ (8 ⋅ 9) mod 11 ≡ 72 mod 11 ≡ 6 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 43416 mod 499.
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. 434 -> x
2. mod(x²,499) -> 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: 4341=434
2: 4342=4341+1=4341⋅4341 ≡ 434⋅434=188356 ≡ 233 mod 499
4: 4344=4342+2=4342⋅4342 ≡ 233⋅233=54289 ≡ 397 mod 499
8: 4348=4344+4=4344⋅4344 ≡ 397⋅397=157609 ≡ 424 mod 499
16: 43416=4348+8=4348⋅4348 ≡ 424⋅424=179776 ≡ 136 mod 499
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 694210 mod 907.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 210 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 210 an und zerlegen 210 in eine Summer von 2er-Potenzen:
210 = 128+64+16+2
1: 6941=694
2: 6942=6941+1=6941⋅6941 ≡ 694⋅694=481636 ≡ 19 mod 907
4: 6944=6942+2=6942⋅6942 ≡ 19⋅19=361 ≡ 361 mod 907
8: 6948=6944+4=6944⋅6944 ≡ 361⋅361=130321 ≡ 620 mod 907
16: 69416=6948+8=6948⋅6948 ≡ 620⋅620=384400 ≡ 739 mod 907
32: 69432=69416+16=69416⋅69416 ≡ 739⋅739=546121 ≡ 107 mod 907
64: 69464=69432+32=69432⋅69432 ≡ 107⋅107=11449 ≡ 565 mod 907
128: 694128=69464+64=69464⋅69464 ≡ 565⋅565=319225 ≡ 868 mod 907
694210
= 694128+64+16+2
= 694128⋅69464⋅69416⋅6942
≡ 868 ⋅ 565 ⋅ 739 ⋅ 19 mod 907
≡ 490420 ⋅ 739 ⋅ 19 mod 907 ≡ 640 ⋅ 739 ⋅ 19 mod 907
≡ 472960 ⋅ 19 mod 907 ≡ 413 ⋅ 19 mod 907
≡ 7847 mod 907 ≡ 591 mod 907
Es gilt also: 694210 ≡ 591 mod 907
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 40.
Also bestimme x, so dass 40 ⋅ x ≡ 1 mod 61 gilt:
Berechnung des größten gemeinsamen Teilers von 61 und 40
| =>61 | = 1⋅40 + 21 |
| =>40 | = 1⋅21 + 19 |
| =>21 | = 1⋅19 + 2 |
| =>19 | = 9⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(61,40)=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= 19-9⋅2 | |||
| 2= 21-1⋅19 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅19 -9⋅(21 -1⋅ 19)
= 1⋅19 -9⋅21 +9⋅ 19) = -9⋅21 +10⋅ 19 (=1) |
| 19= 40-1⋅21 | eingesetzt in die Zeile drüber: | 1 |
= -9⋅21 +10⋅(40 -1⋅ 21)
= -9⋅21 +10⋅40 -10⋅ 21) = 10⋅40 -19⋅ 21 (=1) |
| 21= 61-1⋅40 | eingesetzt in die Zeile drüber: | 1 |
= 10⋅40 -19⋅(61 -1⋅ 40)
= 10⋅40 -19⋅61 +19⋅ 40) = -19⋅61 +29⋅ 40 (=1) |
Es gilt also: ggt(61,40)=1 = -19⋅61 +29⋅40
oder wenn man -19⋅61 auf die linke Seite bringt:
1 +19⋅61 = +29⋅40
Es gilt also: 29⋅40 = 19⋅61 +1
Somit 29⋅40 = 1 mod 61
29 ist also das Inverse von 40 mod 61
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 37. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
