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: (801 - 16004) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(801 - 16004) mod 4 ≡ (801 mod 4 - 16004 mod 4) mod 4.

801 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 801 = 800+1 = 4 ⋅ 200 +1.

16004 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 16004 = 16000+4 = 4 ⋅ 4000 +4.

Somit gilt:

(801 - 16004) mod 4 ≡ (1 - 0) mod 4 ≡ 1 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (27 ⋅ 66) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(27 ⋅ 66) mod 7 ≡ (27 mod 7 ⋅ 66 mod 7) mod 7.

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

66 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 66 = 63 + 3 = 9 ⋅ 7 + 3 ist.

Somit gilt:

(27 ⋅ 66) mod 7 ≡ (6 ⋅ 3) mod 7 ≡ 18 mod 7 ≡ 4 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 52864 mod 547.

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. 528 -> x
2. mod(x²,547) -> 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: 5281=528

2: 5282=5281+1=5281⋅5281 ≡ 528⋅528=278784 ≡ 361 mod 547

4: 5284=5282+2=5282⋅5282 ≡ 361⋅361=130321 ≡ 135 mod 547

8: 5288=5284+4=5284⋅5284 ≡ 135⋅135=18225 ≡ 174 mod 547

16: 52816=5288+8=5288⋅5288 ≡ 174⋅174=30276 ≡ 191 mod 547

32: 52832=52816+16=52816⋅52816 ≡ 191⋅191=36481 ≡ 379 mod 547

64: 52864=52832+32=52832⋅52832 ≡ 379⋅379=143641 ≡ 327 mod 547

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 262171 mod 617.

Lösung einblenden

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

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

171 = 128+32+8+2+1

1: 2621=262

2: 2622=2621+1=2621⋅2621 ≡ 262⋅262=68644 ≡ 157 mod 617

4: 2624=2622+2=2622⋅2622 ≡ 157⋅157=24649 ≡ 586 mod 617

8: 2628=2624+4=2624⋅2624 ≡ 586⋅586=343396 ≡ 344 mod 617

16: 26216=2628+8=2628⋅2628 ≡ 344⋅344=118336 ≡ 489 mod 617

32: 26232=26216+16=26216⋅26216 ≡ 489⋅489=239121 ≡ 342 mod 617

64: 26264=26232+32=26232⋅26232 ≡ 342⋅342=116964 ≡ 351 mod 617

128: 262128=26264+64=26264⋅26264 ≡ 351⋅351=123201 ≡ 418 mod 617

262171

= 262128+32+8+2+1

= 262128⋅26232⋅2628⋅2622⋅2621

≡ 418 ⋅ 342 ⋅ 344 ⋅ 157 ⋅ 262 mod 617
≡ 142956 ⋅ 344 ⋅ 157 ⋅ 262 mod 617 ≡ 429 ⋅ 344 ⋅ 157 ⋅ 262 mod 617
≡ 147576 ⋅ 157 ⋅ 262 mod 617 ≡ 113 ⋅ 157 ⋅ 262 mod 617
≡ 17741 ⋅ 262 mod 617 ≡ 465 ⋅ 262 mod 617
≡ 121830 mod 617 ≡ 281 mod 617

Es gilt also: 262171 ≡ 281 mod 617

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>89 = 1⋅69 + 20
=>69 = 3⋅20 + 9
=>20 = 2⋅9 + 2
=>9 = 4⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(89,69)=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= 9-4⋅2
2= 20-2⋅9 eingesetzt in die Zeile drüber: 1 = 1⋅9 -4⋅(20 -2⋅ 9)
= 1⋅9 -4⋅20 +8⋅ 9)
= -4⋅20 +9⋅ 9 (=1)
9= 69-3⋅20 eingesetzt in die Zeile drüber: 1 = -4⋅20 +9⋅(69 -3⋅ 20)
= -4⋅20 +9⋅69 -27⋅ 20)
= 9⋅69 -31⋅ 20 (=1)
20= 89-1⋅69 eingesetzt in die Zeile drüber: 1 = 9⋅69 -31⋅(89 -1⋅ 69)
= 9⋅69 -31⋅89 +31⋅ 69)
= -31⋅89 +40⋅ 69 (=1)

Es gilt also: ggt(89,69)=1 = -31⋅89 +40⋅69

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

1 +31⋅89 = +40⋅69

Es gilt also: 40⋅69 = 31⋅89 +1

Somit 40⋅69 = 1 mod 89

40 ist also das Inverse von 69 mod 89

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden