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: (1194 + 1801) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1194 + 1801) mod 6 ≡ (1194 mod 6 + 1801 mod 6) mod 6.

1194 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 1194 = 1200-6 = 6 ⋅ 200 -6 = 6 ⋅ 200 - 6 + 0.

1801 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 1801 = 1800+1 = 6 ⋅ 300 +1.

Somit gilt:

(1194 + 1801) mod 6 ≡ (0 + 1) mod 6 ≡ 1 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (80 ⋅ 83) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(80 ⋅ 83) mod 8 ≡ (80 mod 8 ⋅ 83 mod 8) mod 8.

80 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 80 = 80 + 0 = 10 ⋅ 8 + 0 ist.

83 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 83 = 80 + 3 = 10 ⋅ 8 + 3 ist.

Somit gilt:

(80 ⋅ 83) mod 8 ≡ (0 ⋅ 3) mod 8 ≡ 0 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 9716 mod 239.

Lösung einblenden

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. 97 -> x
2. mod(x²,239) -> 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: 971=97

2: 972=971+1=971⋅971 ≡ 97⋅97=9409 ≡ 88 mod 239

4: 974=972+2=972⋅972 ≡ 88⋅88=7744 ≡ 96 mod 239

8: 978=974+4=974⋅974 ≡ 96⋅96=9216 ≡ 134 mod 239

16: 9716=978+8=978⋅978 ≡ 134⋅134=17956 ≡ 31 mod 239

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 655172 mod 769.

Lösung einblenden

Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 172 (grauer Kasten).

Dann schauen wir die Binärdarstellung von 172 an und zerlegen 172 in eine Summer von 2er-Potenzen:

172 = 128+32+8+4

1: 6551=655

2: 6552=6551+1=6551⋅6551 ≡ 655⋅655=429025 ≡ 692 mod 769

4: 6554=6552+2=6552⋅6552 ≡ 692⋅692=478864 ≡ 546 mod 769

8: 6558=6554+4=6554⋅6554 ≡ 546⋅546=298116 ≡ 513 mod 769

16: 65516=6558+8=6558⋅6558 ≡ 513⋅513=263169 ≡ 171 mod 769

32: 65532=65516+16=65516⋅65516 ≡ 171⋅171=29241 ≡ 19 mod 769

64: 65564=65532+32=65532⋅65532 ≡ 19⋅19=361 ≡ 361 mod 769

128: 655128=65564+64=65564⋅65564 ≡ 361⋅361=130321 ≡ 360 mod 769

655172

= 655128+32+8+4

= 655128⋅65532⋅6558⋅6554

≡ 360 ⋅ 19 ⋅ 513 ⋅ 546 mod 769
≡ 6840 ⋅ 513 ⋅ 546 mod 769 ≡ 688 ⋅ 513 ⋅ 546 mod 769
≡ 352944 ⋅ 546 mod 769 ≡ 742 ⋅ 546 mod 769
≡ 405132 mod 769 ≡ 638 mod 769

Es gilt also: 655172 ≡ 638 mod 769

erweiterter Euklid'scher Algorithmus

Beispiel:

Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-101-Inverse zur Zahl 87.

Also bestimme x, so dass 87 ⋅ x ≡ 1 mod 101 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 101 und 87

=>101 = 1⋅87 + 14
=>87 = 6⋅14 + 3
=>14 = 4⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(101,87)=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= 14-4⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(14 -4⋅ 3)
= 1⋅3 -1⋅14 +4⋅ 3)
= -1⋅14 +5⋅ 3 (=1)
3= 87-6⋅14 eingesetzt in die Zeile drüber: 1 = -1⋅14 +5⋅(87 -6⋅ 14)
= -1⋅14 +5⋅87 -30⋅ 14)
= 5⋅87 -31⋅ 14 (=1)
14= 101-1⋅87 eingesetzt in die Zeile drüber: 1 = 5⋅87 -31⋅(101 -1⋅ 87)
= 5⋅87 -31⋅101 +31⋅ 87)
= -31⋅101 +36⋅ 87 (=1)

Es gilt also: ggt(101,87)=1 = -31⋅101 +36⋅87

oder wenn man -31⋅101 auf die linke Seite bringt:

1 +31⋅101 = +36⋅87

Es gilt also: 36⋅87 = 31⋅101 +1

Somit 36⋅87 = 1 mod 101

36 ist also das Inverse von 87 mod 101

Schlüsselpaar für RSA

Beispiel:

Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 79 und q = 41. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.

Lösung einblenden