Sammelkorb: 
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: (1000 - 2000) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(1000 - 2000) mod 5 ≡ (1000 mod 5 - 2000 mod 5) mod 5.
1000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1000
= 1000
2000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2000
= 2000
Somit gilt:
(1000 - 2000) mod 5 ≡ (0 - 0) mod 5 ≡ 0 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (19 ⋅ 49) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(19 ⋅ 49) mod 9 ≡ (19 mod 9 ⋅ 49 mod 9) mod 9.
19 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 19 = 18 + 1 = 2 ⋅ 9 + 1 ist.
49 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 49 = 45 + 4 = 5 ⋅ 9 + 4 ist.
Somit gilt:
(19 ⋅ 49) mod 9 ≡ (1 ⋅ 4) mod 9 ≡ 4 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 75032 mod 827.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 750 -> 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: 7501=750
2: 7502=7501+1=7501⋅7501 ≡ 750⋅750=562500 ≡ 140 mod 827
4: 7504=7502+2=7502⋅7502 ≡ 140⋅140=19600 ≡ 579 mod 827
8: 7508=7504+4=7504⋅7504 ≡ 579⋅579=335241 ≡ 306 mod 827
16: 75016=7508+8=7508⋅7508 ≡ 306⋅306=93636 ≡ 185 mod 827
32: 75032=75016+16=75016⋅75016 ≡ 185⋅185=34225 ≡ 318 mod 827
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 217105 mod 641.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 105 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 105 an und zerlegen 105 in eine Summer von 2er-Potenzen:
105 = 64+32+8+1
1: 2171=217
2: 2172=2171+1=2171⋅2171 ≡ 217⋅217=47089 ≡ 296 mod 641
4: 2174=2172+2=2172⋅2172 ≡ 296⋅296=87616 ≡ 440 mod 641
8: 2178=2174+4=2174⋅2174 ≡ 440⋅440=193600 ≡ 18 mod 641
16: 21716=2178+8=2178⋅2178 ≡ 18⋅18=324 ≡ 324 mod 641
32: 21732=21716+16=21716⋅21716 ≡ 324⋅324=104976 ≡ 493 mod 641
64: 21764=21732+32=21732⋅21732 ≡ 493⋅493=243049 ≡ 110 mod 641
217105
= 21764+32+8+1
= 21764⋅21732⋅2178⋅2171
≡ 110 ⋅ 493 ⋅ 18 ⋅ 217 mod 641
≡ 54230 ⋅ 18 ⋅ 217 mod 641 ≡ 386 ⋅ 18 ⋅ 217 mod 641
≡ 6948 ⋅ 217 mod 641 ≡ 538 ⋅ 217 mod 641
≡ 116746 mod 641 ≡ 84 mod 641
Es gilt also: 217105 ≡ 84 mod 641
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 57.
Also bestimme x, so dass 57 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 57
| =>83 | = 1⋅57 + 26 |
| =>57 | = 2⋅26 + 5 |
| =>26 | = 5⋅5 + 1 |
| =>5 | = 5⋅1 + 0 |
also gilt: ggt(83,57)=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= 26-5⋅5 | |||
| 5= 57-2⋅26 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅26 -5⋅(57 -2⋅ 26)
= 1⋅26 -5⋅57 +10⋅ 26) = -5⋅57 +11⋅ 26 (=1) |
| 26= 83-1⋅57 | eingesetzt in die Zeile drüber: | 1 |
= -5⋅57 +11⋅(83 -1⋅ 57)
= -5⋅57 +11⋅83 -11⋅ 57) = 11⋅83 -16⋅ 57 (=1) |
Es gilt also: ggt(83,57)=1 = 11⋅83 -16⋅57
oder wenn man 11⋅83 auf die linke Seite bringt:
1 -11⋅83 = -16⋅57
-16⋅57 = -11⋅83 + 1 |+83⋅57
-16⋅57 + 83⋅57 = -11⋅83 + 83⋅57 + 1
(-16 + 83) ⋅ 57 = (-11 + 57) ⋅ 83 + 1
67⋅57 = 46⋅83 + 1
Es gilt also: 67⋅57 = 46⋅83 +1
Somit 67⋅57 = 1 mod 83
67 ist also das Inverse von 57 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 73 und q = 47. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.