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: (32006 + 8000) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(32006 + 8000) mod 8 ≡ (32006 mod 8 + 8000 mod 8) mod 8.

32006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 32006 = 32000+6 = 8 ⋅ 4000 +6.

8000 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 8000 = 8000+0 = 8 ⋅ 1000 +0.

Somit gilt:

(32006 + 8000) mod 8 ≡ (6 + 0) mod 8 ≡ 6 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (53 ⋅ 33) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(53 ⋅ 33) mod 8 ≡ (53 mod 8 ⋅ 33 mod 8) mod 8.

53 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 53 = 48 + 5 = 6 ⋅ 8 + 5 ist.

33 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 33 = 32 + 1 = 4 ⋅ 8 + 1 ist.

Somit gilt:

(53 ⋅ 33) mod 8 ≡ (5 ⋅ 1) mod 8 ≡ 5 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 77416 mod 967.

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. 774 -> x
2. mod(x²,967) -> 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: 7741=774

2: 7742=7741+1=7741⋅7741 ≡ 774⋅774=599076 ≡ 503 mod 967

4: 7744=7742+2=7742⋅7742 ≡ 503⋅503=253009 ≡ 622 mod 967

8: 7748=7744+4=7744⋅7744 ≡ 622⋅622=386884 ≡ 84 mod 967

16: 77416=7748+8=7748⋅7748 ≡ 84⋅84=7056 ≡ 287 mod 967

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 557187 mod 829.

Lösung einblenden

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

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

187 = 128+32+16+8+2+1

1: 5571=557

2: 5572=5571+1=5571⋅5571 ≡ 557⋅557=310249 ≡ 203 mod 829

4: 5574=5572+2=5572⋅5572 ≡ 203⋅203=41209 ≡ 588 mod 829

8: 5578=5574+4=5574⋅5574 ≡ 588⋅588=345744 ≡ 51 mod 829

16: 55716=5578+8=5578⋅5578 ≡ 51⋅51=2601 ≡ 114 mod 829

32: 55732=55716+16=55716⋅55716 ≡ 114⋅114=12996 ≡ 561 mod 829

64: 55764=55732+32=55732⋅55732 ≡ 561⋅561=314721 ≡ 530 mod 829

128: 557128=55764+64=55764⋅55764 ≡ 530⋅530=280900 ≡ 698 mod 829

557187

= 557128+32+16+8+2+1

= 557128⋅55732⋅55716⋅5578⋅5572⋅5571

698 ⋅ 561 ⋅ 114 ⋅ 51 ⋅ 203 ⋅ 557 mod 829
391578 ⋅ 114 ⋅ 51 ⋅ 203 ⋅ 557 mod 829 ≡ 290 ⋅ 114 ⋅ 51 ⋅ 203 ⋅ 557 mod 829
33060 ⋅ 51 ⋅ 203 ⋅ 557 mod 829 ≡ 729 ⋅ 51 ⋅ 203 ⋅ 557 mod 829
37179 ⋅ 203 ⋅ 557 mod 829 ≡ 703 ⋅ 203 ⋅ 557 mod 829
142709 ⋅ 557 mod 829 ≡ 121 ⋅ 557 mod 829
67397 mod 829 ≡ 248 mod 829

Es gilt also: 557187 ≡ 248 mod 829

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 40 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 40

=>89 = 2⋅40 + 9
=>40 = 4⋅9 + 4
=>9 = 2⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(89,40)=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= 9-2⋅4
4= 40-4⋅9 eingesetzt in die Zeile drüber: 1 = 1⋅9 -2⋅(40 -4⋅ 9)
= 1⋅9 -2⋅40 +8⋅ 9)
= -2⋅40 +9⋅ 9 (=1)
9= 89-2⋅40 eingesetzt in die Zeile drüber: 1 = -2⋅40 +9⋅(89 -2⋅ 40)
= -2⋅40 +9⋅89 -18⋅ 40)
= 9⋅89 -20⋅ 40 (=1)

Es gilt also: ggt(89,40)=1 = 9⋅89 -20⋅40

oder wenn man 9⋅89 auf die linke Seite bringt:

1 -9⋅89 = -20⋅40

-20⋅40 = -9⋅89 + 1 |+89⋅40

-20⋅40 + 89⋅40 = -9⋅89 + 89⋅40 + 1

(-20 + 89) ⋅ 40 = (-9 + 40) ⋅ 89 + 1

69⋅40 = 31⋅89 + 1

Es gilt also: 69⋅40 = 31⋅89 +1

Somit 69⋅40 = 1 mod 89

69 ist also das Inverse von 40 mod 89

Schlüsselpaar für RSA

Beispiel:

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