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: (86 + 270) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(86 + 270) mod 9 ≡ (86 mod 9 + 270 mod 9) mod 9.

86 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 86 = 90-4 = 9 ⋅ 10 -4 = 9 ⋅ 10 - 9 + 5.

270 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 270 = 270+0 = 9 ⋅ 30 +0.

Somit gilt:

(86 + 270) mod 9 ≡ (5 + 0) mod 9 ≡ 5 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (60 ⋅ 80) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(60 ⋅ 80) mod 6 ≡ (60 mod 6 ⋅ 80 mod 6) mod 6.

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

80 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 80 = 78 + 2 = 13 ⋅ 6 + 2 ist.

Somit gilt:

(60 ⋅ 80) mod 6 ≡ (0 ⋅ 2) mod 6 ≡ 0 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 29532 mod 937.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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²,937) -> 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 ≡ 821 mod 937

4: 2954=2952+2=2952⋅2952 ≡ 821⋅821=674041 ≡ 338 mod 937

8: 2958=2954+4=2954⋅2954 ≡ 338⋅338=114244 ≡ 867 mod 937

16: 29516=2958+8=2958⋅2958 ≡ 867⋅867=751689 ≡ 215 mod 937

32: 29532=29516+16=29516⋅29516 ≡ 215⋅215=46225 ≡ 312 mod 937

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 80871 mod 907.

Lösung einblenden

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

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

71 = 64+4+2+1

1: 8081=808

2: 8082=8081+1=8081⋅8081 ≡ 808⋅808=652864 ≡ 731 mod 907

4: 8084=8082+2=8082⋅8082 ≡ 731⋅731=534361 ≡ 138 mod 907

8: 8088=8084+4=8084⋅8084 ≡ 138⋅138=19044 ≡ 904 mod 907

16: 80816=8088+8=8088⋅8088 ≡ 904⋅904=817216 ≡ 9 mod 907

32: 80832=80816+16=80816⋅80816 ≡ 9⋅9=81 ≡ 81 mod 907

64: 80864=80832+32=80832⋅80832 ≡ 81⋅81=6561 ≡ 212 mod 907

80871

= 80864+4+2+1

= 80864⋅8084⋅8082⋅8081

≡ 212 ⋅ 138 ⋅ 731 ⋅ 808 mod 907
≡ 29256 ⋅ 731 ⋅ 808 mod 907 ≡ 232 ⋅ 731 ⋅ 808 mod 907
≡ 169592 ⋅ 808 mod 907 ≡ 890 ⋅ 808 mod 907
≡ 719120 mod 907 ≡ 776 mod 907

Es gilt also: 80871 ≡ 776 mod 907

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 2⋅35 + 31
=>35 = 1⋅31 + 4
=>31 = 7⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(101,35)=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= 4-1⋅3
3= 31-7⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(31 -7⋅ 4)
= 1⋅4 -1⋅31 +7⋅ 4)
= -1⋅31 +8⋅ 4 (=1)
4= 35-1⋅31 eingesetzt in die Zeile drüber: 1 = -1⋅31 +8⋅(35 -1⋅ 31)
= -1⋅31 +8⋅35 -8⋅ 31)
= 8⋅35 -9⋅ 31 (=1)
31= 101-2⋅35 eingesetzt in die Zeile drüber: 1 = 8⋅35 -9⋅(101 -2⋅ 35)
= 8⋅35 -9⋅101 +18⋅ 35)
= -9⋅101 +26⋅ 35 (=1)

Es gilt also: ggt(101,35)=1 = -9⋅101 +26⋅35

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

1 +9⋅101 = +26⋅35

Es gilt also: 26⋅35 = 9⋅101 +1

Somit 26⋅35 = 1 mod 101

26 ist also das Inverse von 35 mod 101

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden