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: (268 - 36008) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(268 - 36008) mod 9 ≡ (268 mod 9 - 36008 mod 9) mod 9.
268 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 268
= 270
36008 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 36008
= 36000
Somit gilt:
(268 - 36008) mod 9 ≡ (7 - 8) mod 9 ≡ -1 mod 9 ≡ 8 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (29 ⋅ 82) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(29 ⋅ 82) mod 10 ≡ (29 mod 10 ⋅ 82 mod 10) mod 10.
29 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 29 = 20 + 9 = 2 ⋅ 10 + 9 ist.
82 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 82 = 80 + 2 = 8 ⋅ 10 + 2 ist.
Somit gilt:
(29 ⋅ 82) mod 10 ≡ (9 ⋅ 2) mod 10 ≡ 18 mod 10 ≡ 8 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 1628 mod 521.
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. 162 -> x
2. mod(x²,521) -> 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: 1621=162
2: 1622=1621+1=1621⋅1621 ≡ 162⋅162=26244 ≡ 194 mod 521
4: 1624=1622+2=1622⋅1622 ≡ 194⋅194=37636 ≡ 124 mod 521
8: 1628=1624+4=1624⋅1624 ≡ 124⋅124=15376 ≡ 267 mod 521
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 149135 mod 311.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 135 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 135 an und zerlegen 135 in eine Summer von 2er-Potenzen:
135 = 128+4+2+1
1: 1491=149
2: 1492=1491+1=1491⋅1491 ≡ 149⋅149=22201 ≡ 120 mod 311
4: 1494=1492+2=1492⋅1492 ≡ 120⋅120=14400 ≡ 94 mod 311
8: 1498=1494+4=1494⋅1494 ≡ 94⋅94=8836 ≡ 128 mod 311
16: 14916=1498+8=1498⋅1498 ≡ 128⋅128=16384 ≡ 212 mod 311
32: 14932=14916+16=14916⋅14916 ≡ 212⋅212=44944 ≡ 160 mod 311
64: 14964=14932+32=14932⋅14932 ≡ 160⋅160=25600 ≡ 98 mod 311
128: 149128=14964+64=14964⋅14964 ≡ 98⋅98=9604 ≡ 274 mod 311
149135
= 149128+4+2+1
= 149128⋅1494⋅1492⋅1491
≡ 274 ⋅ 94 ⋅ 120 ⋅ 149 mod 311
≡ 25756 ⋅ 120 ⋅ 149 mod 311 ≡ 254 ⋅ 120 ⋅ 149 mod 311
≡ 30480 ⋅ 149 mod 311 ≡ 2 ⋅ 149 mod 311
≡ 298 mod 311
Es gilt also: 149135 ≡ 298 mod 311
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 62.
Also bestimme x, so dass 62 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 62
| =>67 | = 1⋅62 + 5 |
| =>62 | = 12⋅5 + 2 |
| =>5 | = 2⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(67,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= 5-2⋅2 | |||
| 2= 62-12⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -2⋅(62 -12⋅ 5)
= 1⋅5 -2⋅62 +24⋅ 5) = -2⋅62 +25⋅ 5 (=1) |
| 5= 67-1⋅62 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅62 +25⋅(67 -1⋅ 62)
= -2⋅62 +25⋅67 -25⋅ 62) = 25⋅67 -27⋅ 62 (=1) |
Es gilt also: ggt(67,62)=1 = 25⋅67 -27⋅62
oder wenn man 25⋅67 auf die linke Seite bringt:
1 -25⋅67 = -27⋅62
-27⋅62 = -25⋅67 + 1 |+67⋅62
-27⋅62 + 67⋅62 = -25⋅67 + 67⋅62 + 1
(-27 + 67) ⋅ 62 = (-25 + 62) ⋅ 67 + 1
40⋅62 = 37⋅67 + 1
Es gilt also: 40⋅62 = 37⋅67 +1
Somit 40⋅62 = 1 mod 67
40 ist also das Inverse von 62 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 71 und q = 37. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.