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: (35007 - 2100) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(35007 - 2100) mod 7 ≡ (35007 mod 7 - 2100 mod 7) mod 7.
35007 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 35007
= 35000
2100 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 2100
= 2100
Somit gilt:
(35007 - 2100) mod 7 ≡ (0 - 0) mod 7 ≡ 0 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (24 ⋅ 49) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(24 ⋅ 49) mod 3 ≡ (24 mod 3 ⋅ 49 mod 3) mod 3.
24 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 24 = 24 + 0 = 8 ⋅ 3 + 0 ist.
49 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 49 = 48 + 1 = 16 ⋅ 3 + 1 ist.
Somit gilt:
(24 ⋅ 49) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 29516 mod 743.
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. 295 -> x
2. mod(x²,743) -> 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: 2951=295
2: 2952=2951+1=2951⋅2951 ≡ 295⋅295=87025 ≡ 94 mod 743
4: 2954=2952+2=2952⋅2952 ≡ 94⋅94=8836 ≡ 663 mod 743
8: 2958=2954+4=2954⋅2954 ≡ 663⋅663=439569 ≡ 456 mod 743
16: 29516=2958+8=2958⋅2958 ≡ 456⋅456=207936 ≡ 639 mod 743
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 634102 mod 953.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 102 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 102 an und zerlegen 102 in eine Summer von 2er-Potenzen:
102 = 64+32+4+2
1: 6341=634
2: 6342=6341+1=6341⋅6341 ≡ 634⋅634=401956 ≡ 743 mod 953
4: 6344=6342+2=6342⋅6342 ≡ 743⋅743=552049 ≡ 262 mod 953
8: 6348=6344+4=6344⋅6344 ≡ 262⋅262=68644 ≡ 28 mod 953
16: 63416=6348+8=6348⋅6348 ≡ 28⋅28=784 ≡ 784 mod 953
32: 63432=63416+16=63416⋅63416 ≡ 784⋅784=614656 ≡ 924 mod 953
64: 63464=63432+32=63432⋅63432 ≡ 924⋅924=853776 ≡ 841 mod 953
634102
= 63464+32+4+2
= 63464⋅63432⋅6344⋅6342
≡ 841 ⋅ 924 ⋅ 262 ⋅ 743 mod 953
≡ 777084 ⋅ 262 ⋅ 743 mod 953 ≡ 389 ⋅ 262 ⋅ 743 mod 953
≡ 101918 ⋅ 743 mod 953 ≡ 900 ⋅ 743 mod 953
≡ 668700 mod 953 ≡ 647 mod 953
Es gilt also: 634102 ≡ 647 mod 953
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 80.
Also bestimme x, so dass 80 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 80
| =>83 | = 1⋅80 + 3 |
| =>80 | = 26⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(83,80)=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= 3-1⋅2 | |||
| 2= 80-26⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(80 -26⋅ 3)
= 1⋅3 -1⋅80 +26⋅ 3) = -1⋅80 +27⋅ 3 (=1) |
| 3= 83-1⋅80 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅80 +27⋅(83 -1⋅ 80)
= -1⋅80 +27⋅83 -27⋅ 80) = 27⋅83 -28⋅ 80 (=1) |
Es gilt also: ggt(83,80)=1 = 27⋅83 -28⋅80
oder wenn man 27⋅83 auf die linke Seite bringt:
1 -27⋅83 = -28⋅80
-28⋅80 = -27⋅83 + 1 |+83⋅80
-28⋅80 + 83⋅80 = -27⋅83 + 83⋅80 + 1
(-28 + 83) ⋅ 80 = (-27 + 80) ⋅ 83 + 1
55⋅80 = 53⋅83 + 1
Es gilt also: 55⋅80 = 53⋅83 +1
Somit 55⋅80 = 1 mod 83
55 ist also das Inverse von 80 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 31 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.