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: (2397 - 239) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2397 - 239) mod 6 ≡ (2397 mod 6 - 239 mod 6) mod 6.

2397 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 2397 = 2400-3 = 6 ⋅ 400 -3 = 6 ⋅ 400 - 6 + 3.

239 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 239 = 240-1 = 6 ⋅ 40 -1 = 6 ⋅ 40 - 6 + 5.

Somit gilt:

(2397 - 239) mod 6 ≡ (3 - 5) mod 6 ≡ -2 mod 6 ≡ 4 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (88 ⋅ 69) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(88 ⋅ 69) mod 6 ≡ (88 mod 6 ⋅ 69 mod 6) mod 6.

88 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 88 = 84 + 4 = 14 ⋅ 6 + 4 ist.

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

Somit gilt:

(88 ⋅ 69) mod 6 ≡ (4 ⋅ 3) mod 6 ≡ 12 mod 6 ≡ 0 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 47464 mod 827.

Lösung einblenden

Die 64 im Exponent ist ja ein reine 2er-Potenz (26).

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. 474 -> x
2. mod(x²,827) -> 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: 4741=474

2: 4742=4741+1=4741⋅4741 ≡ 474⋅474=224676 ≡ 559 mod 827

4: 4744=4742+2=4742⋅4742 ≡ 559⋅559=312481 ≡ 702 mod 827

8: 4748=4744+4=4744⋅4744 ≡ 702⋅702=492804 ≡ 739 mod 827

16: 47416=4748+8=4748⋅4748 ≡ 739⋅739=546121 ≡ 301 mod 827

32: 47432=47416+16=47416⋅47416 ≡ 301⋅301=90601 ≡ 458 mod 827

64: 47464=47432+32=47432⋅47432 ≡ 458⋅458=209764 ≡ 533 mod 827

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 216248 mod 347.

Lösung einblenden

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

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

248 = 128+64+32+16+8

1: 2161=216

2: 2162=2161+1=2161⋅2161 ≡ 216⋅216=46656 ≡ 158 mod 347

4: 2164=2162+2=2162⋅2162 ≡ 158⋅158=24964 ≡ 327 mod 347

8: 2168=2164+4=2164⋅2164 ≡ 327⋅327=106929 ≡ 53 mod 347

16: 21616=2168+8=2168⋅2168 ≡ 53⋅53=2809 ≡ 33 mod 347

32: 21632=21616+16=21616⋅21616 ≡ 33⋅33=1089 ≡ 48 mod 347

64: 21664=21632+32=21632⋅21632 ≡ 48⋅48=2304 ≡ 222 mod 347

128: 216128=21664+64=21664⋅21664 ≡ 222⋅222=49284 ≡ 10 mod 347

216248

= 216128+64+32+16+8

= 216128⋅21664⋅21632⋅21616⋅2168

10 ⋅ 222 ⋅ 48 ⋅ 33 ⋅ 53 mod 347
2220 ⋅ 48 ⋅ 33 ⋅ 53 mod 347 ≡ 138 ⋅ 48 ⋅ 33 ⋅ 53 mod 347
6624 ⋅ 33 ⋅ 53 mod 347 ≡ 31 ⋅ 33 ⋅ 53 mod 347
1023 ⋅ 53 mod 347 ≡ 329 ⋅ 53 mod 347
17437 mod 347 ≡ 87 mod 347

Es gilt also: 216248 ≡ 87 mod 347

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>71 = 1⋅53 + 18
=>53 = 2⋅18 + 17
=>18 = 1⋅17 + 1
=>17 = 17⋅1 + 0

also gilt: ggt(71,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= 18-1⋅17
17= 53-2⋅18 eingesetzt in die Zeile drüber: 1 = 1⋅18 -1⋅(53 -2⋅ 18)
= 1⋅18 -1⋅53 +2⋅ 18)
= -1⋅53 +3⋅ 18 (=1)
18= 71-1⋅53 eingesetzt in die Zeile drüber: 1 = -1⋅53 +3⋅(71 -1⋅ 53)
= -1⋅53 +3⋅71 -3⋅ 53)
= 3⋅71 -4⋅ 53 (=1)

Es gilt also: ggt(71,53)=1 = 3⋅71 -4⋅53

oder wenn man 3⋅71 auf die linke Seite bringt:

1 -3⋅71 = -4⋅53

-4⋅53 = -3⋅71 + 1 |+71⋅53

-4⋅53 + 71⋅53 = -3⋅71 + 71⋅53 + 1

(-4 + 71) ⋅ 53 = (-3 + 53) ⋅ 71 + 1

67⋅53 = 50⋅71 + 1

Es gilt also: 67⋅53 = 50⋅71 +1

Somit 67⋅53 = 1 mod 71

67 ist also das Inverse von 53 mod 71

Schlüsselpaar für RSA

Beispiel:

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