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: (400 - 8003) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(400 - 8003) mod 4 ≡ (400 mod 4 - 8003 mod 4) mod 4.

400 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 400 = 400+0 = 4 ⋅ 100 +0.

8003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 8003 = 8000+3 = 4 ⋅ 2000 +3.

Somit gilt:

(400 - 8003) mod 4 ≡ (0 - 3) mod 4 ≡ -3 mod 4 ≡ 1 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (57 ⋅ 81) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(57 ⋅ 81) mod 4 ≡ (57 mod 4 ⋅ 81 mod 4) mod 4.

57 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 57 = 56 + 1 = 14 ⋅ 4 + 1 ist.

81 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 20 ⋅ 4 + 1 ist.

Somit gilt:

(57 ⋅ 81) mod 4 ≡ (1 ⋅ 1) mod 4 ≡ 1 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 26216 mod 677.

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. 262 -> x
2. mod(x²,677) -> 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: 2621=262

2: 2622=2621+1=2621⋅2621 ≡ 262⋅262=68644 ≡ 267 mod 677

4: 2624=2622+2=2622⋅2622 ≡ 267⋅267=71289 ≡ 204 mod 677

8: 2628=2624+4=2624⋅2624 ≡ 204⋅204=41616 ≡ 319 mod 677

16: 26216=2628+8=2628⋅2628 ≡ 319⋅319=101761 ≡ 211 mod 677

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 359160 mod 499.

Lösung einblenden

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

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

160 = 128+32

1: 3591=359

2: 3592=3591+1=3591⋅3591 ≡ 359⋅359=128881 ≡ 139 mod 499

4: 3594=3592+2=3592⋅3592 ≡ 139⋅139=19321 ≡ 359 mod 499

8: 3598=3594+4=3594⋅3594 ≡ 359⋅359=128881 ≡ 139 mod 499

16: 35916=3598+8=3598⋅3598 ≡ 139⋅139=19321 ≡ 359 mod 499

32: 35932=35916+16=35916⋅35916 ≡ 359⋅359=128881 ≡ 139 mod 499

64: 35964=35932+32=35932⋅35932 ≡ 139⋅139=19321 ≡ 359 mod 499

128: 359128=35964+64=35964⋅35964 ≡ 359⋅359=128881 ≡ 139 mod 499

359160

= 359128+32

= 359128⋅35932

≡ 139 ⋅ 139 mod 499
≡ 19321 mod 499 ≡ 359 mod 499

Es gilt also: 359160 ≡ 359 mod 499

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 1⋅67 + 34
=>67 = 1⋅34 + 33
=>34 = 1⋅33 + 1
=>33 = 33⋅1 + 0

also gilt: ggt(101,67)=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= 34-1⋅33
33= 67-1⋅34 eingesetzt in die Zeile drüber: 1 = 1⋅34 -1⋅(67 -1⋅ 34)
= 1⋅34 -1⋅67 +1⋅ 34)
= -1⋅67 +2⋅ 34 (=1)
34= 101-1⋅67 eingesetzt in die Zeile drüber: 1 = -1⋅67 +2⋅(101 -1⋅ 67)
= -1⋅67 +2⋅101 -2⋅ 67)
= 2⋅101 -3⋅ 67 (=1)

Es gilt also: ggt(101,67)=1 = 2⋅101 -3⋅67

oder wenn man 2⋅101 auf die linke Seite bringt:

1 -2⋅101 = -3⋅67

-3⋅67 = -2⋅101 + 1 |+101⋅67

-3⋅67 + 101⋅67 = -2⋅101 + 101⋅67 + 1

(-3 + 101) ⋅ 67 = (-2 + 67) ⋅ 101 + 1

98⋅67 = 65⋅101 + 1

Es gilt also: 98⋅67 = 65⋅101 +1

Somit 98⋅67 = 1 mod 101

98 ist also das Inverse von 67 mod 101

Schlüsselpaar für RSA

Beispiel:

Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 41 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