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: (100 + 996) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(100 + 996) mod 5 ≡ (100 mod 5 + 996 mod 5) mod 5.
100 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 100
= 100
996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 996
= 900
Somit gilt:
(100 + 996) mod 5 ≡ (0 + 1) mod 5 ≡ 1 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (50 ⋅ 53) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(50 ⋅ 53) mod 3 ≡ (50 mod 3 ⋅ 53 mod 3) mod 3.
50 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 50 = 48 + 2 = 16 ⋅ 3 + 2 ist.
53 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 53 = 51 + 2 = 17 ⋅ 3 + 2 ist.
Somit gilt:
(50 ⋅ 53) mod 3 ≡ (2 ⋅ 2) mod 3 ≡ 4 mod 3 ≡ 1 mod 3.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 70916 mod 881.
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. 709 -> x
2. mod(x²,881) -> 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: 7091=709
2: 7092=7091+1=7091⋅7091 ≡ 709⋅709=502681 ≡ 511 mod 881
4: 7094=7092+2=7092⋅7092 ≡ 511⋅511=261121 ≡ 345 mod 881
8: 7098=7094+4=7094⋅7094 ≡ 345⋅345=119025 ≡ 90 mod 881
16: 70916=7098+8=7098⋅7098 ≡ 90⋅90=8100 ≡ 171 mod 881
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 821174 mod 977.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 174 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 174 an und zerlegen 174 in eine Summer von 2er-Potenzen:
174 = 128+32+8+4+2
1: 8211=821
2: 8212=8211+1=8211⋅8211 ≡ 821⋅821=674041 ≡ 888 mod 977
4: 8214=8212+2=8212⋅8212 ≡ 888⋅888=788544 ≡ 105 mod 977
8: 8218=8214+4=8214⋅8214 ≡ 105⋅105=11025 ≡ 278 mod 977
16: 82116=8218+8=8218⋅8218 ≡ 278⋅278=77284 ≡ 101 mod 977
32: 82132=82116+16=82116⋅82116 ≡ 101⋅101=10201 ≡ 431 mod 977
64: 82164=82132+32=82132⋅82132 ≡ 431⋅431=185761 ≡ 131 mod 977
128: 821128=82164+64=82164⋅82164 ≡ 131⋅131=17161 ≡ 552 mod 977
821174
= 821128+32+8+4+2
= 821128⋅82132⋅8218⋅8214⋅8212
≡ 552 ⋅ 431 ⋅ 278 ⋅ 105 ⋅ 888 mod 977
≡ 237912 ⋅ 278 ⋅ 105 ⋅ 888 mod 977 ≡ 501 ⋅ 278 ⋅ 105 ⋅ 888 mod 977
≡ 139278 ⋅ 105 ⋅ 888 mod 977 ≡ 544 ⋅ 105 ⋅ 888 mod 977
≡ 57120 ⋅ 888 mod 977 ≡ 454 ⋅ 888 mod 977
≡ 403152 mod 977 ≡ 628 mod 977
Es gilt also: 821174 ≡ 628 mod 977
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 32.
Also bestimme x, so dass 32 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 32
| =>67 | = 2⋅32 + 3 |
| =>32 | = 10⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(67,32)=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= 3-1⋅2 | |||
| 2= 32-10⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(32 -10⋅ 3)
= 1⋅3 -1⋅32 +10⋅ 3) = -1⋅32 +11⋅ 3 (=1) |
| 3= 67-2⋅32 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅32 +11⋅(67 -2⋅ 32)
= -1⋅32 +11⋅67 -22⋅ 32) = 11⋅67 -23⋅ 32 (=1) |
Es gilt also: ggt(67,32)=1 = 11⋅67 -23⋅32
oder wenn man 11⋅67 auf die linke Seite bringt:
1 -11⋅67 = -23⋅32
-23⋅32 = -11⋅67 + 1 |+67⋅32
-23⋅32 + 67⋅32 = -11⋅67 + 67⋅32 + 1
(-23 + 67) ⋅ 32 = (-11 + 32) ⋅ 67 + 1
44⋅32 = 21⋅67 + 1
Es gilt also: 44⋅32 = 21⋅67 +1
Somit 44⋅32 = 1 mod 67
44 ist also das Inverse von 32 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 37 und q = 41. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
