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: (240 - 153) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(240 - 153) mod 8 ≡ (240 mod 8 - 153 mod 8) mod 8.

240 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 240 = 240+0 = 8 ⋅ 30 +0.

153 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 153 = 160-7 = 8 ⋅ 20 -7 = 8 ⋅ 20 - 8 + 1.

Somit gilt:

(240 - 153) mod 8 ≡ (0 - 1) mod 8 ≡ -1 mod 8 ≡ 7 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (97 ⋅ 95) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(97 ⋅ 95) mod 10 ≡ (97 mod 10 ⋅ 95 mod 10) mod 10.

97 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 97 = 90 + 7 = 9 ⋅ 10 + 7 ist.

95 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 95 = 90 + 5 = 9 ⋅ 10 + 5 ist.

Somit gilt:

(97 ⋅ 95) mod 10 ≡ (7 ⋅ 5) mod 10 ≡ 35 mod 10 ≡ 5 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 20616 mod 401.

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. 206 -> x
2. mod(x²,401) -> 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: 2061=206

2: 2062=2061+1=2061⋅2061 ≡ 206⋅206=42436 ≡ 331 mod 401

4: 2064=2062+2=2062⋅2062 ≡ 331⋅331=109561 ≡ 88 mod 401

8: 2068=2064+4=2064⋅2064 ≡ 88⋅88=7744 ≡ 125 mod 401

16: 20616=2068+8=2068⋅2068 ≡ 125⋅125=15625 ≡ 387 mod 401

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 536180 mod 823.

Lösung einblenden

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

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

180 = 128+32+16+4

1: 5361=536

2: 5362=5361+1=5361⋅5361 ≡ 536⋅536=287296 ≡ 69 mod 823

4: 5364=5362+2=5362⋅5362 ≡ 69⋅69=4761 ≡ 646 mod 823

8: 5368=5364+4=5364⋅5364 ≡ 646⋅646=417316 ≡ 55 mod 823

16: 53616=5368+8=5368⋅5368 ≡ 55⋅55=3025 ≡ 556 mod 823

32: 53632=53616+16=53616⋅53616 ≡ 556⋅556=309136 ≡ 511 mod 823

64: 53664=53632+32=53632⋅53632 ≡ 511⋅511=261121 ≡ 230 mod 823

128: 536128=53664+64=53664⋅53664 ≡ 230⋅230=52900 ≡ 228 mod 823

536180

= 536128+32+16+4

= 536128⋅53632⋅53616⋅5364

≡ 228 ⋅ 511 ⋅ 556 ⋅ 646 mod 823
≡ 116508 ⋅ 556 ⋅ 646 mod 823 ≡ 465 ⋅ 556 ⋅ 646 mod 823
≡ 258540 ⋅ 646 mod 823 ≡ 118 ⋅ 646 mod 823
≡ 76228 mod 823 ≡ 512 mod 823

Es gilt also: 536180 ≡ 512 mod 823

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>89 = 1⋅51 + 38
=>51 = 1⋅38 + 13
=>38 = 2⋅13 + 12
=>13 = 1⋅12 + 1
=>12 = 12⋅1 + 0

also gilt: ggt(89,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= 13-1⋅12
12= 38-2⋅13 eingesetzt in die Zeile drüber: 1 = 1⋅13 -1⋅(38 -2⋅ 13)
= 1⋅13 -1⋅38 +2⋅ 13)
= -1⋅38 +3⋅ 13 (=1)
13= 51-1⋅38 eingesetzt in die Zeile drüber: 1 = -1⋅38 +3⋅(51 -1⋅ 38)
= -1⋅38 +3⋅51 -3⋅ 38)
= 3⋅51 -4⋅ 38 (=1)
38= 89-1⋅51 eingesetzt in die Zeile drüber: 1 = 3⋅51 -4⋅(89 -1⋅ 51)
= 3⋅51 -4⋅89 +4⋅ 51)
= -4⋅89 +7⋅ 51 (=1)

Es gilt also: ggt(89,51)=1 = -4⋅89 +7⋅51

oder wenn man -4⋅89 auf die linke Seite bringt:

1 +4⋅89 = +7⋅51

Es gilt also: 7⋅51 = 4⋅89 +1

Somit 7⋅51 = 1 mod 89

7 ist also das Inverse von 51 mod 89

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden