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: (47 + 205) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(47 + 205) mod 5 ≡ (47 mod 5 + 205 mod 5) mod 5.

47 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 47 = 40+7 = 5 ⋅ 8 +7.

205 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 205 = 200+5 = 5 ⋅ 40 +5.

Somit gilt:

(47 + 205) mod 5 ≡ (2 + 0) mod 5 ≡ 2 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (31 ⋅ 35) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 35) mod 5 ≡ (31 mod 5 ⋅ 35 mod 5) mod 5.

31 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 31 = 30 + 1 = 6 ⋅ 5 + 1 ist.

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

Somit gilt:

(31 ⋅ 35) mod 5 ≡ (1 ⋅ 0) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 19032 mod 499.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 190 -> x
2. mod(x²,499) -> 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: 1901=190

2: 1902=1901+1=1901⋅1901 ≡ 190⋅190=36100 ≡ 172 mod 499

4: 1904=1902+2=1902⋅1902 ≡ 172⋅172=29584 ≡ 143 mod 499

8: 1908=1904+4=1904⋅1904 ≡ 143⋅143=20449 ≡ 489 mod 499

16: 19016=1908+8=1908⋅1908 ≡ 489⋅489=239121 ≡ 100 mod 499

32: 19032=19016+16=19016⋅19016 ≡ 100⋅100=10000 ≡ 20 mod 499

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 119246 mod 263.

Lösung einblenden

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

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

246 = 128+64+32+16+4+2

1: 1191=119

2: 1192=1191+1=1191⋅1191 ≡ 119⋅119=14161 ≡ 222 mod 263

4: 1194=1192+2=1192⋅1192 ≡ 222⋅222=49284 ≡ 103 mod 263

8: 1198=1194+4=1194⋅1194 ≡ 103⋅103=10609 ≡ 89 mod 263

16: 11916=1198+8=1198⋅1198 ≡ 89⋅89=7921 ≡ 31 mod 263

32: 11932=11916+16=11916⋅11916 ≡ 31⋅31=961 ≡ 172 mod 263

64: 11964=11932+32=11932⋅11932 ≡ 172⋅172=29584 ≡ 128 mod 263

128: 119128=11964+64=11964⋅11964 ≡ 128⋅128=16384 ≡ 78 mod 263

119246

= 119128+64+32+16+4+2

= 119128⋅11964⋅11932⋅11916⋅1194⋅1192

78 ⋅ 128 ⋅ 172 ⋅ 31 ⋅ 103 ⋅ 222 mod 263
9984 ⋅ 172 ⋅ 31 ⋅ 103 ⋅ 222 mod 263 ≡ 253 ⋅ 172 ⋅ 31 ⋅ 103 ⋅ 222 mod 263
43516 ⋅ 31 ⋅ 103 ⋅ 222 mod 263 ≡ 121 ⋅ 31 ⋅ 103 ⋅ 222 mod 263
3751 ⋅ 103 ⋅ 222 mod 263 ≡ 69 ⋅ 103 ⋅ 222 mod 263
7107 ⋅ 222 mod 263 ≡ 6 ⋅ 222 mod 263
1332 mod 263 ≡ 17 mod 263

Es gilt also: 119246 ≡ 17 mod 263

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 23 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 23

=>73 = 3⋅23 + 4
=>23 = 5⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(73,23)=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= 4-1⋅3
3= 23-5⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(23 -5⋅ 4)
= 1⋅4 -1⋅23 +5⋅ 4)
= -1⋅23 +6⋅ 4 (=1)
4= 73-3⋅23 eingesetzt in die Zeile drüber: 1 = -1⋅23 +6⋅(73 -3⋅ 23)
= -1⋅23 +6⋅73 -18⋅ 23)
= 6⋅73 -19⋅ 23 (=1)

Es gilt also: ggt(73,23)=1 = 6⋅73 -19⋅23

oder wenn man 6⋅73 auf die linke Seite bringt:

1 -6⋅73 = -19⋅23

-19⋅23 = -6⋅73 + 1 |+73⋅23

-19⋅23 + 73⋅23 = -6⋅73 + 73⋅23 + 1

(-19 + 73) ⋅ 23 = (-6 + 23) ⋅ 73 + 1

54⋅23 = 17⋅73 + 1

Es gilt also: 54⋅23 = 17⋅73 +1

Somit 54⋅23 = 1 mod 73

54 ist also das Inverse von 23 mod 73

Schlüsselpaar für RSA

Beispiel:

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