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: (3499 + 21000) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3499 + 21000) mod 7 ≡ (3499 mod 7 + 21000 mod 7) mod 7.

3499 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 3499 = 3500-1 = 7 ⋅ 500 -1 = 7 ⋅ 500 - 7 + 6.

21000 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 21000 = 21000+0 = 7 ⋅ 3000 +0.

Somit gilt:

(3499 + 21000) mod 7 ≡ (6 + 0) mod 7 ≡ 6 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (25 ⋅ 34) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(25 ⋅ 34) mod 9 ≡ (25 mod 9 ⋅ 34 mod 9) mod 9.

25 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 25 = 18 + 7 = 2 ⋅ 9 + 7 ist.

34 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 34 = 27 + 7 = 3 ⋅ 9 + 7 ist.

Somit gilt:

(25 ⋅ 34) mod 9 ≡ (7 ⋅ 7) mod 9 ≡ 49 mod 9 ≡ 4 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 463128 mod 661.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 463 -> x
2. mod(x²,661) -> 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: 4631=463

2: 4632=4631+1=4631⋅4631 ≡ 463⋅463=214369 ≡ 205 mod 661

4: 4634=4632+2=4632⋅4632 ≡ 205⋅205=42025 ≡ 382 mod 661

8: 4638=4634+4=4634⋅4634 ≡ 382⋅382=145924 ≡ 504 mod 661

16: 46316=4638+8=4638⋅4638 ≡ 504⋅504=254016 ≡ 192 mod 661

32: 46332=46316+16=46316⋅46316 ≡ 192⋅192=36864 ≡ 509 mod 661

64: 46364=46332+32=46332⋅46332 ≡ 509⋅509=259081 ≡ 630 mod 661

128: 463128=46364+64=46364⋅46364 ≡ 630⋅630=396900 ≡ 300 mod 661

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 668104 mod 967.

Lösung einblenden

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

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

104 = 64+32+8

1: 6681=668

2: 6682=6681+1=6681⋅6681 ≡ 668⋅668=446224 ≡ 437 mod 967

4: 6684=6682+2=6682⋅6682 ≡ 437⋅437=190969 ≡ 470 mod 967

8: 6688=6684+4=6684⋅6684 ≡ 470⋅470=220900 ≡ 424 mod 967

16: 66816=6688+8=6688⋅6688 ≡ 424⋅424=179776 ≡ 881 mod 967

32: 66832=66816+16=66816⋅66816 ≡ 881⋅881=776161 ≡ 627 mod 967

64: 66864=66832+32=66832⋅66832 ≡ 627⋅627=393129 ≡ 527 mod 967

668104

= 66864+32+8

= 66864⋅66832⋅6688

≡ 527 ⋅ 627 ⋅ 424 mod 967
≡ 330429 ⋅ 424 mod 967 ≡ 682 ⋅ 424 mod 967
≡ 289168 mod 967 ≡ 35 mod 967

Es gilt also: 668104 ≡ 35 mod 967

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 48 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 48

=>67 = 1⋅48 + 19
=>48 = 2⋅19 + 10
=>19 = 1⋅10 + 9
=>10 = 1⋅9 + 1
=>9 = 9⋅1 + 0

also gilt: ggt(67,48)=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= 10-1⋅9
9= 19-1⋅10 eingesetzt in die Zeile drüber: 1 = 1⋅10 -1⋅(19 -1⋅ 10)
= 1⋅10 -1⋅19 +1⋅ 10)
= -1⋅19 +2⋅ 10 (=1)
10= 48-2⋅19 eingesetzt in die Zeile drüber: 1 = -1⋅19 +2⋅(48 -2⋅ 19)
= -1⋅19 +2⋅48 -4⋅ 19)
= 2⋅48 -5⋅ 19 (=1)
19= 67-1⋅48 eingesetzt in die Zeile drüber: 1 = 2⋅48 -5⋅(67 -1⋅ 48)
= 2⋅48 -5⋅67 +5⋅ 48)
= -5⋅67 +7⋅ 48 (=1)

Es gilt also: ggt(67,48)=1 = -5⋅67 +7⋅48

oder wenn man -5⋅67 auf die linke Seite bringt:

1 +5⋅67 = +7⋅48

Es gilt also: 7⋅48 = 5⋅67 +1

Somit 7⋅48 = 1 mod 67

7 ist also das Inverse von 48 mod 67

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden