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: (9003 + 1200) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(9003 + 1200) mod 3 ≡ (9003 mod 3 + 1200 mod 3) mod 3.
9003 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 9003
= 9000
1200 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1200
= 1200
Somit gilt:
(9003 + 1200) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (24 ⋅ 78) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(24 ⋅ 78) mod 5 ≡ (24 mod 5 ⋅ 78 mod 5) mod 5.
24 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 24 = 20 + 4 = 4 ⋅ 5 + 4 ist.
78 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 78 = 75 + 3 = 15 ⋅ 5 + 3 ist.
Somit gilt:
(24 ⋅ 78) mod 5 ≡ (4 ⋅ 3) mod 5 ≡ 12 mod 5 ≡ 2 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 27416 mod 643.
Die 16 im Exponent ist ja ein reine 2er-Potenz (24).
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. 274 -> x
2. mod(x²,643) -> 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: 2741=274
2: 2742=2741+1=2741⋅2741 ≡ 274⋅274=75076 ≡ 488 mod 643
4: 2744=2742+2=2742⋅2742 ≡ 488⋅488=238144 ≡ 234 mod 643
8: 2748=2744+4=2744⋅2744 ≡ 234⋅234=54756 ≡ 101 mod 643
16: 27416=2748+8=2748⋅2748 ≡ 101⋅101=10201 ≡ 556 mod 643
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 215216 mod 229.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 216 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 216 an und zerlegen 216 in eine Summer von 2er-Potenzen:
216 = 128+64+16+8
1: 2151=215
2: 2152=2151+1=2151⋅2151 ≡ 215⋅215=46225 ≡ 196 mod 229
4: 2154=2152+2=2152⋅2152 ≡ 196⋅196=38416 ≡ 173 mod 229
8: 2158=2154+4=2154⋅2154 ≡ 173⋅173=29929 ≡ 159 mod 229
16: 21516=2158+8=2158⋅2158 ≡ 159⋅159=25281 ≡ 91 mod 229
32: 21532=21516+16=21516⋅21516 ≡ 91⋅91=8281 ≡ 37 mod 229
64: 21564=21532+32=21532⋅21532 ≡ 37⋅37=1369 ≡ 224 mod 229
128: 215128=21564+64=21564⋅21564 ≡ 224⋅224=50176 ≡ 25 mod 229
215216
= 215128+64+16+8
= 215128⋅21564⋅21516⋅2158
≡ 25 ⋅ 224 ⋅ 91 ⋅ 159 mod 229
≡ 5600 ⋅ 91 ⋅ 159 mod 229 ≡ 104 ⋅ 91 ⋅ 159 mod 229
≡ 9464 ⋅ 159 mod 229 ≡ 75 ⋅ 159 mod 229
≡ 11925 mod 229 ≡ 17 mod 229
Es gilt also: 215216 ≡ 17 mod 229
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 33.
Also bestimme x, so dass 33 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 33
| =>97 | = 2⋅33 + 31 |
| =>33 | = 1⋅31 + 2 |
| =>31 | = 15⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(97,33)=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= 31-15⋅2 | |||
| 2= 33-1⋅31 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅31 -15⋅(33 -1⋅ 31)
= 1⋅31 -15⋅33 +15⋅ 31) = -15⋅33 +16⋅ 31 (=1) |
| 31= 97-2⋅33 | eingesetzt in die Zeile drüber: | 1 |
= -15⋅33 +16⋅(97 -2⋅ 33)
= -15⋅33 +16⋅97 -32⋅ 33) = 16⋅97 -47⋅ 33 (=1) |
Es gilt also: ggt(97,33)=1 = 16⋅97 -47⋅33
oder wenn man 16⋅97 auf die linke Seite bringt:
1 -16⋅97 = -47⋅33
-47⋅33 = -16⋅97 + 1 |+97⋅33
-47⋅33 + 97⋅33 = -16⋅97 + 97⋅33 + 1
(-47 + 97) ⋅ 33 = (-16 + 33) ⋅ 97 + 1
50⋅33 = 17⋅97 + 1
Es gilt also: 50⋅33 = 17⋅97 +1
Somit 50⋅33 = 1 mod 97
50 ist also das Inverse von 33 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 67. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.