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: (2497 + 247) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2497 + 247) mod 5 ≡ (2497 mod 5 + 247 mod 5) mod 5.

2497 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 2497 = 2400+97 = 5 ⋅ 480 +97.

247 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 247 = 240+7 = 5 ⋅ 48 +7.

Somit gilt:

(2497 + 247) mod 5 ≡ (2 + 2) mod 5 ≡ 4 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (57 ⋅ 15) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(57 ⋅ 15) mod 8 ≡ (57 mod 8 ⋅ 15 mod 8) mod 8.

57 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 57 = 56 + 1 = 7 ⋅ 8 + 1 ist.

15 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 15 = 8 + 7 = 1 ⋅ 8 + 7 ist.

Somit gilt:

(57 ⋅ 15) mod 8 ≡ (1 ⋅ 7) mod 8 ≡ 7 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 40764 mod 487.

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. 407 -> x
2. mod(x²,487) -> 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: 4071=407

2: 4072=4071+1=4071⋅4071 ≡ 407⋅407=165649 ≡ 69 mod 487

4: 4074=4072+2=4072⋅4072 ≡ 69⋅69=4761 ≡ 378 mod 487

8: 4078=4074+4=4074⋅4074 ≡ 378⋅378=142884 ≡ 193 mod 487

16: 40716=4078+8=4078⋅4078 ≡ 193⋅193=37249 ≡ 237 mod 487

32: 40732=40716+16=40716⋅40716 ≡ 237⋅237=56169 ≡ 164 mod 487

64: 40764=40732+32=40732⋅40732 ≡ 164⋅164=26896 ≡ 111 mod 487

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 457180 mod 463.

Lösung einblenden

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

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

180 = 128+32+16+4

1: 4571=457

2: 4572=4571+1=4571⋅4571 ≡ 457⋅457=208849 ≡ 36 mod 463

4: 4574=4572+2=4572⋅4572 ≡ 36⋅36=1296 ≡ 370 mod 463

8: 4578=4574+4=4574⋅4574 ≡ 370⋅370=136900 ≡ 315 mod 463

16: 45716=4578+8=4578⋅4578 ≡ 315⋅315=99225 ≡ 143 mod 463

32: 45732=45716+16=45716⋅45716 ≡ 143⋅143=20449 ≡ 77 mod 463

64: 45764=45732+32=45732⋅45732 ≡ 77⋅77=5929 ≡ 373 mod 463

128: 457128=45764+64=45764⋅45764 ≡ 373⋅373=139129 ≡ 229 mod 463

457180

= 457128+32+16+4

= 457128⋅45732⋅45716⋅4574

≡ 229 ⋅ 77 ⋅ 143 ⋅ 370 mod 463
≡ 17633 ⋅ 143 ⋅ 370 mod 463 ≡ 39 ⋅ 143 ⋅ 370 mod 463
≡ 5577 ⋅ 370 mod 463 ≡ 21 ⋅ 370 mod 463
≡ 7770 mod 463 ≡ 362 mod 463

Es gilt also: 457180 ≡ 362 mod 463

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>71 = 1⋅59 + 12
=>59 = 4⋅12 + 11
=>12 = 1⋅11 + 1
=>11 = 11⋅1 + 0

also gilt: ggt(71,59)=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= 12-1⋅11
11= 59-4⋅12 eingesetzt in die Zeile drüber: 1 = 1⋅12 -1⋅(59 -4⋅ 12)
= 1⋅12 -1⋅59 +4⋅ 12)
= -1⋅59 +5⋅ 12 (=1)
12= 71-1⋅59 eingesetzt in die Zeile drüber: 1 = -1⋅59 +5⋅(71 -1⋅ 59)
= -1⋅59 +5⋅71 -5⋅ 59)
= 5⋅71 -6⋅ 59 (=1)

Es gilt also: ggt(71,59)=1 = 5⋅71 -6⋅59

oder wenn man 5⋅71 auf die linke Seite bringt:

1 -5⋅71 = -6⋅59

-6⋅59 = -5⋅71 + 1 |+71⋅59

-6⋅59 + 71⋅59 = -5⋅71 + 71⋅59 + 1

(-6 + 71) ⋅ 59 = (-5 + 59) ⋅ 71 + 1

65⋅59 = 54⋅71 + 1

Es gilt also: 65⋅59 = 54⋅71 +1

Somit 65⋅59 = 1 mod 71

65 ist also das Inverse von 59 mod 71

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden