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: (19997 + 4996) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(19997 + 4996) mod 5 ≡ (19997 mod 5 + 4996 mod 5) mod 5.

19997 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 19997 = 19000+997 = 5 ⋅ 3800 +997.

4996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 4996 = 4000+996 = 5 ⋅ 800 +996.

Somit gilt:

(19997 + 4996) mod 5 ≡ (2 + 1) mod 5 ≡ 3 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (26 ⋅ 92) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(26 ⋅ 92) mod 7 ≡ (26 mod 7 ⋅ 92 mod 7) mod 7.

26 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 26 = 21 + 5 = 3 ⋅ 7 + 5 ist.

92 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 92 = 91 + 1 = 13 ⋅ 7 + 1 ist.

Somit gilt:

(26 ⋅ 92) mod 7 ≡ (5 ⋅ 1) mod 7 ≡ 5 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 27616 mod 433.

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. 276 -> x
2. mod(x²,433) -> 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: 2761=276

2: 2762=2761+1=2761⋅2761 ≡ 276⋅276=76176 ≡ 401 mod 433

4: 2764=2762+2=2762⋅2762 ≡ 401⋅401=160801 ≡ 158 mod 433

8: 2768=2764+4=2764⋅2764 ≡ 158⋅158=24964 ≡ 283 mod 433

16: 27616=2768+8=2768⋅2768 ≡ 283⋅283=80089 ≡ 417 mod 433

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 225167 mod 463.

Lösung einblenden

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

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

167 = 128+32+4+2+1

1: 2251=225

2: 2252=2251+1=2251⋅2251 ≡ 225⋅225=50625 ≡ 158 mod 463

4: 2254=2252+2=2252⋅2252 ≡ 158⋅158=24964 ≡ 425 mod 463

8: 2258=2254+4=2254⋅2254 ≡ 425⋅425=180625 ≡ 55 mod 463

16: 22516=2258+8=2258⋅2258 ≡ 55⋅55=3025 ≡ 247 mod 463

32: 22532=22516+16=22516⋅22516 ≡ 247⋅247=61009 ≡ 356 mod 463

64: 22564=22532+32=22532⋅22532 ≡ 356⋅356=126736 ≡ 337 mod 463

128: 225128=22564+64=22564⋅22564 ≡ 337⋅337=113569 ≡ 134 mod 463

225167

= 225128+32+4+2+1

= 225128⋅22532⋅2254⋅2252⋅2251

≡ 134 ⋅ 356 ⋅ 425 ⋅ 158 ⋅ 225 mod 463
≡ 47704 ⋅ 425 ⋅ 158 ⋅ 225 mod 463 ≡ 15 ⋅ 425 ⋅ 158 ⋅ 225 mod 463
≡ 6375 ⋅ 158 ⋅ 225 mod 463 ≡ 356 ⋅ 158 ⋅ 225 mod 463
≡ 56248 ⋅ 225 mod 463 ≡ 225 ⋅ 225 mod 463
≡ 50625 mod 463 ≡ 158 mod 463

Es gilt also: 225167 ≡ 158 mod 463

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>73 = 1⋅51 + 22
=>51 = 2⋅22 + 7
=>22 = 3⋅7 + 1
=>7 = 7⋅1 + 0

also gilt: ggt(73,51)=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= 22-3⋅7
7= 51-2⋅22 eingesetzt in die Zeile drüber: 1 = 1⋅22 -3⋅(51 -2⋅ 22)
= 1⋅22 -3⋅51 +6⋅ 22)
= -3⋅51 +7⋅ 22 (=1)
22= 73-1⋅51 eingesetzt in die Zeile drüber: 1 = -3⋅51 +7⋅(73 -1⋅ 51)
= -3⋅51 +7⋅73 -7⋅ 51)
= 7⋅73 -10⋅ 51 (=1)

Es gilt also: ggt(73,51)=1 = 7⋅73 -10⋅51

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

1 -7⋅73 = -10⋅51

-10⋅51 = -7⋅73 + 1 |+73⋅51

-10⋅51 + 73⋅51 = -7⋅73 + 73⋅51 + 1

(-10 + 73) ⋅ 51 = (-7 + 51) ⋅ 73 + 1

63⋅51 = 44⋅73 + 1

Es gilt also: 63⋅51 = 44⋅73 +1

Somit 63⋅51 = 1 mod 73

63 ist also das Inverse von 51 mod 73

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden