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: (3503 - 344) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3503 - 344) mod 7 ≡ (3503 mod 7 - 344 mod 7) mod 7.

3503 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 3503 = 3500+3 = 7 ⋅ 500 +3.

344 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 344 = 350-6 = 7 ⋅ 50 -6 = 7 ⋅ 50 - 7 + 1.

Somit gilt:

(3503 - 344) mod 7 ≡ (3 - 1) mod 7 ≡ 2 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (94 ⋅ 64) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 64) mod 7 ≡ (94 mod 7 ⋅ 64 mod 7) mod 7.

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

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

Somit gilt:

(94 ⋅ 64) mod 7 ≡ (3 ⋅ 1) mod 7 ≡ 3 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 130128 mod 239.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 130 -> x
2. mod(x²,239) -> 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: 1301=130

2: 1302=1301+1=1301⋅1301 ≡ 130⋅130=16900 ≡ 170 mod 239

4: 1304=1302+2=1302⋅1302 ≡ 170⋅170=28900 ≡ 220 mod 239

8: 1308=1304+4=1304⋅1304 ≡ 220⋅220=48400 ≡ 122 mod 239

16: 13016=1308+8=1308⋅1308 ≡ 122⋅122=14884 ≡ 66 mod 239

32: 13032=13016+16=13016⋅13016 ≡ 66⋅66=4356 ≡ 54 mod 239

64: 13064=13032+32=13032⋅13032 ≡ 54⋅54=2916 ≡ 48 mod 239

128: 130128=13064+64=13064⋅13064 ≡ 48⋅48=2304 ≡ 153 mod 239

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 538236 mod 829.

Lösung einblenden

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

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

236 = 128+64+32+8+4

1: 5381=538

2: 5382=5381+1=5381⋅5381 ≡ 538⋅538=289444 ≡ 123 mod 829

4: 5384=5382+2=5382⋅5382 ≡ 123⋅123=15129 ≡ 207 mod 829

8: 5388=5384+4=5384⋅5384 ≡ 207⋅207=42849 ≡ 570 mod 829

16: 53816=5388+8=5388⋅5388 ≡ 570⋅570=324900 ≡ 761 mod 829

32: 53832=53816+16=53816⋅53816 ≡ 761⋅761=579121 ≡ 479 mod 829

64: 53864=53832+32=53832⋅53832 ≡ 479⋅479=229441 ≡ 637 mod 829

128: 538128=53864+64=53864⋅53864 ≡ 637⋅637=405769 ≡ 388 mod 829

538236

= 538128+64+32+8+4

= 538128⋅53864⋅53832⋅5388⋅5384

388 ⋅ 637 ⋅ 479 ⋅ 570 ⋅ 207 mod 829
247156 ⋅ 479 ⋅ 570 ⋅ 207 mod 829 ≡ 114 ⋅ 479 ⋅ 570 ⋅ 207 mod 829
54606 ⋅ 570 ⋅ 207 mod 829 ≡ 721 ⋅ 570 ⋅ 207 mod 829
410970 ⋅ 207 mod 829 ≡ 615 ⋅ 207 mod 829
127305 mod 829 ≡ 468 mod 829

Es gilt also: 538236 ≡ 468 mod 829

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>53 = 1⋅46 + 7
=>46 = 6⋅7 + 4
=>7 = 1⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

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

Es gilt also: ggt(53,46)=1 = -13⋅53 +15⋅46

oder wenn man -13⋅53 auf die linke Seite bringt:

1 +13⋅53 = +15⋅46

Es gilt also: 15⋅46 = 13⋅53 +1

Somit 15⋅46 = 1 mod 53

15 ist also das Inverse von 46 mod 53

Schlüsselpaar für RSA

Beispiel:

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