Klasse 5 (G9)
Klasse 6 (G9)
Klasse 7 (G9)
Klasse 8 (G8)
Klasse 9-10 (G8)
Kursstufe (G8)
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: (1500 - 2503) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1500 - 2503) mod 5 ≡ (1500 mod 5 - 2503 mod 5) mod 5.
1500 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1500
= 1500
2503 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2503
= 2500
Somit gilt:
(1500 - 2503) mod 5 ≡ (0 - 3) mod 5 ≡ -3 mod 5 ≡ 2 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (34 ⋅ 18) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(34 ⋅ 18) mod 3 ≡ (34 mod 3 ⋅ 18 mod 3) mod 3.
34 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 34 = 33 + 1 = 11 ⋅ 3 + 1 ist.
18 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 18 = 18 + 0 = 6 ⋅ 3 + 0 ist.
Somit gilt:
(34 ⋅ 18) mod 3 ≡ (1 ⋅ 0) mod 3 ≡ 0 mod 3.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 679128 mod 823.
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. 679 -> x
2. mod(x²,823) -> 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: 6791=679
2: 6792=6791+1=6791⋅6791 ≡ 679⋅679=461041 ≡ 161 mod 823
4: 6794=6792+2=6792⋅6792 ≡ 161⋅161=25921 ≡ 408 mod 823
8: 6798=6794+4=6794⋅6794 ≡ 408⋅408=166464 ≡ 218 mod 823
16: 67916=6798+8=6798⋅6798 ≡ 218⋅218=47524 ≡ 613 mod 823
32: 67932=67916+16=67916⋅67916 ≡ 613⋅613=375769 ≡ 481 mod 823
64: 67964=67932+32=67932⋅67932 ≡ 481⋅481=231361 ≡ 98 mod 823
128: 679128=67964+64=67964⋅67964 ≡ 98⋅98=9604 ≡ 551 mod 823
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 854231 mod 929.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 231 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 231 an und zerlegen 231 in eine Summer von 2er-Potenzen:
231 = 128+64+32+4+2+1
1: 8541=854
2: 8542=8541+1=8541⋅8541 ≡ 854⋅854=729316 ≡ 51 mod 929
4: 8544=8542+2=8542⋅8542 ≡ 51⋅51=2601 ≡ 743 mod 929
8: 8548=8544+4=8544⋅8544 ≡ 743⋅743=552049 ≡ 223 mod 929
16: 85416=8548+8=8548⋅8548 ≡ 223⋅223=49729 ≡ 492 mod 929
32: 85432=85416+16=85416⋅85416 ≡ 492⋅492=242064 ≡ 524 mod 929
64: 85464=85432+32=85432⋅85432 ≡ 524⋅524=274576 ≡ 521 mod 929
128: 854128=85464+64=85464⋅85464 ≡ 521⋅521=271441 ≡ 173 mod 929
854231
= 854128+64+32+4+2+1
= 854128⋅85464⋅85432⋅8544⋅8542⋅8541
≡ 173 ⋅ 521 ⋅ 524 ⋅ 743 ⋅ 51 ⋅ 854 mod 929
≡ 90133 ⋅ 524 ⋅ 743 ⋅ 51 ⋅ 854 mod 929 ≡ 20 ⋅ 524 ⋅ 743 ⋅ 51 ⋅ 854 mod 929
≡ 10480 ⋅ 743 ⋅ 51 ⋅ 854 mod 929 ≡ 261 ⋅ 743 ⋅ 51 ⋅ 854 mod 929
≡ 193923 ⋅ 51 ⋅ 854 mod 929 ≡ 691 ⋅ 51 ⋅ 854 mod 929
≡ 35241 ⋅ 854 mod 929 ≡ 868 ⋅ 854 mod 929
≡ 741272 mod 929 ≡ 859 mod 929
Es gilt also: 854231 ≡ 859 mod 929
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 32.
Also bestimme x, so dass 32 ⋅ x ≡ 1 mod 73 gilt:
Berechnung des größten gemeinsamen Teilers von 73 und 32
| =>73 | = 2⋅32 + 9 |
| =>32 | = 3⋅9 + 5 |
| =>9 | = 1⋅5 + 4 |
| =>5 | = 1⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(73,32)=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= 5-1⋅4 | |||
| 4= 9-1⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -1⋅(9 -1⋅ 5)
= 1⋅5 -1⋅9 +1⋅ 5) = -1⋅9 +2⋅ 5 (=1) |
| 5= 32-3⋅9 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅9 +2⋅(32 -3⋅ 9)
= -1⋅9 +2⋅32 -6⋅ 9) = 2⋅32 -7⋅ 9 (=1) |
| 9= 73-2⋅32 | eingesetzt in die Zeile drüber: | 1 |
= 2⋅32 -7⋅(73 -2⋅ 32)
= 2⋅32 -7⋅73 +14⋅ 32) = -7⋅73 +16⋅ 32 (=1) |
Es gilt also: ggt(73,32)=1 = -7⋅73 +16⋅32
oder wenn man -7⋅73 auf die linke Seite bringt:
1 +7⋅73 = +16⋅32
Es gilt also: 16⋅32 = 7⋅73 +1
Somit 16⋅32 = 1 mod 73
16 ist also das Inverse von 32 mod 73
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 37. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
