Klasse 5-6
Klasse 7-8
Klasse 9-10
Kursstufe
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: (2397 - 239) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2397 - 239) mod 6 ≡ (2397 mod 6 - 239 mod 6) mod 6.
2397 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 2397
= 2400
239 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 239
= 240
Somit gilt:
(2397 - 239) mod 6 ≡ (3 - 5) mod 6 ≡ -2 mod 6 ≡ 4 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (88 ⋅ 69) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(88 ⋅ 69) mod 6 ≡ (88 mod 6 ⋅ 69 mod 6) mod 6.
88 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 88 = 84 + 4 = 14 ⋅ 6 + 4 ist.
69 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 69 = 66 + 3 = 11 ⋅ 6 + 3 ist.
Somit gilt:
(88 ⋅ 69) mod 6 ≡ (4 ⋅ 3) mod 6 ≡ 12 mod 6 ≡ 0 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 47464 mod 827.
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. 474 -> x
2. mod(x²,827) -> 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: 4741=474
2: 4742=4741+1=4741⋅4741 ≡ 474⋅474=224676 ≡ 559 mod 827
4: 4744=4742+2=4742⋅4742 ≡ 559⋅559=312481 ≡ 702 mod 827
8: 4748=4744+4=4744⋅4744 ≡ 702⋅702=492804 ≡ 739 mod 827
16: 47416=4748+8=4748⋅4748 ≡ 739⋅739=546121 ≡ 301 mod 827
32: 47432=47416+16=47416⋅47416 ≡ 301⋅301=90601 ≡ 458 mod 827
64: 47464=47432+32=47432⋅47432 ≡ 458⋅458=209764 ≡ 533 mod 827
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 216248 mod 347.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 248 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 248 an und zerlegen 248 in eine Summer von 2er-Potenzen:
248 = 128+64+32+16+8
1: 2161=216
2: 2162=2161+1=2161⋅2161 ≡ 216⋅216=46656 ≡ 158 mod 347
4: 2164=2162+2=2162⋅2162 ≡ 158⋅158=24964 ≡ 327 mod 347
8: 2168=2164+4=2164⋅2164 ≡ 327⋅327=106929 ≡ 53 mod 347
16: 21616=2168+8=2168⋅2168 ≡ 53⋅53=2809 ≡ 33 mod 347
32: 21632=21616+16=21616⋅21616 ≡ 33⋅33=1089 ≡ 48 mod 347
64: 21664=21632+32=21632⋅21632 ≡ 48⋅48=2304 ≡ 222 mod 347
128: 216128=21664+64=21664⋅21664 ≡ 222⋅222=49284 ≡ 10 mod 347
216248
= 216128+64+32+16+8
= 216128⋅21664⋅21632⋅21616⋅2168
≡ 10 ⋅ 222 ⋅ 48 ⋅ 33 ⋅ 53 mod 347
≡ 2220 ⋅ 48 ⋅ 33 ⋅ 53 mod 347 ≡ 138 ⋅ 48 ⋅ 33 ⋅ 53 mod 347
≡ 6624 ⋅ 33 ⋅ 53 mod 347 ≡ 31 ⋅ 33 ⋅ 53 mod 347
≡ 1023 ⋅ 53 mod 347 ≡ 329 ⋅ 53 mod 347
≡ 17437 mod 347 ≡ 87 mod 347
Es gilt also: 216248 ≡ 87 mod 347
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 53.
Also bestimme x, so dass 53 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 53
=>71 | = 1⋅53 + 18 |
=>53 | = 2⋅18 + 17 |
=>18 | = 1⋅17 + 1 |
=>17 | = 17⋅1 + 0 |
also gilt: ggt(71,53)=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= 18-1⋅17 | |||
17= 53-2⋅18 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅18 -1⋅(53 -2⋅ 18)
= 1⋅18 -1⋅53 +2⋅ 18) = -1⋅53 +3⋅ 18 (=1) |
18= 71-1⋅53 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅53 +3⋅(71 -1⋅ 53)
= -1⋅53 +3⋅71 -3⋅ 53) = 3⋅71 -4⋅ 53 (=1) |
Es gilt also: ggt(71,53)=1 = 3⋅71 -4⋅53
oder wenn man 3⋅71 auf die linke Seite bringt:
1 -3⋅71 = -4⋅53
-4⋅53 = -3⋅71 + 1 |+71⋅53
-4⋅53 + 71⋅53 = -3⋅71 + 71⋅53 + 1
(-4 + 71) ⋅ 53 = (-3 + 53) ⋅ 71 + 1
67⋅53 = 50⋅71 + 1
Es gilt also: 67⋅53 = 50⋅71 +1
Somit 67⋅53 = 1 mod 71
67 ist also das Inverse von 53 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 37 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.