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: (1805 + 177) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1805 + 177) mod 9 ≡ (1805 mod 9 + 177 mod 9) mod 9.
1805 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 1805
= 1800
177 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 177
= 180
Somit gilt:
(1805 + 177) mod 9 ≡ (5 + 6) mod 9 ≡ 11 mod 9 ≡ 2 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (47 ⋅ 69) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(47 ⋅ 69) mod 7 ≡ (47 mod 7 ⋅ 69 mod 7) mod 7.
47 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 47 = 42 + 5 = 6 ⋅ 7 + 5 ist.
69 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 69 = 63 + 6 = 9 ⋅ 7 + 6 ist.
Somit gilt:
(47 ⋅ 69) mod 7 ≡ (5 ⋅ 6) mod 7 ≡ 30 mod 7 ≡ 2 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 121128 mod 397.
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. 121 -> x
2. mod(x²,397) -> 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: 1211=121
2: 1212=1211+1=1211⋅1211 ≡ 121⋅121=14641 ≡ 349 mod 397
4: 1214=1212+2=1212⋅1212 ≡ 349⋅349=121801 ≡ 319 mod 397
8: 1218=1214+4=1214⋅1214 ≡ 319⋅319=101761 ≡ 129 mod 397
16: 12116=1218+8=1218⋅1218 ≡ 129⋅129=16641 ≡ 364 mod 397
32: 12132=12116+16=12116⋅12116 ≡ 364⋅364=132496 ≡ 295 mod 397
64: 12164=12132+32=12132⋅12132 ≡ 295⋅295=87025 ≡ 82 mod 397
128: 121128=12164+64=12164⋅12164 ≡ 82⋅82=6724 ≡ 372 mod 397
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 451141 mod 571.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 141 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 141 an und zerlegen 141 in eine Summer von 2er-Potenzen:
141 = 128+8+4+1
1: 4511=451
2: 4512=4511+1=4511⋅4511 ≡ 451⋅451=203401 ≡ 125 mod 571
4: 4514=4512+2=4512⋅4512 ≡ 125⋅125=15625 ≡ 208 mod 571
8: 4518=4514+4=4514⋅4514 ≡ 208⋅208=43264 ≡ 439 mod 571
16: 45116=4518+8=4518⋅4518 ≡ 439⋅439=192721 ≡ 294 mod 571
32: 45132=45116+16=45116⋅45116 ≡ 294⋅294=86436 ≡ 215 mod 571
64: 45164=45132+32=45132⋅45132 ≡ 215⋅215=46225 ≡ 545 mod 571
128: 451128=45164+64=45164⋅45164 ≡ 545⋅545=297025 ≡ 105 mod 571
451141
= 451128+8+4+1
= 451128⋅4518⋅4514⋅4511
≡ 105 ⋅ 439 ⋅ 208 ⋅ 451 mod 571
≡ 46095 ⋅ 208 ⋅ 451 mod 571 ≡ 415 ⋅ 208 ⋅ 451 mod 571
≡ 86320 ⋅ 451 mod 571 ≡ 99 ⋅ 451 mod 571
≡ 44649 mod 571 ≡ 111 mod 571
Es gilt also: 451141 ≡ 111 mod 571
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-59-Inverse zur Zahl 54.
Also bestimme x, so dass 54 ⋅ x ≡ 1 mod 59 gilt:
Berechnung des größten gemeinsamen Teilers von 59 und 54
| =>59 | = 1⋅54 + 5 |
| =>54 | = 10⋅5 + 4 |
| =>5 | = 1⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(59,54)=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= 54-10⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -1⋅(54 -10⋅ 5)
= 1⋅5 -1⋅54 +10⋅ 5) = -1⋅54 +11⋅ 5 (=1) |
| 5= 59-1⋅54 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅54 +11⋅(59 -1⋅ 54)
= -1⋅54 +11⋅59 -11⋅ 54) = 11⋅59 -12⋅ 54 (=1) |
Es gilt also: ggt(59,54)=1 = 11⋅59 -12⋅54
oder wenn man 11⋅59 auf die linke Seite bringt:
1 -11⋅59 = -12⋅54
-12⋅54 = -11⋅59 + 1 |+59⋅54
-12⋅54 + 59⋅54 = -11⋅59 + 59⋅54 + 1
(-12 + 59) ⋅ 54 = (-11 + 54) ⋅ 59 + 1
47⋅54 = 43⋅59 + 1
Es gilt also: 47⋅54 = 43⋅59 +1
Somit 47⋅54 = 1 mod 59
47 ist also das Inverse von 54 mod 59
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 59 und q = 79. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
