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: (122 + 65) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(122 + 65) mod 6 ≡ (122 mod 6 + 65 mod 6) mod 6.

122 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 122 = 120+2 = 6 ⋅ 20 +2.

65 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 65 = 60+5 = 6 ⋅ 10 +5.

Somit gilt:

(122 + 65) mod 6 ≡ (2 + 5) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (82 ⋅ 29) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(82 ⋅ 29) mod 7 ≡ (82 mod 7 ⋅ 29 mod 7) mod 7.

82 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 82 = 77 + 5 = 11 ⋅ 7 + 5 ist.

29 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 29 = 28 + 1 = 4 ⋅ 7 + 1 ist.

Somit gilt:

(82 ⋅ 29) mod 7 ≡ (5 ⋅ 1) mod 7 ≡ 5 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 3548 mod 463.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 354 -> x
2. mod(x²,463) -> 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: 3541=354

2: 3542=3541+1=3541⋅3541 ≡ 354⋅354=125316 ≡ 306 mod 463

4: 3544=3542+2=3542⋅3542 ≡ 306⋅306=93636 ≡ 110 mod 463

8: 3548=3544+4=3544⋅3544 ≡ 110⋅110=12100 ≡ 62 mod 463

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 639170 mod 739.

Lösung einblenden

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

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

170 = 128+32+8+2

1: 6391=639

2: 6392=6391+1=6391⋅6391 ≡ 639⋅639=408321 ≡ 393 mod 739

4: 6394=6392+2=6392⋅6392 ≡ 393⋅393=154449 ≡ 737 mod 739

8: 6398=6394+4=6394⋅6394 ≡ 737⋅737=543169 ≡ 4 mod 739

16: 63916=6398+8=6398⋅6398 ≡ 4⋅4=16 ≡ 16 mod 739

32: 63932=63916+16=63916⋅63916 ≡ 16⋅16=256 ≡ 256 mod 739

64: 63964=63932+32=63932⋅63932 ≡ 256⋅256=65536 ≡ 504 mod 739

128: 639128=63964+64=63964⋅63964 ≡ 504⋅504=254016 ≡ 539 mod 739

639170

= 639128+32+8+2

= 639128⋅63932⋅6398⋅6392

≡ 539 ⋅ 256 ⋅ 4 ⋅ 393 mod 739
≡ 137984 ⋅ 4 ⋅ 393 mod 739 ≡ 530 ⋅ 4 ⋅ 393 mod 739
≡ 2120 ⋅ 393 mod 739 ≡ 642 ⋅ 393 mod 739
≡ 252306 mod 739 ≡ 307 mod 739

Es gilt also: 639170 ≡ 307 mod 739

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 50 ⋅ x ≡ 1 mod 61 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 61 und 50

=>61 = 1⋅50 + 11
=>50 = 4⋅11 + 6
=>11 = 1⋅6 + 5
=>6 = 1⋅5 + 1
=>5 = 5⋅1 + 0

also gilt: ggt(61,50)=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= 6-1⋅5
5= 11-1⋅6 eingesetzt in die Zeile drüber: 1 = 1⋅6 -1⋅(11 -1⋅ 6)
= 1⋅6 -1⋅11 +1⋅ 6)
= -1⋅11 +2⋅ 6 (=1)
6= 50-4⋅11 eingesetzt in die Zeile drüber: 1 = -1⋅11 +2⋅(50 -4⋅ 11)
= -1⋅11 +2⋅50 -8⋅ 11)
= 2⋅50 -9⋅ 11 (=1)
11= 61-1⋅50 eingesetzt in die Zeile drüber: 1 = 2⋅50 -9⋅(61 -1⋅ 50)
= 2⋅50 -9⋅61 +9⋅ 50)
= -9⋅61 +11⋅ 50 (=1)

Es gilt also: ggt(61,50)=1 = -9⋅61 +11⋅50

oder wenn man -9⋅61 auf die linke Seite bringt:

1 +9⋅61 = +11⋅50

Es gilt also: 11⋅50 = 9⋅61 +1

Somit 11⋅50 = 1 mod 61

11 ist also das Inverse von 50 mod 61

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden