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: (3001 + 148) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3001 + 148) mod 3 ≡ (3001 mod 3 + 148 mod 3) mod 3.

3001 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 3001 = 3000+1 = 3 ⋅ 1000 +1.

148 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 148 = 150-2 = 3 ⋅ 50 -2 = 3 ⋅ 50 - 3 + 1.

Somit gilt:

(3001 + 148) mod 3 ≡ (1 + 1) mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (76 ⋅ 55) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(76 ⋅ 55) mod 9 ≡ (76 mod 9 ⋅ 55 mod 9) mod 9.

76 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 76 = 72 + 4 = 8 ⋅ 9 + 4 ist.

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

Somit gilt:

(76 ⋅ 55) mod 9 ≡ (4 ⋅ 1) mod 9 ≡ 4 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 43232 mod 877.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 432 -> x
2. mod(x²,877) -> 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: 4321=432

2: 4322=4321+1=4321⋅4321 ≡ 432⋅432=186624 ≡ 700 mod 877

4: 4324=4322+2=4322⋅4322 ≡ 700⋅700=490000 ≡ 634 mod 877

8: 4328=4324+4=4324⋅4324 ≡ 634⋅634=401956 ≡ 290 mod 877

16: 43216=4328+8=4328⋅4328 ≡ 290⋅290=84100 ≡ 785 mod 877

32: 43232=43216+16=43216⋅43216 ≡ 785⋅785=616225 ≡ 571 mod 877

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 428117 mod 827.

Lösung einblenden

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

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

117 = 64+32+16+4+1

1: 4281=428

2: 4282=4281+1=4281⋅4281 ≡ 428⋅428=183184 ≡ 417 mod 827

4: 4284=4282+2=4282⋅4282 ≡ 417⋅417=173889 ≡ 219 mod 827

8: 4288=4284+4=4284⋅4284 ≡ 219⋅219=47961 ≡ 822 mod 827

16: 42816=4288+8=4288⋅4288 ≡ 822⋅822=675684 ≡ 25 mod 827

32: 42832=42816+16=42816⋅42816 ≡ 25⋅25=625 ≡ 625 mod 827

64: 42864=42832+32=42832⋅42832 ≡ 625⋅625=390625 ≡ 281 mod 827

428117

= 42864+32+16+4+1

= 42864⋅42832⋅42816⋅4284⋅4281

≡ 281 ⋅ 625 ⋅ 25 ⋅ 219 ⋅ 428 mod 827
≡ 175625 ⋅ 25 ⋅ 219 ⋅ 428 mod 827 ≡ 301 ⋅ 25 ⋅ 219 ⋅ 428 mod 827
≡ 7525 ⋅ 219 ⋅ 428 mod 827 ≡ 82 ⋅ 219 ⋅ 428 mod 827
≡ 17958 ⋅ 428 mod 827 ≡ 591 ⋅ 428 mod 827
≡ 252948 mod 827 ≡ 713 mod 827

Es gilt also: 428117 ≡ 713 mod 827

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>79 = 3⋅24 + 7
=>24 = 3⋅7 + 3
=>7 = 2⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(79,24)=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= 7-2⋅3
3= 24-3⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -2⋅(24 -3⋅ 7)
= 1⋅7 -2⋅24 +6⋅ 7)
= -2⋅24 +7⋅ 7 (=1)
7= 79-3⋅24 eingesetzt in die Zeile drüber: 1 = -2⋅24 +7⋅(79 -3⋅ 24)
= -2⋅24 +7⋅79 -21⋅ 24)
= 7⋅79 -23⋅ 24 (=1)

Es gilt also: ggt(79,24)=1 = 7⋅79 -23⋅24

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

1 -7⋅79 = -23⋅24

-23⋅24 = -7⋅79 + 1 |+79⋅24

-23⋅24 + 79⋅24 = -7⋅79 + 79⋅24 + 1

(-23 + 79) ⋅ 24 = (-7 + 24) ⋅ 79 + 1

56⋅24 = 17⋅79 + 1

Es gilt also: 56⋅24 = 17⋅79 +1

Somit 56⋅24 = 1 mod 79

56 ist also das Inverse von 24 mod 79

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden