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: (317 + 7996) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(317 + 7996) mod 8 ≡ (317 mod 8 + 7996 mod 8) mod 8.

317 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 317 = 320-3 = 8 ⋅ 40 -3 = 8 ⋅ 40 - 8 + 5.

7996 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 7996 = 7000+996 = 8 ⋅ 875 +996.

Somit gilt:

(317 + 7996) mod 8 ≡ (5 + 4) mod 8 ≡ 9 mod 8 ≡ 1 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (38 ⋅ 70) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 70) mod 6 ≡ (38 mod 6 ⋅ 70 mod 6) mod 6.

38 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 38 = 36 + 2 = 6 ⋅ 6 + 2 ist.

70 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 11 ⋅ 6 + 4 ist.

Somit gilt:

(38 ⋅ 70) mod 6 ≡ (2 ⋅ 4) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 2138 mod 347.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 213 -> x
2. mod(x²,347) -> 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: 2131=213

2: 2132=2131+1=2131⋅2131 ≡ 213⋅213=45369 ≡ 259 mod 347

4: 2134=2132+2=2132⋅2132 ≡ 259⋅259=67081 ≡ 110 mod 347

8: 2138=2134+4=2134⋅2134 ≡ 110⋅110=12100 ≡ 302 mod 347

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 65969 mod 823.

Lösung einblenden

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

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

69 = 64+4+1

1: 6591=659

2: 6592=6591+1=6591⋅6591 ≡ 659⋅659=434281 ≡ 560 mod 823

4: 6594=6592+2=6592⋅6592 ≡ 560⋅560=313600 ≡ 37 mod 823

8: 6598=6594+4=6594⋅6594 ≡ 37⋅37=1369 ≡ 546 mod 823

16: 65916=6598+8=6598⋅6598 ≡ 546⋅546=298116 ≡ 190 mod 823

32: 65932=65916+16=65916⋅65916 ≡ 190⋅190=36100 ≡ 711 mod 823

64: 65964=65932+32=65932⋅65932 ≡ 711⋅711=505521 ≡ 199 mod 823

65969

= 65964+4+1

= 65964⋅6594⋅6591

≡ 199 ⋅ 37 ⋅ 659 mod 823
≡ 7363 ⋅ 659 mod 823 ≡ 779 ⋅ 659 mod 823
≡ 513361 mod 823 ≡ 632 mod 823

Es gilt also: 65969 ≡ 632 mod 823

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 53 ⋅ x ≡ 1 mod 59 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 59 und 53

=>59 = 1⋅53 + 6
=>53 = 8⋅6 + 5
=>6 = 1⋅5 + 1
=>5 = 5⋅1 + 0

also gilt: ggt(59,53)=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= 6-1⋅5
5= 53-8⋅6 eingesetzt in die Zeile drüber: 1 = 1⋅6 -1⋅(53 -8⋅ 6)
= 1⋅6 -1⋅53 +8⋅ 6)
= -1⋅53 +9⋅ 6 (=1)
6= 59-1⋅53 eingesetzt in die Zeile drüber: 1 = -1⋅53 +9⋅(59 -1⋅ 53)
= -1⋅53 +9⋅59 -9⋅ 53)
= 9⋅59 -10⋅ 53 (=1)

Es gilt also: ggt(59,53)=1 = 9⋅59 -10⋅53

oder wenn man 9⋅59 auf die linke Seite bringt:

1 -9⋅59 = -10⋅53

-10⋅53 = -9⋅59 + 1 |+59⋅53

-10⋅53 + 59⋅53 = -9⋅59 + 59⋅53 + 1

(-10 + 59) ⋅ 53 = (-9 + 53) ⋅ 59 + 1

49⋅53 = 44⋅59 + 1

Es gilt also: 49⋅53 = 44⋅59 +1

Somit 49⋅53 = 1 mod 59

49 ist also das Inverse von 53 mod 59

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden