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: (457 + 95) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(457 + 95) mod 9 ≡ (457 mod 9 + 95 mod 9) mod 9.

457 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 457 = 450+7 = 9 ⋅ 50 +7.

95 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 95 = 90+5 = 9 ⋅ 10 +5.

Somit gilt:

(457 + 95) mod 9 ≡ (7 + 5) mod 9 ≡ 12 mod 9 ≡ 3 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (98 ⋅ 59) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(98 ⋅ 59) mod 6 ≡ (98 mod 6 ⋅ 59 mod 6) mod 6.

98 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 98 = 96 + 2 = 16 ⋅ 6 + 2 ist.

59 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 59 = 54 + 5 = 9 ⋅ 6 + 5 ist.

Somit gilt:

(98 ⋅ 59) mod 6 ≡ (2 ⋅ 5) mod 6 ≡ 10 mod 6 ≡ 4 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 523128 mod 827.

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

2: 5232=5231+1=5231⋅5231 ≡ 523⋅523=273529 ≡ 619 mod 827

4: 5234=5232+2=5232⋅5232 ≡ 619⋅619=383161 ≡ 260 mod 827

8: 5238=5234+4=5234⋅5234 ≡ 260⋅260=67600 ≡ 613 mod 827

16: 52316=5238+8=5238⋅5238 ≡ 613⋅613=375769 ≡ 311 mod 827

32: 52332=52316+16=52316⋅52316 ≡ 311⋅311=96721 ≡ 789 mod 827

64: 52364=52332+32=52332⋅52332 ≡ 789⋅789=622521 ≡ 617 mod 827

128: 523128=52364+64=52364⋅52364 ≡ 617⋅617=380689 ≡ 269 mod 827

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 39667 mod 647.

Lösung einblenden

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

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

67 = 64+2+1

1: 3961=396

2: 3962=3961+1=3961⋅3961 ≡ 396⋅396=156816 ≡ 242 mod 647

4: 3964=3962+2=3962⋅3962 ≡ 242⋅242=58564 ≡ 334 mod 647

8: 3968=3964+4=3964⋅3964 ≡ 334⋅334=111556 ≡ 272 mod 647

16: 39616=3968+8=3968⋅3968 ≡ 272⋅272=73984 ≡ 226 mod 647

32: 39632=39616+16=39616⋅39616 ≡ 226⋅226=51076 ≡ 610 mod 647

64: 39664=39632+32=39632⋅39632 ≡ 610⋅610=372100 ≡ 75 mod 647

39667

= 39664+2+1

= 39664⋅3962⋅3961

≡ 75 ⋅ 242 ⋅ 396 mod 647
≡ 18150 ⋅ 396 mod 647 ≡ 34 ⋅ 396 mod 647
≡ 13464 mod 647 ≡ 524 mod 647

Es gilt also: 39667 ≡ 524 mod 647

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 68 ⋅ x ≡ 1 mod 79 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 79 und 68

=>79 = 1⋅68 + 11
=>68 = 6⋅11 + 2
=>11 = 5⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(79,68)=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= 11-5⋅2
2= 68-6⋅11 eingesetzt in die Zeile drüber: 1 = 1⋅11 -5⋅(68 -6⋅ 11)
= 1⋅11 -5⋅68 +30⋅ 11)
= -5⋅68 +31⋅ 11 (=1)
11= 79-1⋅68 eingesetzt in die Zeile drüber: 1 = -5⋅68 +31⋅(79 -1⋅ 68)
= -5⋅68 +31⋅79 -31⋅ 68)
= 31⋅79 -36⋅ 68 (=1)

Es gilt also: ggt(79,68)=1 = 31⋅79 -36⋅68

oder wenn man 31⋅79 auf die linke Seite bringt:

1 -31⋅79 = -36⋅68

-36⋅68 = -31⋅79 + 1 |+79⋅68

-36⋅68 + 79⋅68 = -31⋅79 + 79⋅68 + 1

(-36 + 79) ⋅ 68 = (-31 + 68) ⋅ 79 + 1

43⋅68 = 37⋅79 + 1

Es gilt also: 43⋅68 = 37⋅79 +1

Somit 43⋅68 = 1 mod 79

43 ist also das Inverse von 68 mod 79

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden