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: (2497 + 247) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2497 + 247) mod 5 ≡ (2497 mod 5 + 247 mod 5) mod 5.
2497 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 2497
= 2400
247 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 247
= 240
Somit gilt:
(2497 + 247) mod 5 ≡ (2 + 2) mod 5 ≡ 4 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (57 ⋅ 15) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(57 ⋅ 15) mod 8 ≡ (57 mod 8 ⋅ 15 mod 8) mod 8.
57 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 57 = 56 + 1 = 7 ⋅ 8 + 1 ist.
15 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 15 = 8 + 7 = 1 ⋅ 8 + 7 ist.
Somit gilt:
(57 ⋅ 15) mod 8 ≡ (1 ⋅ 7) mod 8 ≡ 7 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 40764 mod 487.
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. 407 -> x
2. mod(x²,487) -> 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: 4071=407
2: 4072=4071+1=4071⋅4071 ≡ 407⋅407=165649 ≡ 69 mod 487
4: 4074=4072+2=4072⋅4072 ≡ 69⋅69=4761 ≡ 378 mod 487
8: 4078=4074+4=4074⋅4074 ≡ 378⋅378=142884 ≡ 193 mod 487
16: 40716=4078+8=4078⋅4078 ≡ 193⋅193=37249 ≡ 237 mod 487
32: 40732=40716+16=40716⋅40716 ≡ 237⋅237=56169 ≡ 164 mod 487
64: 40764=40732+32=40732⋅40732 ≡ 164⋅164=26896 ≡ 111 mod 487
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 457180 mod 463.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 180 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 180 an und zerlegen 180 in eine Summer von 2er-Potenzen:
180 = 128+32+16+4
1: 4571=457
2: 4572=4571+1=4571⋅4571 ≡ 457⋅457=208849 ≡ 36 mod 463
4: 4574=4572+2=4572⋅4572 ≡ 36⋅36=1296 ≡ 370 mod 463
8: 4578=4574+4=4574⋅4574 ≡ 370⋅370=136900 ≡ 315 mod 463
16: 45716=4578+8=4578⋅4578 ≡ 315⋅315=99225 ≡ 143 mod 463
32: 45732=45716+16=45716⋅45716 ≡ 143⋅143=20449 ≡ 77 mod 463
64: 45764=45732+32=45732⋅45732 ≡ 77⋅77=5929 ≡ 373 mod 463
128: 457128=45764+64=45764⋅45764 ≡ 373⋅373=139129 ≡ 229 mod 463
457180
= 457128+32+16+4
= 457128⋅45732⋅45716⋅4574
≡ 229 ⋅ 77 ⋅ 143 ⋅ 370 mod 463
≡ 17633 ⋅ 143 ⋅ 370 mod 463 ≡ 39 ⋅ 143 ⋅ 370 mod 463
≡ 5577 ⋅ 370 mod 463 ≡ 21 ⋅ 370 mod 463
≡ 7770 mod 463 ≡ 362 mod 463
Es gilt also: 457180 ≡ 362 mod 463
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 59.
Also bestimme x, so dass 59 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 59
| =>71 | = 1⋅59 + 12 |
| =>59 | = 4⋅12 + 11 |
| =>12 | = 1⋅11 + 1 |
| =>11 | = 11⋅1 + 0 |
also gilt: ggt(71,59)=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= 12-1⋅11 | |||
| 11= 59-4⋅12 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅12 -1⋅(59 -4⋅ 12)
= 1⋅12 -1⋅59 +4⋅ 12) = -1⋅59 +5⋅ 12 (=1) |
| 12= 71-1⋅59 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅59 +5⋅(71 -1⋅ 59)
= -1⋅59 +5⋅71 -5⋅ 59) = 5⋅71 -6⋅ 59 (=1) |
Es gilt also: ggt(71,59)=1 = 5⋅71 -6⋅59
oder wenn man 5⋅71 auf die linke Seite bringt:
1 -5⋅71 = -6⋅59
-6⋅59 = -5⋅71 + 1 |+71⋅59
-6⋅59 + 71⋅59 = -5⋅71 + 71⋅59 + 1
(-6 + 71) ⋅ 59 = (-5 + 59) ⋅ 71 + 1
65⋅59 = 54⋅71 + 1
Es gilt also: 65⋅59 = 54⋅71 +1
Somit 65⋅59 = 1 mod 71
65 ist also das Inverse von 59 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 71. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
