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: (139 - 27994) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(139 - 27994) mod 7 ≡ (139 mod 7 - 27994 mod 7) mod 7.
139 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 139
= 140
27994 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 27994
= 28000
Somit gilt:
(139 - 27994) mod 7 ≡ (6 - 1) mod 7 ≡ 5 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (99 ⋅ 85) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(99 ⋅ 85) mod 4 ≡ (99 mod 4 ⋅ 85 mod 4) mod 4.
99 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 99 = 96 + 3 = 24 ⋅ 4 + 3 ist.
85 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 21 ⋅ 4 + 1 ist.
Somit gilt:
(99 ⋅ 85) mod 4 ≡ (3 ⋅ 1) mod 4 ≡ 3 mod 4.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 29316 mod 337.
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. 293 -> x
2. mod(x²,337) -> 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: 2931=293
2: 2932=2931+1=2931⋅2931 ≡ 293⋅293=85849 ≡ 251 mod 337
4: 2934=2932+2=2932⋅2932 ≡ 251⋅251=63001 ≡ 319 mod 337
8: 2938=2934+4=2934⋅2934 ≡ 319⋅319=101761 ≡ 324 mod 337
16: 29316=2938+8=2938⋅2938 ≡ 324⋅324=104976 ≡ 169 mod 337
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 696240 mod 997.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 240 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 240 an und zerlegen 240 in eine Summer von 2er-Potenzen:
240 = 128+64+32+16
1: 6961=696
2: 6962=6961+1=6961⋅6961 ≡ 696⋅696=484416 ≡ 871 mod 997
4: 6964=6962+2=6962⋅6962 ≡ 871⋅871=758641 ≡ 921 mod 997
8: 6968=6964+4=6964⋅6964 ≡ 921⋅921=848241 ≡ 791 mod 997
16: 69616=6968+8=6968⋅6968 ≡ 791⋅791=625681 ≡ 562 mod 997
32: 69632=69616+16=69616⋅69616 ≡ 562⋅562=315844 ≡ 792 mod 997
64: 69664=69632+32=69632⋅69632 ≡ 792⋅792=627264 ≡ 151 mod 997
128: 696128=69664+64=69664⋅69664 ≡ 151⋅151=22801 ≡ 867 mod 997
696240
= 696128+64+32+16
= 696128⋅69664⋅69632⋅69616
≡ 867 ⋅ 151 ⋅ 792 ⋅ 562 mod 997
≡ 130917 ⋅ 792 ⋅ 562 mod 997 ≡ 310 ⋅ 792 ⋅ 562 mod 997
≡ 245520 ⋅ 562 mod 997 ≡ 258 ⋅ 562 mod 997
≡ 144996 mod 997 ≡ 431 mod 997
Es gilt also: 696240 ≡ 431 mod 997
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 55.
Also bestimme x, so dass 55 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 55
| =>83 | = 1⋅55 + 28 |
| =>55 | = 1⋅28 + 27 |
| =>28 | = 1⋅27 + 1 |
| =>27 | = 27⋅1 + 0 |
also gilt: ggt(83,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= 28-1⋅27 | |||
| 27= 55-1⋅28 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅28 -1⋅(55 -1⋅ 28)
= 1⋅28 -1⋅55 +1⋅ 28) = -1⋅55 +2⋅ 28 (=1) |
| 28= 83-1⋅55 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅55 +2⋅(83 -1⋅ 55)
= -1⋅55 +2⋅83 -2⋅ 55) = 2⋅83 -3⋅ 55 (=1) |
Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55
oder wenn man 2⋅83 auf die linke Seite bringt:
1 -2⋅83 = -3⋅55
-3⋅55 = -2⋅83 + 1 |+83⋅55
-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1
(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1
80⋅55 = 53⋅83 + 1
Es gilt also: 80⋅55 = 53⋅83 +1
Somit 80⋅55 = 1 mod 83
80 ist also das Inverse von 55 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 31 und q = 71. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
