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: (24002 - 39997) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(24002 - 39997) mod 8 ≡ (24002 mod 8 - 39997 mod 8) mod 8.

24002 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 24002 = 24000+2 = 8 ⋅ 3000 +2.

39997 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 39997 = 39000+997 = 8 ⋅ 4875 +997.

Somit gilt:

(24002 - 39997) mod 8 ≡ (2 - 5) mod 8 ≡ -3 mod 8 ≡ 5 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (68 ⋅ 52) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 ⋅ 52) mod 8 ≡ (68 mod 8 ⋅ 52 mod 8) mod 8.

68 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 68 = 64 + 4 = 8 ⋅ 8 + 4 ist.

52 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 52 = 48 + 4 = 6 ⋅ 8 + 4 ist.

Somit gilt:

(68 ⋅ 52) mod 8 ≡ (4 ⋅ 4) mod 8 ≡ 16 mod 8 ≡ 0 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 6178 mod 683.

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. 617 -> x
2. mod(x²,683) -> 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: 6171=617

2: 6172=6171+1=6171⋅6171 ≡ 617⋅617=380689 ≡ 258 mod 683

4: 6174=6172+2=6172⋅6172 ≡ 258⋅258=66564 ≡ 313 mod 683

8: 6178=6174+4=6174⋅6174 ≡ 313⋅313=97969 ≡ 300 mod 683

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 249134 mod 557.

Lösung einblenden

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

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

134 = 128+4+2

1: 2491=249

2: 2492=2491+1=2491⋅2491 ≡ 249⋅249=62001 ≡ 174 mod 557

4: 2494=2492+2=2492⋅2492 ≡ 174⋅174=30276 ≡ 198 mod 557

8: 2498=2494+4=2494⋅2494 ≡ 198⋅198=39204 ≡ 214 mod 557

16: 24916=2498+8=2498⋅2498 ≡ 214⋅214=45796 ≡ 122 mod 557

32: 24932=24916+16=24916⋅24916 ≡ 122⋅122=14884 ≡ 402 mod 557

64: 24964=24932+32=24932⋅24932 ≡ 402⋅402=161604 ≡ 74 mod 557

128: 249128=24964+64=24964⋅24964 ≡ 74⋅74=5476 ≡ 463 mod 557

249134

= 249128+4+2

= 249128⋅2494⋅2492

≡ 463 ⋅ 198 ⋅ 174 mod 557
≡ 91674 ⋅ 174 mod 557 ≡ 326 ⋅ 174 mod 557
≡ 56724 mod 557 ≡ 467 mod 557

Es gilt also: 249134 ≡ 467 mod 557

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 = 101 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.

Lösung einblenden