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: (92 + 368) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(92 + 368) mod 9 ≡ (92 mod 9 + 368 mod 9) mod 9.
92 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 92
= 90
368 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 368
= 360
Somit gilt:
(92 + 368) mod 9 ≡ (2 + 8) mod 9 ≡ 10 mod 9 ≡ 1 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (65 ⋅ 29) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(65 ⋅ 29) mod 7 ≡ (65 mod 7 ⋅ 29 mod 7) mod 7.
65 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 9 ⋅ 7 + 2 ist.
29 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 29 = 28 + 1 = 4 ⋅ 7 + 1 ist.
Somit gilt:
(65 ⋅ 29) mod 7 ≡ (2 ⋅ 1) mod 7 ≡ 2 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 55864 mod 787.
Die 64 im Exponent ist ja ein reine 2er-Potenz (26).
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. 558 -> x
2. mod(x²,787) -> 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: 5581=558
2: 5582=5581+1=5581⋅5581 ≡ 558⋅558=311364 ≡ 499 mod 787
4: 5584=5582+2=5582⋅5582 ≡ 499⋅499=249001 ≡ 309 mod 787
8: 5588=5584+4=5584⋅5584 ≡ 309⋅309=95481 ≡ 254 mod 787
16: 55816=5588+8=5588⋅5588 ≡ 254⋅254=64516 ≡ 769 mod 787
32: 55832=55816+16=55816⋅55816 ≡ 769⋅769=591361 ≡ 324 mod 787
64: 55864=55832+32=55832⋅55832 ≡ 324⋅324=104976 ≡ 305 mod 787
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 29578 mod 599.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 78 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 78 an und zerlegen 78 in eine Summer von 2er-Potenzen:
78 = 64+8+4+2
1: 2951=295
2: 2952=2951+1=2951⋅2951 ≡ 295⋅295=87025 ≡ 170 mod 599
4: 2954=2952+2=2952⋅2952 ≡ 170⋅170=28900 ≡ 148 mod 599
8: 2958=2954+4=2954⋅2954 ≡ 148⋅148=21904 ≡ 340 mod 599
16: 29516=2958+8=2958⋅2958 ≡ 340⋅340=115600 ≡ 592 mod 599
32: 29532=29516+16=29516⋅29516 ≡ 592⋅592=350464 ≡ 49 mod 599
64: 29564=29532+32=29532⋅29532 ≡ 49⋅49=2401 ≡ 5 mod 599
29578
= 29564+8+4+2
= 29564⋅2958⋅2954⋅2952
≡ 5 ⋅ 340 ⋅ 148 ⋅ 170 mod 599
≡ 1700 ⋅ 148 ⋅ 170 mod 599 ≡ 502 ⋅ 148 ⋅ 170 mod 599
≡ 74296 ⋅ 170 mod 599 ≡ 20 ⋅ 170 mod 599
≡ 3400 mod 599 ≡ 405 mod 599
Es gilt also: 29578 ≡ 405 mod 599
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-89-Inverse zur Zahl 60.
Also bestimme x, so dass 60 ⋅ x ≡ 1 mod 89 gilt:
Berechnung des größten gemeinsamen Teilers von 89 und 60
| =>89 | = 1⋅60 + 29 |
| =>60 | = 2⋅29 + 2 |
| =>29 | = 14⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(89,60)=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= 29-14⋅2 | |||
| 2= 60-2⋅29 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅29 -14⋅(60 -2⋅ 29)
= 1⋅29 -14⋅60 +28⋅ 29) = -14⋅60 +29⋅ 29 (=1) |
| 29= 89-1⋅60 | eingesetzt in die Zeile drüber: | 1 |
= -14⋅60 +29⋅(89 -1⋅ 60)
= -14⋅60 +29⋅89 -29⋅ 60) = 29⋅89 -43⋅ 60 (=1) |
Es gilt also: ggt(89,60)=1 = 29⋅89 -43⋅60
oder wenn man 29⋅89 auf die linke Seite bringt:
1 -29⋅89 = -43⋅60
-43⋅60 = -29⋅89 + 1 |+89⋅60
-43⋅60 + 89⋅60 = -29⋅89 + 89⋅60 + 1
(-43 + 89) ⋅ 60 = (-29 + 60) ⋅ 89 + 1
46⋅60 = 31⋅89 + 1
Es gilt also: 46⋅60 = 31⋅89 +1
Somit 46⋅60 = 1 mod 89
46 ist also das Inverse von 60 mod 89
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 73 und q = 53. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.