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: (804 - 24003) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(804 - 24003) mod 8 ≡ (804 mod 8 - 24003 mod 8) mod 8.
804 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 804
= 800
24003 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 24003
= 24000
Somit gilt:
(804 - 24003) mod 8 ≡ (4 - 3) mod 8 ≡ 1 mod 8.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (97 ⋅ 90) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(97 ⋅ 90) mod 11 ≡ (97 mod 11 ⋅ 90 mod 11) mod 11.
97 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 97 = 88 + 9 = 8 ⋅ 11 + 9 ist.
90 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 90 = 88 + 2 = 8 ⋅ 11 + 2 ist.
Somit gilt:
(97 ⋅ 90) mod 11 ≡ (9 ⋅ 2) mod 11 ≡ 18 mod 11 ≡ 7 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 488128 mod 593.
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. 488 -> x
2. mod(x²,593) -> 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: 4881=488
2: 4882=4881+1=4881⋅4881 ≡ 488⋅488=238144 ≡ 351 mod 593
4: 4884=4882+2=4882⋅4882 ≡ 351⋅351=123201 ≡ 450 mod 593
8: 4888=4884+4=4884⋅4884 ≡ 450⋅450=202500 ≡ 287 mod 593
16: 48816=4888+8=4888⋅4888 ≡ 287⋅287=82369 ≡ 535 mod 593
32: 48832=48816+16=48816⋅48816 ≡ 535⋅535=286225 ≡ 399 mod 593
64: 48864=48832+32=48832⋅48832 ≡ 399⋅399=159201 ≡ 277 mod 593
128: 488128=48864+64=48864⋅48864 ≡ 277⋅277=76729 ≡ 232 mod 593
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 593255 mod 809.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 255 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 255 an und zerlegen 255 in eine Summer von 2er-Potenzen:
255 = 128+64+32+16+8+4+2+1
1: 5931=593
2: 5932=5931+1=5931⋅5931 ≡ 593⋅593=351649 ≡ 543 mod 809
4: 5934=5932+2=5932⋅5932 ≡ 543⋅543=294849 ≡ 373 mod 809
8: 5938=5934+4=5934⋅5934 ≡ 373⋅373=139129 ≡ 790 mod 809
16: 59316=5938+8=5938⋅5938 ≡ 790⋅790=624100 ≡ 361 mod 809
32: 59332=59316+16=59316⋅59316 ≡ 361⋅361=130321 ≡ 72 mod 809
64: 59364=59332+32=59332⋅59332 ≡ 72⋅72=5184 ≡ 330 mod 809
128: 593128=59364+64=59364⋅59364 ≡ 330⋅330=108900 ≡ 494 mod 809
593255
= 593128+64+32+16+8+4+2+1
= 593128⋅59364⋅59332⋅59316⋅5938⋅5934⋅5932⋅5931
≡ 494 ⋅ 330 ⋅ 72 ⋅ 361 ⋅ 790 ⋅ 373 ⋅ 543 ⋅ 593 mod 809
≡ 163020 ⋅ 72 ⋅ 361 ⋅ 790 ⋅ 373 ⋅ 543 ⋅ 593 mod 809 ≡ 411 ⋅ 72 ⋅ 361 ⋅ 790 ⋅ 373 ⋅ 543 ⋅ 593 mod 809
≡ 29592 ⋅ 361 ⋅ 790 ⋅ 373 ⋅ 543 ⋅ 593 mod 809 ≡ 468 ⋅ 361 ⋅ 790 ⋅ 373 ⋅ 543 ⋅ 593 mod 809
≡ 168948 ⋅ 790 ⋅ 373 ⋅ 543 ⋅ 593 mod 809 ≡ 676 ⋅ 790 ⋅ 373 ⋅ 543 ⋅ 593 mod 809
≡ 534040 ⋅ 373 ⋅ 543 ⋅ 593 mod 809 ≡ 100 ⋅ 373 ⋅ 543 ⋅ 593 mod 809
≡ 37300 ⋅ 543 ⋅ 593 mod 809 ≡ 86 ⋅ 543 ⋅ 593 mod 809
≡ 46698 ⋅ 593 mod 809 ≡ 585 ⋅ 593 mod 809
≡ 346905 mod 809 ≡ 653 mod 809
Es gilt also: 593255 ≡ 653 mod 809
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 23.
Also bestimme x, so dass 23 ⋅ x ≡ 1 mod 61 gilt:
Berechnung des größten gemeinsamen Teilers von 61 und 23
| =>61 | = 2⋅23 + 15 |
| =>23 | = 1⋅15 + 8 |
| =>15 | = 1⋅8 + 7 |
| =>8 | = 1⋅7 + 1 |
| =>7 | = 7⋅1 + 0 |
also gilt: ggt(61,23)=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= 8-1⋅7 | |||
| 7= 15-1⋅8 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅8 -1⋅(15 -1⋅ 8)
= 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1) |
| 8= 23-1⋅15 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅15 +2⋅(23 -1⋅ 15)
= -1⋅15 +2⋅23 -2⋅ 15) = 2⋅23 -3⋅ 15 (=1) |
| 15= 61-2⋅23 | eingesetzt in die Zeile drüber: | 1 |
= 2⋅23 -3⋅(61 -2⋅ 23)
= 2⋅23 -3⋅61 +6⋅ 23) = -3⋅61 +8⋅ 23 (=1) |
Es gilt also: ggt(61,23)=1 = -3⋅61 +8⋅23
oder wenn man -3⋅61 auf die linke Seite bringt:
1 +3⋅61 = +8⋅23
Es gilt also: 8⋅23 = 3⋅61 +1
Somit 8⋅23 = 1 mod 61
8 ist also das Inverse von 23 mod 61
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 59 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
