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: (15002 - 2495) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(15002 - 2495) mod 5 ≡ (15002 mod 5 - 2495 mod 5) mod 5.

15002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 15002 = 15000+2 = 5 ⋅ 3000 +2.

2495 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2495 = 2400+95 = 5 ⋅ 480 +95.

Somit gilt:

(15002 - 2495) mod 5 ≡ (2 - 0) mod 5 ≡ 2 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (73 ⋅ 69) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(73 ⋅ 69) mod 9 ≡ (73 mod 9 ⋅ 69 mod 9) mod 9.

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

69 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 69 = 63 + 6 = 7 ⋅ 9 + 6 ist.

Somit gilt:

(73 ⋅ 69) mod 9 ≡ (1 ⋅ 6) mod 9 ≡ 6 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 29716 mod 853.

Lösung einblenden

Die 16 im Exponent ist ja ein reine 2er-Potenz (24).

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. 297 -> x
2. mod(x²,853) -> 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: 2971=297

2: 2972=2971+1=2971⋅2971 ≡ 297⋅297=88209 ≡ 350 mod 853

4: 2974=2972+2=2972⋅2972 ≡ 350⋅350=122500 ≡ 521 mod 853

8: 2978=2974+4=2974⋅2974 ≡ 521⋅521=271441 ≡ 187 mod 853

16: 29716=2978+8=2978⋅2978 ≡ 187⋅187=34969 ≡ 849 mod 853

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 47774 mod 733.

Lösung einblenden

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

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

74 = 64+8+2

1: 4771=477

2: 4772=4771+1=4771⋅4771 ≡ 477⋅477=227529 ≡ 299 mod 733

4: 4774=4772+2=4772⋅4772 ≡ 299⋅299=89401 ≡ 708 mod 733

8: 4778=4774+4=4774⋅4774 ≡ 708⋅708=501264 ≡ 625 mod 733

16: 47716=4778+8=4778⋅4778 ≡ 625⋅625=390625 ≡ 669 mod 733

32: 47732=47716+16=47716⋅47716 ≡ 669⋅669=447561 ≡ 431 mod 733

64: 47764=47732+32=47732⋅47732 ≡ 431⋅431=185761 ≡ 312 mod 733

47774

= 47764+8+2

= 47764⋅4778⋅4772

312 ⋅ 625 ⋅ 299 mod 733
195000 ⋅ 299 mod 733 ≡ 22 ⋅ 299 mod 733
6578 mod 733 ≡ 714 mod 733

Es gilt also: 47774 ≡ 714 mod 733

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 58 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 58

=>67 = 1⋅58 + 9
=>58 = 6⋅9 + 4
=>9 = 2⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(67,58)=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= 9-2⋅4
4= 58-6⋅9 eingesetzt in die Zeile drüber: 1 = 1⋅9 -2⋅(58 -6⋅ 9)
= 1⋅9 -2⋅58 +12⋅ 9)
= -2⋅58 +13⋅ 9 (=1)
9= 67-1⋅58 eingesetzt in die Zeile drüber: 1 = -2⋅58 +13⋅(67 -1⋅ 58)
= -2⋅58 +13⋅67 -13⋅ 58)
= 13⋅67 -15⋅ 58 (=1)

Es gilt also: ggt(67,58)=1 = 13⋅67 -15⋅58

oder wenn man 13⋅67 auf die linke Seite bringt:

1 -13⋅67 = -15⋅58

-15⋅58 = -13⋅67 + 1 |+67⋅58

-15⋅58 + 67⋅58 = -13⋅67 + 67⋅58 + 1

(-15 + 67) ⋅ 58 = (-13 + 58) ⋅ 67 + 1

52⋅58 = 45⋅67 + 1

Es gilt also: 52⋅58 = 45⋅67 +1

Somit 52⋅58 = 1 mod 67

52 ist also das Inverse von 58 mod 67

Schlüsselpaar für RSA

Beispiel:

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