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: (1199 - 7999) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1199 - 7999) mod 4 ≡ (1199 mod 4 - 7999 mod 4) mod 4.

1199 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1199 = 1100+99 = 4 ⋅ 275 +99.

7999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 7999 = 7000+999 = 4 ⋅ 1750 +999.

Somit gilt:

(1199 - 7999) mod 4 ≡ (3 - 3) mod 4 ≡ 0 mod 4.

Modulo multiplizieren

Beispiel:

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

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

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

33 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 33 = 33 + 0 = 3 ⋅ 11 + 0 ist.

53 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 53 = 44 + 9 = 4 ⋅ 11 + 9 ist.

Somit gilt:

(33 ⋅ 53) mod 11 ≡ (0 ⋅ 9) mod 11 ≡ 0 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 204128 mod 643.

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. 204 -> x
2. mod(x²,643) -> 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: 2041=204

2: 2042=2041+1=2041⋅2041 ≡ 204⋅204=41616 ≡ 464 mod 643

4: 2044=2042+2=2042⋅2042 ≡ 464⋅464=215296 ≡ 534 mod 643

8: 2048=2044+4=2044⋅2044 ≡ 534⋅534=285156 ≡ 307 mod 643

16: 20416=2048+8=2048⋅2048 ≡ 307⋅307=94249 ≡ 371 mod 643

32: 20432=20416+16=20416⋅20416 ≡ 371⋅371=137641 ≡ 39 mod 643

64: 20464=20432+32=20432⋅20432 ≡ 39⋅39=1521 ≡ 235 mod 643

128: 204128=20464+64=20464⋅20464 ≡ 235⋅235=55225 ≡ 570 mod 643

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 34967 mod 443.

Lösung einblenden

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

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

67 = 64+2+1

1: 3491=349

2: 3492=3491+1=3491⋅3491 ≡ 349⋅349=121801 ≡ 419 mod 443

4: 3494=3492+2=3492⋅3492 ≡ 419⋅419=175561 ≡ 133 mod 443

8: 3498=3494+4=3494⋅3494 ≡ 133⋅133=17689 ≡ 412 mod 443

16: 34916=3498+8=3498⋅3498 ≡ 412⋅412=169744 ≡ 75 mod 443

32: 34932=34916+16=34916⋅34916 ≡ 75⋅75=5625 ≡ 309 mod 443

64: 34964=34932+32=34932⋅34932 ≡ 309⋅309=95481 ≡ 236 mod 443

34967

= 34964+2+1

= 34964⋅3492⋅3491

≡ 236 ⋅ 419 ⋅ 349 mod 443
≡ 98884 ⋅ 349 mod 443 ≡ 95 ⋅ 349 mod 443
≡ 33155 mod 443 ≡ 373 mod 443

Es gilt also: 34967 ≡ 373 mod 443

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>89 = 1⋅72 + 17
=>72 = 4⋅17 + 4
=>17 = 4⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(89,72)=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= 17-4⋅4
4= 72-4⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -4⋅(72 -4⋅ 17)
= 1⋅17 -4⋅72 +16⋅ 17)
= -4⋅72 +17⋅ 17 (=1)
17= 89-1⋅72 eingesetzt in die Zeile drüber: 1 = -4⋅72 +17⋅(89 -1⋅ 72)
= -4⋅72 +17⋅89 -17⋅ 72)
= 17⋅89 -21⋅ 72 (=1)

Es gilt also: ggt(89,72)=1 = 17⋅89 -21⋅72

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

1 -17⋅89 = -21⋅72

-21⋅72 = -17⋅89 + 1 |+89⋅72

-21⋅72 + 89⋅72 = -17⋅89 + 89⋅72 + 1

(-21 + 89) ⋅ 72 = (-17 + 72) ⋅ 89 + 1

68⋅72 = 55⋅89 + 1

Es gilt also: 68⋅72 = 55⋅89 +1

Somit 68⋅72 = 1 mod 89

68 ist also das Inverse von 72 mod 89

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden