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: (144 - 2801) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(144 - 2801) mod 7 ≡ (144 mod 7 - 2801 mod 7) mod 7.

144 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 144 = 140+4 = 7 ⋅ 20 +4.

2801 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 2801 = 2800+1 = 7 ⋅ 400 +1.

Somit gilt:

(144 - 2801) mod 7 ≡ (4 - 1) mod 7 ≡ 3 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (100 ⋅ 17) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(100 ⋅ 17) mod 5 ≡ (100 mod 5 ⋅ 17 mod 5) mod 5.

100 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 100 = 100 + 0 = 20 ⋅ 5 + 0 ist.

17 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 17 = 15 + 2 = 3 ⋅ 5 + 2 ist.

Somit gilt:

(100 ⋅ 17) mod 5 ≡ (0 ⋅ 2) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 131128 mod 389.

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. 131 -> x
2. mod(x²,389) -> 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: 1311=131

2: 1312=1311+1=1311⋅1311 ≡ 131⋅131=17161 ≡ 45 mod 389

4: 1314=1312+2=1312⋅1312 ≡ 45⋅45=2025 ≡ 80 mod 389

8: 1318=1314+4=1314⋅1314 ≡ 80⋅80=6400 ≡ 176 mod 389

16: 13116=1318+8=1318⋅1318 ≡ 176⋅176=30976 ≡ 245 mod 389

32: 13132=13116+16=13116⋅13116 ≡ 245⋅245=60025 ≡ 119 mod 389

64: 13164=13132+32=13132⋅13132 ≡ 119⋅119=14161 ≡ 157 mod 389

128: 131128=13164+64=13164⋅13164 ≡ 157⋅157=24649 ≡ 142 mod 389

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 729219 mod 733.

Lösung einblenden

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

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

219 = 128+64+16+8+2+1

1: 7291=729

2: 7292=7291+1=7291⋅7291 ≡ 729⋅729=531441 ≡ 16 mod 733

4: 7294=7292+2=7292⋅7292 ≡ 16⋅16=256 ≡ 256 mod 733

8: 7298=7294+4=7294⋅7294 ≡ 256⋅256=65536 ≡ 299 mod 733

16: 72916=7298+8=7298⋅7298 ≡ 299⋅299=89401 ≡ 708 mod 733

32: 72932=72916+16=72916⋅72916 ≡ 708⋅708=501264 ≡ 625 mod 733

64: 72964=72932+32=72932⋅72932 ≡ 625⋅625=390625 ≡ 669 mod 733

128: 729128=72964+64=72964⋅72964 ≡ 669⋅669=447561 ≡ 431 mod 733

729219

= 729128+64+16+8+2+1

= 729128⋅72964⋅72916⋅7298⋅7292⋅7291

431 ⋅ 669 ⋅ 708 ⋅ 299 ⋅ 16 ⋅ 729 mod 733
288339 ⋅ 708 ⋅ 299 ⋅ 16 ⋅ 729 mod 733 ≡ 270 ⋅ 708 ⋅ 299 ⋅ 16 ⋅ 729 mod 733
191160 ⋅ 299 ⋅ 16 ⋅ 729 mod 733 ≡ 580 ⋅ 299 ⋅ 16 ⋅ 729 mod 733
173420 ⋅ 16 ⋅ 729 mod 733 ≡ 432 ⋅ 16 ⋅ 729 mod 733
6912 ⋅ 729 mod 733 ≡ 315 ⋅ 729 mod 733
229635 mod 733 ≡ 206 mod 733

Es gilt also: 729219 ≡ 206 mod 733

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 1⋅72 + 29
=>72 = 2⋅29 + 14
=>29 = 2⋅14 + 1
=>14 = 14⋅1 + 0

also gilt: ggt(101,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= 29-2⋅14
14= 72-2⋅29 eingesetzt in die Zeile drüber: 1 = 1⋅29 -2⋅(72 -2⋅ 29)
= 1⋅29 -2⋅72 +4⋅ 29)
= -2⋅72 +5⋅ 29 (=1)
29= 101-1⋅72 eingesetzt in die Zeile drüber: 1 = -2⋅72 +5⋅(101 -1⋅ 72)
= -2⋅72 +5⋅101 -5⋅ 72)
= 5⋅101 -7⋅ 72 (=1)

Es gilt also: ggt(101,72)=1 = 5⋅101 -7⋅72

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

1 -5⋅101 = -7⋅72

-7⋅72 = -5⋅101 + 1 |+101⋅72

-7⋅72 + 101⋅72 = -5⋅101 + 101⋅72 + 1

(-7 + 101) ⋅ 72 = (-5 + 72) ⋅ 101 + 1

94⋅72 = 67⋅101 + 1

Es gilt also: 94⋅72 = 67⋅101 +1

Somit 94⋅72 = 1 mod 101

94 ist also das Inverse von 72 mod 101

Schlüsselpaar für RSA

Beispiel:

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