- 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: (244 - 3998) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(244 - 3998) mod 8 ≡ (244 mod 8 - 3998 mod 8) mod 8.
244 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 244
= 240
3998 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 3998
= 4000
Somit gilt:
(244 - 3998) mod 8 ≡ (4 - 6) mod 8 ≡ -2 mod 8 ≡ 6 mod 8.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (52 ⋅ 83) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(52 ⋅ 83) mod 11 ≡ (52 mod 11 ⋅ 83 mod 11) mod 11.
52 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 52 = 44 + 8 = 4 ⋅ 11 + 8 ist.
83 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 83 = 77 + 6 = 7 ⋅ 11 + 6 ist.
Somit gilt:
(52 ⋅ 83) mod 11 ≡ (8 ⋅ 6) mod 11 ≡ 48 mod 11 ≡ 4 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 416128 mod 709.
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. 416 -> x
2. mod(x²,709) -> 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: 4161=416
2: 4162=4161+1=4161⋅4161 ≡ 416⋅416=173056 ≡ 60 mod 709
4: 4164=4162+2=4162⋅4162 ≡ 60⋅60=3600 ≡ 55 mod 709
8: 4168=4164+4=4164⋅4164 ≡ 55⋅55=3025 ≡ 189 mod 709
16: 41616=4168+8=4168⋅4168 ≡ 189⋅189=35721 ≡ 271 mod 709
32: 41632=41616+16=41616⋅41616 ≡ 271⋅271=73441 ≡ 414 mod 709
64: 41664=41632+32=41632⋅41632 ≡ 414⋅414=171396 ≡ 527 mod 709
128: 416128=41664+64=41664⋅41664 ≡ 527⋅527=277729 ≡ 510 mod 709
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 251218 mod 823.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 218 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 218 an und zerlegen 218 in eine Summer von 2er-Potenzen:
218 = 128+64+16+8+2
1: 2511=251
2: 2512=2511+1=2511⋅2511 ≡ 251⋅251=63001 ≡ 453 mod 823
4: 2514=2512+2=2512⋅2512 ≡ 453⋅453=205209 ≡ 282 mod 823
8: 2518=2514+4=2514⋅2514 ≡ 282⋅282=79524 ≡ 516 mod 823
16: 25116=2518+8=2518⋅2518 ≡ 516⋅516=266256 ≡ 427 mod 823
32: 25132=25116+16=25116⋅25116 ≡ 427⋅427=182329 ≡ 446 mod 823
64: 25164=25132+32=25132⋅25132 ≡ 446⋅446=198916 ≡ 573 mod 823
128: 251128=25164+64=25164⋅25164 ≡ 573⋅573=328329 ≡ 775 mod 823
251218
= 251128+64+16+8+2
= 251128⋅25164⋅25116⋅2518⋅2512
≡ 775 ⋅ 573 ⋅ 427 ⋅ 516 ⋅ 453 mod 823
≡ 444075 ⋅ 427 ⋅ 516 ⋅ 453 mod 823 ≡ 478 ⋅ 427 ⋅ 516 ⋅ 453 mod 823
≡ 204106 ⋅ 516 ⋅ 453 mod 823 ≡ 2 ⋅ 516 ⋅ 453 mod 823
≡ 1032 ⋅ 453 mod 823 ≡ 209 ⋅ 453 mod 823
≡ 94677 mod 823 ≡ 32 mod 823
Es gilt also: 251218 ≡ 32 mod 823
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-59-Inverse zur Zahl 48.
Also bestimme x, so dass 48 ⋅ x ≡ 1 mod 59 gilt:
Berechnung des größten gemeinsamen Teilers von 59 und 48
=>59 | = 1⋅48 + 11 |
=>48 | = 4⋅11 + 4 |
=>11 | = 2⋅4 + 3 |
=>4 | = 1⋅3 + 1 |
=>3 | = 3⋅1 + 0 |
also gilt: ggt(59,48)=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= 11-2⋅4 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅4 -1⋅(11 -2⋅ 4)
= 1⋅4 -1⋅11 +2⋅ 4) = -1⋅11 +3⋅ 4 (=1) |
4= 48-4⋅11 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅11 +3⋅(48 -4⋅ 11)
= -1⋅11 +3⋅48 -12⋅ 11) = 3⋅48 -13⋅ 11 (=1) |
11= 59-1⋅48 | eingesetzt in die Zeile drüber: | 1 |
= 3⋅48 -13⋅(59 -1⋅ 48)
= 3⋅48 -13⋅59 +13⋅ 48) = -13⋅59 +16⋅ 48 (=1) |
Es gilt also: ggt(59,48)=1 = -13⋅59 +16⋅48
oder wenn man -13⋅59 auf die linke Seite bringt:
1 +13⋅59 = +16⋅48
Es gilt also: 16⋅48 = 13⋅59 +1
Somit 16⋅48 = 1 mod 59
16 ist also das Inverse von 48 mod 59
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 97 und q = 41. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.