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: (246 + 24002) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(246 + 24002) mod 8 ≡ (246 mod 8 + 24002 mod 8) mod 8.
246 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 246
= 240
24002 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 24002
= 24000
Somit gilt:
(246 + 24002) mod 8 ≡ (6 + 2) mod 8 ≡ 8 mod 8 ≡ 0 mod 8.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (33 ⋅ 46) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(33 ⋅ 46) mod 8 ≡ (33 mod 8 ⋅ 46 mod 8) mod 8.
33 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 33 = 32 + 1 = 4 ⋅ 8 + 1 ist.
46 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 46 = 40 + 6 = 5 ⋅ 8 + 6 ist.
Somit gilt:
(33 ⋅ 46) mod 8 ≡ (1 ⋅ 6) mod 8 ≡ 6 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 2138 mod 277.
Die 8 im Exponent ist ja ein reine 2er-Potenz (23).
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. 213 -> x
2. mod(x²,277) -> 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: 2131=213
2: 2132=2131+1=2131⋅2131 ≡ 213⋅213=45369 ≡ 218 mod 277
4: 2134=2132+2=2132⋅2132 ≡ 218⋅218=47524 ≡ 157 mod 277
8: 2138=2134+4=2134⋅2134 ≡ 157⋅157=24649 ≡ 273 mod 277
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 66877 mod 739.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 77 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 77 an und zerlegen 77 in eine Summer von 2er-Potenzen:
77 = 64+8+4+1
1: 6681=668
2: 6682=6681+1=6681⋅6681 ≡ 668⋅668=446224 ≡ 607 mod 739
4: 6684=6682+2=6682⋅6682 ≡ 607⋅607=368449 ≡ 427 mod 739
8: 6688=6684+4=6684⋅6684 ≡ 427⋅427=182329 ≡ 535 mod 739
16: 66816=6688+8=6688⋅6688 ≡ 535⋅535=286225 ≡ 232 mod 739
32: 66832=66816+16=66816⋅66816 ≡ 232⋅232=53824 ≡ 616 mod 739
64: 66864=66832+32=66832⋅66832 ≡ 616⋅616=379456 ≡ 349 mod 739
66877
= 66864+8+4+1
= 66864⋅6688⋅6684⋅6681
≡ 349 ⋅ 535 ⋅ 427 ⋅ 668 mod 739
≡ 186715 ⋅ 427 ⋅ 668 mod 739 ≡ 487 ⋅ 427 ⋅ 668 mod 739
≡ 207949 ⋅ 668 mod 739 ≡ 290 ⋅ 668 mod 739
≡ 193720 mod 739 ≡ 102 mod 739
Es gilt also: 66877 ≡ 102 mod 739
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 31.
Also bestimme x, so dass 31 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 31
| =>97 | = 3⋅31 + 4 |
| =>31 | = 7⋅4 + 3 |
| =>4 | = 1⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(97,31)=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= 4-1⋅3 | |||
| 3= 31-7⋅4 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅4 -1⋅(31 -7⋅ 4)
= 1⋅4 -1⋅31 +7⋅ 4) = -1⋅31 +8⋅ 4 (=1) |
| 4= 97-3⋅31 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅31 +8⋅(97 -3⋅ 31)
= -1⋅31 +8⋅97 -24⋅ 31) = 8⋅97 -25⋅ 31 (=1) |
Es gilt also: ggt(97,31)=1 = 8⋅97 -25⋅31
oder wenn man 8⋅97 auf die linke Seite bringt:
1 -8⋅97 = -25⋅31
-25⋅31 = -8⋅97 + 1 |+97⋅31
-25⋅31 + 97⋅31 = -8⋅97 + 97⋅31 + 1
(-25 + 97) ⋅ 31 = (-8 + 31) ⋅ 97 + 1
72⋅31 = 23⋅97 + 1
Es gilt also: 72⋅31 = 23⋅97 +1
Somit 72⋅31 = 1 mod 97
72 ist also das Inverse von 31 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 73 und q = 67. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
