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: (1593 + 32003) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1593 + 32003) mod 8 ≡ (1593 mod 8 + 32003 mod 8) mod 8.

1593 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 1593 = 1600-7 = 8 ⋅ 200 -7 = 8 ⋅ 200 - 8 + 1.

32003 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 32003 = 32000+3 = 8 ⋅ 4000 +3.

Somit gilt:

(1593 + 32003) mod 8 ≡ (1 + 3) mod 8 ≡ 4 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (97 ⋅ 97) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(97 ⋅ 97) mod 9 ≡ (97 mod 9 ⋅ 97 mod 9) mod 9.

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

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

Somit gilt:

(97 ⋅ 97) mod 9 ≡ (7 ⋅ 7) mod 9 ≡ 49 mod 9 ≡ 4 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 332128 mod 941.

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. 332 -> x
2. mod(x²,941) -> 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: 3321=332

2: 3322=3321+1=3321⋅3321 ≡ 332⋅332=110224 ≡ 127 mod 941

4: 3324=3322+2=3322⋅3322 ≡ 127⋅127=16129 ≡ 132 mod 941

8: 3328=3324+4=3324⋅3324 ≡ 132⋅132=17424 ≡ 486 mod 941

16: 33216=3328+8=3328⋅3328 ≡ 486⋅486=236196 ≡ 5 mod 941

32: 33232=33216+16=33216⋅33216 ≡ 5⋅5=25 ≡ 25 mod 941

64: 33264=33232+32=33232⋅33232 ≡ 25⋅25=625 ≡ 625 mod 941

128: 332128=33264+64=33264⋅33264 ≡ 625⋅625=390625 ≡ 110 mod 941

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 232194 mod 487.

Lösung einblenden

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

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

194 = 128+64+2

1: 2321=232

2: 2322=2321+1=2321⋅2321 ≡ 232⋅232=53824 ≡ 254 mod 487

4: 2324=2322+2=2322⋅2322 ≡ 254⋅254=64516 ≡ 232 mod 487

8: 2328=2324+4=2324⋅2324 ≡ 232⋅232=53824 ≡ 254 mod 487

16: 23216=2328+8=2328⋅2328 ≡ 254⋅254=64516 ≡ 232 mod 487

32: 23232=23216+16=23216⋅23216 ≡ 232⋅232=53824 ≡ 254 mod 487

64: 23264=23232+32=23232⋅23232 ≡ 254⋅254=64516 ≡ 232 mod 487

128: 232128=23264+64=23264⋅23264 ≡ 232⋅232=53824 ≡ 254 mod 487

232194

= 232128+64+2

= 232128⋅23264⋅2322

≡ 254 ⋅ 232 ⋅ 254 mod 487
≡ 58928 ⋅ 254 mod 487 ≡ 1 ⋅ 254 mod 487
≡ 254 mod 487

Es gilt also: 232194 ≡ 254 mod 487

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 40 ⋅ x ≡ 1 mod 59 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 59 und 40

=>59 = 1⋅40 + 19
=>40 = 2⋅19 + 2
=>19 = 9⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(59,40)=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= 19-9⋅2
2= 40-2⋅19 eingesetzt in die Zeile drüber: 1 = 1⋅19 -9⋅(40 -2⋅ 19)
= 1⋅19 -9⋅40 +18⋅ 19)
= -9⋅40 +19⋅ 19 (=1)
19= 59-1⋅40 eingesetzt in die Zeile drüber: 1 = -9⋅40 +19⋅(59 -1⋅ 40)
= -9⋅40 +19⋅59 -19⋅ 40)
= 19⋅59 -28⋅ 40 (=1)

Es gilt also: ggt(59,40)=1 = 19⋅59 -28⋅40

oder wenn man 19⋅59 auf die linke Seite bringt:

1 -19⋅59 = -28⋅40

-28⋅40 = -19⋅59 + 1 |+59⋅40

-28⋅40 + 59⋅40 = -19⋅59 + 59⋅40 + 1

(-28 + 59) ⋅ 40 = (-19 + 40) ⋅ 59 + 1

31⋅40 = 21⋅59 + 1

Es gilt also: 31⋅40 = 21⋅59 +1

Somit 31⋅40 = 1 mod 59

31 ist also das Inverse von 40 mod 59

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden