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: (595 - 597) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(595 - 597) mod 6 ≡ (595 mod 6 - 597 mod 6) mod 6.
595 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 595
= 600
597 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 597
= 600
Somit gilt:
(595 - 597) mod 6 ≡ (1 - 3) mod 6 ≡ -2 mod 6 ≡ 4 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (98 ⋅ 50) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(98 ⋅ 50) mod 9 ≡ (98 mod 9 ⋅ 50 mod 9) mod 9.
98 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 98 = 90 + 8 = 10 ⋅ 9 + 8 ist.
50 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 50 = 45 + 5 = 5 ⋅ 9 + 5 ist.
Somit gilt:
(98 ⋅ 50) mod 9 ≡ (8 ⋅ 5) mod 9 ≡ 40 mod 9 ≡ 4 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 17764 mod 503.
Die 64 im Exponent ist ja ein reine 2er-Potenz (26).
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. 177 -> x
2. mod(x²,503) -> 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: 1771=177
2: 1772=1771+1=1771⋅1771 ≡ 177⋅177=31329 ≡ 143 mod 503
4: 1774=1772+2=1772⋅1772 ≡ 143⋅143=20449 ≡ 329 mod 503
8: 1778=1774+4=1774⋅1774 ≡ 329⋅329=108241 ≡ 96 mod 503
16: 17716=1778+8=1778⋅1778 ≡ 96⋅96=9216 ≡ 162 mod 503
32: 17732=17716+16=17716⋅17716 ≡ 162⋅162=26244 ≡ 88 mod 503
64: 17764=17732+32=17732⋅17732 ≡ 88⋅88=7744 ≡ 199 mod 503
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 544125 mod 797.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 125 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 125 an und zerlegen 125 in eine Summer von 2er-Potenzen:
125 = 64+32+16+8+4+1
1: 5441=544
2: 5442=5441+1=5441⋅5441 ≡ 544⋅544=295936 ≡ 249 mod 797
4: 5444=5442+2=5442⋅5442 ≡ 249⋅249=62001 ≡ 632 mod 797
8: 5448=5444+4=5444⋅5444 ≡ 632⋅632=399424 ≡ 127 mod 797
16: 54416=5448+8=5448⋅5448 ≡ 127⋅127=16129 ≡ 189 mod 797
32: 54432=54416+16=54416⋅54416 ≡ 189⋅189=35721 ≡ 653 mod 797
64: 54464=54432+32=54432⋅54432 ≡ 653⋅653=426409 ≡ 14 mod 797
544125
= 54464+32+16+8+4+1
= 54464⋅54432⋅54416⋅5448⋅5444⋅5441
≡ 14 ⋅ 653 ⋅ 189 ⋅ 127 ⋅ 632 ⋅ 544 mod 797
≡ 9142 ⋅ 189 ⋅ 127 ⋅ 632 ⋅ 544 mod 797 ≡ 375 ⋅ 189 ⋅ 127 ⋅ 632 ⋅ 544 mod 797
≡ 70875 ⋅ 127 ⋅ 632 ⋅ 544 mod 797 ≡ 739 ⋅ 127 ⋅ 632 ⋅ 544 mod 797
≡ 93853 ⋅ 632 ⋅ 544 mod 797 ≡ 604 ⋅ 632 ⋅ 544 mod 797
≡ 381728 ⋅ 544 mod 797 ≡ 762 ⋅ 544 mod 797
≡ 414528 mod 797 ≡ 88 mod 797
Es gilt also: 544125 ≡ 88 mod 797
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 37.
Also bestimme x, so dass 37 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 37
| =>71 | = 1⋅37 + 34 |
| =>37 | = 1⋅34 + 3 |
| =>34 | = 11⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(71,37)=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= 34-11⋅3 | |||
| 3= 37-1⋅34 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅34 -11⋅(37 -1⋅ 34)
= 1⋅34 -11⋅37 +11⋅ 34) = -11⋅37 +12⋅ 34 (=1) |
| 34= 71-1⋅37 | eingesetzt in die Zeile drüber: | 1 |
= -11⋅37 +12⋅(71 -1⋅ 37)
= -11⋅37 +12⋅71 -12⋅ 37) = 12⋅71 -23⋅ 37 (=1) |
Es gilt also: ggt(71,37)=1 = 12⋅71 -23⋅37
oder wenn man 12⋅71 auf die linke Seite bringt:
1 -12⋅71 = -23⋅37
-23⋅37 = -12⋅71 + 1 |+71⋅37
-23⋅37 + 71⋅37 = -12⋅71 + 71⋅37 + 1
(-23 + 71) ⋅ 37 = (-12 + 37) ⋅ 71 + 1
48⋅37 = 25⋅71 + 1
Es gilt also: 48⋅37 = 25⋅71 +1
Somit 48⋅37 = 1 mod 71
48 ist also das Inverse von 37 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 43 und q = 53. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
