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: (1999 - 2505) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1999 - 2505) mod 5 ≡ (1999 mod 5 - 2505 mod 5) mod 5.
1999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1999
= 1900
2505 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2505
= 2500
Somit gilt:
(1999 - 2505) mod 5 ≡ (4 - 0) mod 5 ≡ 4 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (35 ⋅ 25) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(35 ⋅ 25) mod 10 ≡ (35 mod 10 ⋅ 25 mod 10) mod 10.
35 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 35 = 30 + 5 = 3 ⋅ 10 + 5 ist.
25 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 25 = 20 + 5 = 2 ⋅ 10 + 5 ist.
Somit gilt:
(35 ⋅ 25) mod 10 ≡ (5 ⋅ 5) mod 10 ≡ 25 mod 10 ≡ 5 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 56932 mod 733.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 569 -> x
2. mod(x²,733) -> 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: 5691=569
2: 5692=5691+1=5691⋅5691 ≡ 569⋅569=323761 ≡ 508 mod 733
4: 5694=5692+2=5692⋅5692 ≡ 508⋅508=258064 ≡ 48 mod 733
8: 5698=5694+4=5694⋅5694 ≡ 48⋅48=2304 ≡ 105 mod 733
16: 56916=5698+8=5698⋅5698 ≡ 105⋅105=11025 ≡ 30 mod 733
32: 56932=56916+16=56916⋅56916 ≡ 30⋅30=900 ≡ 167 mod 733
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 213189 mod 331.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 189 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 189 an und zerlegen 189 in eine Summer von 2er-Potenzen:
189 = 128+32+16+8+4+1
1: 2131=213
2: 2132=2131+1=2131⋅2131 ≡ 213⋅213=45369 ≡ 22 mod 331
4: 2134=2132+2=2132⋅2132 ≡ 22⋅22=484 ≡ 153 mod 331
8: 2138=2134+4=2134⋅2134 ≡ 153⋅153=23409 ≡ 239 mod 331
16: 21316=2138+8=2138⋅2138 ≡ 239⋅239=57121 ≡ 189 mod 331
32: 21332=21316+16=21316⋅21316 ≡ 189⋅189=35721 ≡ 304 mod 331
64: 21364=21332+32=21332⋅21332 ≡ 304⋅304=92416 ≡ 67 mod 331
128: 213128=21364+64=21364⋅21364 ≡ 67⋅67=4489 ≡ 186 mod 331
213189
= 213128+32+16+8+4+1
= 213128⋅21332⋅21316⋅2138⋅2134⋅2131
≡ 186 ⋅ 304 ⋅ 189 ⋅ 239 ⋅ 153 ⋅ 213 mod 331
≡ 56544 ⋅ 189 ⋅ 239 ⋅ 153 ⋅ 213 mod 331 ≡ 274 ⋅ 189 ⋅ 239 ⋅ 153 ⋅ 213 mod 331
≡ 51786 ⋅ 239 ⋅ 153 ⋅ 213 mod 331 ≡ 150 ⋅ 239 ⋅ 153 ⋅ 213 mod 331
≡ 35850 ⋅ 153 ⋅ 213 mod 331 ≡ 102 ⋅ 153 ⋅ 213 mod 331
≡ 15606 ⋅ 213 mod 331 ≡ 49 ⋅ 213 mod 331
≡ 10437 mod 331 ≡ 176 mod 331
Es gilt also: 213189 ≡ 176 mod 331
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 = 43 und q = 47. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
