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: (1201 + 1600) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1201 + 1600) mod 4 ≡ (1201 mod 4 + 1600 mod 4) mod 4.
1201 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 1201
= 1200
1600 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1600
= 1600
Somit gilt:
(1201 + 1600) mod 4 ≡ (1 + 0) mod 4 ≡ 1 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (91 ⋅ 16) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(91 ⋅ 16) mod 7 ≡ (91 mod 7 ⋅ 16 mod 7) mod 7.
91 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 91 = 91 + 0 = 13 ⋅ 7 + 0 ist.
16 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 16 = 14 + 2 = 2 ⋅ 7 + 2 ist.
Somit gilt:
(91 ⋅ 16) mod 7 ≡ (0 ⋅ 2) mod 7 ≡ 0 mod 7.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 32116 mod 431.
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. 321 -> x
2. mod(x²,431) -> 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: 3211=321
2: 3212=3211+1=3211⋅3211 ≡ 321⋅321=103041 ≡ 32 mod 431
4: 3214=3212+2=3212⋅3212 ≡ 32⋅32=1024 ≡ 162 mod 431
8: 3218=3214+4=3214⋅3214 ≡ 162⋅162=26244 ≡ 384 mod 431
16: 32116=3218+8=3218⋅3218 ≡ 384⋅384=147456 ≡ 54 mod 431
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 778222 mod 941.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 222 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 222 an und zerlegen 222 in eine Summer von 2er-Potenzen:
222 = 128+64+16+8+4+2
1: 7781=778
2: 7782=7781+1=7781⋅7781 ≡ 778⋅778=605284 ≡ 221 mod 941
4: 7784=7782+2=7782⋅7782 ≡ 221⋅221=48841 ≡ 850 mod 941
8: 7788=7784+4=7784⋅7784 ≡ 850⋅850=722500 ≡ 753 mod 941
16: 77816=7788+8=7788⋅7788 ≡ 753⋅753=567009 ≡ 527 mod 941
32: 77832=77816+16=77816⋅77816 ≡ 527⋅527=277729 ≡ 134 mod 941
64: 77864=77832+32=77832⋅77832 ≡ 134⋅134=17956 ≡ 77 mod 941
128: 778128=77864+64=77864⋅77864 ≡ 77⋅77=5929 ≡ 283 mod 941
778222
= 778128+64+16+8+4+2
= 778128⋅77864⋅77816⋅7788⋅7784⋅7782
≡ 283 ⋅ 77 ⋅ 527 ⋅ 753 ⋅ 850 ⋅ 221 mod 941
≡ 21791 ⋅ 527 ⋅ 753 ⋅ 850 ⋅ 221 mod 941 ≡ 148 ⋅ 527 ⋅ 753 ⋅ 850 ⋅ 221 mod 941
≡ 77996 ⋅ 753 ⋅ 850 ⋅ 221 mod 941 ≡ 834 ⋅ 753 ⋅ 850 ⋅ 221 mod 941
≡ 628002 ⋅ 850 ⋅ 221 mod 941 ≡ 355 ⋅ 850 ⋅ 221 mod 941
≡ 301750 ⋅ 221 mod 941 ≡ 630 ⋅ 221 mod 941
≡ 139230 mod 941 ≡ 903 mod 941
Es gilt also: 778222 ≡ 903 mod 941
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 56.
Also bestimme x, so dass 56 ⋅ x ≡ 1 mod 101 gilt:
Berechnung des größten gemeinsamen Teilers von 101 und 56
| =>101 | = 1⋅56 + 45 |
| =>56 | = 1⋅45 + 11 |
| =>45 | = 4⋅11 + 1 |
| =>11 | = 11⋅1 + 0 |
also gilt: ggt(101,56)=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= 45-4⋅11 | |||
| 11= 56-1⋅45 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅45 -4⋅(56 -1⋅ 45)
= 1⋅45 -4⋅56 +4⋅ 45) = -4⋅56 +5⋅ 45 (=1) |
| 45= 101-1⋅56 | eingesetzt in die Zeile drüber: | 1 |
= -4⋅56 +5⋅(101 -1⋅ 56)
= -4⋅56 +5⋅101 -5⋅ 56) = 5⋅101 -9⋅ 56 (=1) |
Es gilt also: ggt(101,56)=1 = 5⋅101 -9⋅56
oder wenn man 5⋅101 auf die linke Seite bringt:
1 -5⋅101 = -9⋅56
-9⋅56 = -5⋅101 + 1 |+101⋅56
-9⋅56 + 101⋅56 = -5⋅101 + 101⋅56 + 1
(-9 + 101) ⋅ 56 = (-5 + 56) ⋅ 101 + 1
92⋅56 = 51⋅101 + 1
Es gilt also: 92⋅56 = 51⋅101 +1
Somit 92⋅56 = 1 mod 101
92 ist also das Inverse von 56 mod 101
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 61 und q = 101. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
