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: (303 - 1800) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(303 - 1800) mod 6 ≡ (303 mod 6 - 1800 mod 6) mod 6.

303 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 303 = 300+3 = 6 ⋅ 50 +3.

1800 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 1800 = 1800+0 = 6 ⋅ 300 +0.

Somit gilt:

(303 - 1800) mod 6 ≡ (3 - 0) mod 6 ≡ 3 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (94 ⋅ 65) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 65) mod 11 ≡ (94 mod 11 ⋅ 65 mod 11) mod 11.

94 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 94 = 88 + 6 = 8 ⋅ 11 + 6 ist.

65 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 65 = 55 + 10 = 5 ⋅ 11 + 10 ist.

Somit gilt:

(94 ⋅ 65) mod 11 ≡ (6 ⋅ 10) mod 11 ≡ 60 mod 11 ≡ 5 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 41264 mod 523.

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. 412 -> x
2. mod(x²,523) -> 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: 4121=412

2: 4122=4121+1=4121⋅4121 ≡ 412⋅412=169744 ≡ 292 mod 523

4: 4124=4122+2=4122⋅4122 ≡ 292⋅292=85264 ≡ 15 mod 523

8: 4128=4124+4=4124⋅4124 ≡ 15⋅15=225 ≡ 225 mod 523

16: 41216=4128+8=4128⋅4128 ≡ 225⋅225=50625 ≡ 417 mod 523

32: 41232=41216+16=41216⋅41216 ≡ 417⋅417=173889 ≡ 253 mod 523

64: 41264=41232+32=41232⋅41232 ≡ 253⋅253=64009 ≡ 203 mod 523

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 372247 mod 953.

Lösung einblenden

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

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

247 = 128+64+32+16+4+2+1

1: 3721=372

2: 3722=3721+1=3721⋅3721 ≡ 372⋅372=138384 ≡ 199 mod 953

4: 3724=3722+2=3722⋅3722 ≡ 199⋅199=39601 ≡ 528 mod 953

8: 3728=3724+4=3724⋅3724 ≡ 528⋅528=278784 ≡ 508 mod 953

16: 37216=3728+8=3728⋅3728 ≡ 508⋅508=258064 ≡ 754 mod 953

32: 37232=37216+16=37216⋅37216 ≡ 754⋅754=568516 ≡ 528 mod 953

64: 37264=37232+32=37232⋅37232 ≡ 528⋅528=278784 ≡ 508 mod 953

128: 372128=37264+64=37264⋅37264 ≡ 508⋅508=258064 ≡ 754 mod 953

372247

= 372128+64+32+16+4+2+1

= 372128⋅37264⋅37232⋅37216⋅3724⋅3722⋅3721

754 ⋅ 508 ⋅ 528 ⋅ 754 ⋅ 528 ⋅ 199 ⋅ 372 mod 953
383032 ⋅ 528 ⋅ 754 ⋅ 528 ⋅ 199 ⋅ 372 mod 953 ≡ 879 ⋅ 528 ⋅ 754 ⋅ 528 ⋅ 199 ⋅ 372 mod 953
464112 ⋅ 754 ⋅ 528 ⋅ 199 ⋅ 372 mod 953 ≡ 1 ⋅ 754 ⋅ 528 ⋅ 199 ⋅ 372 mod 953
754 ⋅ 528 ⋅ 199 ⋅ 372 mod 953
398112 ⋅ 199 ⋅ 372 mod 953 ≡ 711 ⋅ 199 ⋅ 372 mod 953
141489 ⋅ 372 mod 953 ≡ 445 ⋅ 372 mod 953
165540 mod 953 ≡ 671 mod 953

Es gilt also: 372247 ≡ 671 mod 953

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 38 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 38

=>73 = 1⋅38 + 35
=>38 = 1⋅35 + 3
=>35 = 11⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

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

Es gilt also: ggt(73,38)=1 = -13⋅73 +25⋅38

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

1 +13⋅73 = +25⋅38

Es gilt also: 25⋅38 = 13⋅73 +1

Somit 25⋅38 = 1 mod 73

25 ist also das Inverse von 38 mod 73

Schlüsselpaar für RSA

Beispiel:

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