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: (1504 - 14996) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1504 - 14996) mod 5 ≡ (1504 mod 5 - 14996 mod 5) mod 5.

1504 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1504 = 1500+4 = 5 ⋅ 300 +4.

14996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 14996 = 14000+996 = 5 ⋅ 2800 +996.

Somit gilt:

(1504 - 14996) mod 5 ≡ (4 - 1) mod 5 ≡ 3 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (99 ⋅ 99) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 99) mod 5 ≡ (99 mod 5 ⋅ 99 mod 5) mod 5.

99 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 99 = 95 + 4 = 19 ⋅ 5 + 4 ist.

99 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 99 = 95 + 4 = 19 ⋅ 5 + 4 ist.

Somit gilt:

(99 ⋅ 99) mod 5 ≡ (4 ⋅ 4) mod 5 ≡ 16 mod 5 ≡ 1 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 8548 mod 857.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 854 -> x
2. mod(x²,857) -> 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: 8541=854

2: 8542=8541+1=8541⋅8541 ≡ 854⋅854=729316 ≡ 9 mod 857

4: 8544=8542+2=8542⋅8542 ≡ 9⋅9=81 ≡ 81 mod 857

8: 8548=8544+4=8544⋅8544 ≡ 81⋅81=6561 ≡ 562 mod 857

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 198136 mod 211.

Lösung einblenden

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

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

136 = 128+8

1: 1981=198

2: 1982=1981+1=1981⋅1981 ≡ 198⋅198=39204 ≡ 169 mod 211

4: 1984=1982+2=1982⋅1982 ≡ 169⋅169=28561 ≡ 76 mod 211

8: 1988=1984+4=1984⋅1984 ≡ 76⋅76=5776 ≡ 79 mod 211

16: 19816=1988+8=1988⋅1988 ≡ 79⋅79=6241 ≡ 122 mod 211

32: 19832=19816+16=19816⋅19816 ≡ 122⋅122=14884 ≡ 114 mod 211

64: 19864=19832+32=19832⋅19832 ≡ 114⋅114=12996 ≡ 125 mod 211

128: 198128=19864+64=19864⋅19864 ≡ 125⋅125=15625 ≡ 11 mod 211

198136

= 198128+8

= 198128⋅1988

≡ 11 ⋅ 79 mod 211
≡ 869 mod 211 ≡ 25 mod 211

Es gilt also: 198136 ≡ 25 mod 211

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 1⋅77 + 24
=>77 = 3⋅24 + 5
=>24 = 4⋅5 + 4
=>5 = 1⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(101,77)=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= 5-1⋅4
4= 24-4⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -1⋅(24 -4⋅ 5)
= 1⋅5 -1⋅24 +4⋅ 5)
= -1⋅24 +5⋅ 5 (=1)
5= 77-3⋅24 eingesetzt in die Zeile drüber: 1 = -1⋅24 +5⋅(77 -3⋅ 24)
= -1⋅24 +5⋅77 -15⋅ 24)
= 5⋅77 -16⋅ 24 (=1)
24= 101-1⋅77 eingesetzt in die Zeile drüber: 1 = 5⋅77 -16⋅(101 -1⋅ 77)
= 5⋅77 -16⋅101 +16⋅ 77)
= -16⋅101 +21⋅ 77 (=1)

Es gilt also: ggt(101,77)=1 = -16⋅101 +21⋅77

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

1 +16⋅101 = +21⋅77

Es gilt also: 21⋅77 = 16⋅101 +1

Somit 21⋅77 = 1 mod 101

21 ist also das Inverse von 77 mod 101

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden