Klasse 5-6
Klasse 7-8
Klasse 9-10
Kursstufe
cosh
nach Aufgabentypen suchen
Aufgabentypen anhand von Beispielen durchstöbern
Browserfenster aktualisieren (F5), um neue Beispiele bei den Aufgabentypen zu sehen
Modulo addieren
Beispiel:
Berechne ohne WTR: (2097 - 1399) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2097 - 1399) mod 7 ≡ (2097 mod 7 - 1399 mod 7) mod 7.
2097 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 2097
= 2100
1399 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 1399
= 1400
Somit gilt:
(2097 - 1399) mod 7 ≡ (4 - 6) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (47 ⋅ 51) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(47 ⋅ 51) mod 9 ≡ (47 mod 9 ⋅ 51 mod 9) mod 9.
47 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 47 = 45 + 2 = 5 ⋅ 9 + 2 ist.
51 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 51 = 45 + 6 = 5 ⋅ 9 + 6 ist.
Somit gilt:
(47 ⋅ 51) mod 9 ≡ (2 ⋅ 6) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 422128 mod 659.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 422 -> x
2. mod(x²,659) -> 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: 4221=422
2: 4222=4221+1=4221⋅4221 ≡ 422⋅422=178084 ≡ 154 mod 659
4: 4224=4222+2=4222⋅4222 ≡ 154⋅154=23716 ≡ 651 mod 659
8: 4228=4224+4=4224⋅4224 ≡ 651⋅651=423801 ≡ 64 mod 659
16: 42216=4228+8=4228⋅4228 ≡ 64⋅64=4096 ≡ 142 mod 659
32: 42232=42216+16=42216⋅42216 ≡ 142⋅142=20164 ≡ 394 mod 659
64: 42264=42232+32=42232⋅42232 ≡ 394⋅394=155236 ≡ 371 mod 659
128: 422128=42264+64=42264⋅42264 ≡ 371⋅371=137641 ≡ 569 mod 659
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 470246 mod 661.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 246 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 246 an und zerlegen 246 in eine Summer von 2er-Potenzen:
246 = 128+64+32+16+4+2
1: 4701=470
2: 4702=4701+1=4701⋅4701 ≡ 470⋅470=220900 ≡ 126 mod 661
4: 4704=4702+2=4702⋅4702 ≡ 126⋅126=15876 ≡ 12 mod 661
8: 4708=4704+4=4704⋅4704 ≡ 12⋅12=144 ≡ 144 mod 661
16: 47016=4708+8=4708⋅4708 ≡ 144⋅144=20736 ≡ 245 mod 661
32: 47032=47016+16=47016⋅47016 ≡ 245⋅245=60025 ≡ 535 mod 661
64: 47064=47032+32=47032⋅47032 ≡ 535⋅535=286225 ≡ 12 mod 661
128: 470128=47064+64=47064⋅47064 ≡ 12⋅12=144 ≡ 144 mod 661
470246
= 470128+64+32+16+4+2
= 470128⋅47064⋅47032⋅47016⋅4704⋅4702
≡ 144 ⋅ 12 ⋅ 535 ⋅ 245 ⋅ 12 ⋅ 126 mod 661
≡ 1728 ⋅ 535 ⋅ 245 ⋅ 12 ⋅ 126 mod 661 ≡ 406 ⋅ 535 ⋅ 245 ⋅ 12 ⋅ 126 mod 661
≡ 217210 ⋅ 245 ⋅ 12 ⋅ 126 mod 661 ≡ 402 ⋅ 245 ⋅ 12 ⋅ 126 mod 661
≡ 98490 ⋅ 12 ⋅ 126 mod 661 ≡ 1 ⋅ 12 ⋅ 126 mod 661
≡ 12 ⋅ 126 mod 661
≡ 1512 mod 661 ≡ 190 mod 661
Es gilt also: 470246 ≡ 190 mod 661
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-79-Inverse zur Zahl 60.
Also bestimme x, so dass 60 ⋅ x ≡ 1 mod 79 gilt:
Berechnung des größten gemeinsamen Teilers von 79 und 60
| =>79 | = 1⋅60 + 19 |
| =>60 | = 3⋅19 + 3 |
| =>19 | = 6⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(79,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= 19-6⋅3 | |||
| 3= 60-3⋅19 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅19 -6⋅(60 -3⋅ 19)
= 1⋅19 -6⋅60 +18⋅ 19) = -6⋅60 +19⋅ 19 (=1) |
| 19= 79-1⋅60 | eingesetzt in die Zeile drüber: | 1 |
= -6⋅60 +19⋅(79 -1⋅ 60)
= -6⋅60 +19⋅79 -19⋅ 60) = 19⋅79 -25⋅ 60 (=1) |
Es gilt also: ggt(79,60)=1 = 19⋅79 -25⋅60
oder wenn man 19⋅79 auf die linke Seite bringt:
1 -19⋅79 = -25⋅60
-25⋅60 = -19⋅79 + 1 |+79⋅60
-25⋅60 + 79⋅60 = -19⋅79 + 79⋅60 + 1
(-25 + 79) ⋅ 60 = (-19 + 60) ⋅ 79 + 1
54⋅60 = 41⋅79 + 1
Es gilt also: 54⋅60 = 41⋅79 +1
Somit 54⋅60 = 1 mod 79
54 ist also das Inverse von 60 mod 79
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
