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: (240 + 18004) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(240 + 18004) mod 6 ≡ (240 mod 6 + 18004 mod 6) mod 6.
240 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 240
= 240
18004 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 18004
= 18000
Somit gilt:
(240 + 18004) mod 6 ≡ (0 + 4) mod 6 ≡ 4 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (20 ⋅ 16) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(20 ⋅ 16) mod 3 ≡ (20 mod 3 ⋅ 16 mod 3) mod 3.
20 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 20 = 18 + 2 = 6 ⋅ 3 + 2 ist.
16 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 16 = 15 + 1 = 5 ⋅ 3 + 1 ist.
Somit gilt:
(20 ⋅ 16) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 587128 mod 877.
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. 587 -> x
2. mod(x²,877) -> 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: 5871=587
2: 5872=5871+1=5871⋅5871 ≡ 587⋅587=344569 ≡ 785 mod 877
4: 5874=5872+2=5872⋅5872 ≡ 785⋅785=616225 ≡ 571 mod 877
8: 5878=5874+4=5874⋅5874 ≡ 571⋅571=326041 ≡ 674 mod 877
16: 58716=5878+8=5878⋅5878 ≡ 674⋅674=454276 ≡ 867 mod 877
32: 58732=58716+16=58716⋅58716 ≡ 867⋅867=751689 ≡ 100 mod 877
64: 58764=58732+32=58732⋅58732 ≡ 100⋅100=10000 ≡ 353 mod 877
128: 587128=58764+64=58764⋅58764 ≡ 353⋅353=124609 ≡ 75 mod 877
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 54865 mod 613.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 65 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 65 an und zerlegen 65 in eine Summer von 2er-Potenzen:
65 = 64+1
1: 5481=548
2: 5482=5481+1=5481⋅5481 ≡ 548⋅548=300304 ≡ 547 mod 613
4: 5484=5482+2=5482⋅5482 ≡ 547⋅547=299209 ≡ 65 mod 613
8: 5488=5484+4=5484⋅5484 ≡ 65⋅65=4225 ≡ 547 mod 613
16: 54816=5488+8=5488⋅5488 ≡ 547⋅547=299209 ≡ 65 mod 613
32: 54832=54816+16=54816⋅54816 ≡ 65⋅65=4225 ≡ 547 mod 613
64: 54864=54832+32=54832⋅54832 ≡ 547⋅547=299209 ≡ 65 mod 613
54865
= 54864+1
= 54864⋅5481
≡ 65 ⋅ 548 mod 613
≡ 35620 mod 613 ≡ 66 mod 613
Es gilt also: 54865 ≡ 66 mod 613
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 47.
Also bestimme x, so dass 47 ⋅ x ≡ 1 mod 61 gilt:
Berechnung des größten gemeinsamen Teilers von 61 und 47
| =>61 | = 1⋅47 + 14 |
| =>47 | = 3⋅14 + 5 |
| =>14 | = 2⋅5 + 4 |
| =>5 | = 1⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(61,47)=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= 14-2⋅5 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅5 -1⋅(14 -2⋅ 5)
= 1⋅5 -1⋅14 +2⋅ 5) = -1⋅14 +3⋅ 5 (=1) |
| 5= 47-3⋅14 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅14 +3⋅(47 -3⋅ 14)
= -1⋅14 +3⋅47 -9⋅ 14) = 3⋅47 -10⋅ 14 (=1) |
| 14= 61-1⋅47 | eingesetzt in die Zeile drüber: | 1 |
= 3⋅47 -10⋅(61 -1⋅ 47)
= 3⋅47 -10⋅61 +10⋅ 47) = -10⋅61 +13⋅ 47 (=1) |
Es gilt also: ggt(61,47)=1 = -10⋅61 +13⋅47
oder wenn man -10⋅61 auf die linke Seite bringt:
1 +10⋅61 = +13⋅47
Es gilt also: 13⋅47 = 10⋅61 +1
Somit 13⋅47 = 1 mod 61
13 ist also das Inverse von 47 mod 61
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 73 und q = 53. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.