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: (1501 + 105) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1501 + 105) mod 5 ≡ (1501 mod 5 + 105 mod 5) mod 5.

1501 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 1501 = 1500+1 = 5 ⋅ 300 +1.

105 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 105 = 100+5 = 5 ⋅ 20 +5.

Somit gilt:

(1501 + 105) mod 5 ≡ (1 + 0) mod 5 ≡ 1 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (97 ⋅ 92) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(97 ⋅ 92) mod 8 ≡ (97 mod 8 ⋅ 92 mod 8) mod 8.

97 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 97 = 96 + 1 = 12 ⋅ 8 + 1 ist.

92 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 92 = 88 + 4 = 11 ⋅ 8 + 4 ist.

Somit gilt:

(97 ⋅ 92) mod 8 ≡ (1 ⋅ 4) mod 8 ≡ 4 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 5638 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. 563 -> 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: 5631=563

2: 5632=5631+1=5631⋅5631 ≡ 563⋅563=316969 ≡ 57 mod 683

4: 5634=5632+2=5632⋅5632 ≡ 57⋅57=3249 ≡ 517 mod 683

8: 5638=5634+4=5634⋅5634 ≡ 517⋅517=267289 ≡ 236 mod 683

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 115231 mod 283.

Lösung einblenden

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

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

231 = 128+64+32+4+2+1

1: 1151=115

2: 1152=1151+1=1151⋅1151 ≡ 115⋅115=13225 ≡ 207 mod 283

4: 1154=1152+2=1152⋅1152 ≡ 207⋅207=42849 ≡ 116 mod 283

8: 1158=1154+4=1154⋅1154 ≡ 116⋅116=13456 ≡ 155 mod 283

16: 11516=1158+8=1158⋅1158 ≡ 155⋅155=24025 ≡ 253 mod 283

32: 11532=11516+16=11516⋅11516 ≡ 253⋅253=64009 ≡ 51 mod 283

64: 11564=11532+32=11532⋅11532 ≡ 51⋅51=2601 ≡ 54 mod 283

128: 115128=11564+64=11564⋅11564 ≡ 54⋅54=2916 ≡ 86 mod 283

115231

= 115128+64+32+4+2+1

= 115128⋅11564⋅11532⋅1154⋅1152⋅1151

≡ 86 ⋅ 54 ⋅ 51 ⋅ 116 ⋅ 207 ⋅ 115 mod 283
≡ 4644 ⋅ 51 ⋅ 116 ⋅ 207 ⋅ 115 mod 283 ≡ 116 ⋅ 51 ⋅ 116 ⋅ 207 ⋅ 115 mod 283
≡ 5916 ⋅ 116 ⋅ 207 ⋅ 115 mod 283 ≡ 256 ⋅ 116 ⋅ 207 ⋅ 115 mod 283
≡ 29696 ⋅ 207 ⋅ 115 mod 283 ≡ 264 ⋅ 207 ⋅ 115 mod 283
≡ 54648 ⋅ 115 mod 283 ≡ 29 ⋅ 115 mod 283
≡ 3335 mod 283 ≡ 222 mod 283

Es gilt also: 115231 ≡ 222 mod 283

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>97 = 1⋅58 + 39
=>58 = 1⋅39 + 19
=>39 = 2⋅19 + 1
=>19 = 19⋅1 + 0

also gilt: ggt(97,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= 39-2⋅19
19= 58-1⋅39 eingesetzt in die Zeile drüber: 1 = 1⋅39 -2⋅(58 -1⋅ 39)
= 1⋅39 -2⋅58 +2⋅ 39)
= -2⋅58 +3⋅ 39 (=1)
39= 97-1⋅58 eingesetzt in die Zeile drüber: 1 = -2⋅58 +3⋅(97 -1⋅ 58)
= -2⋅58 +3⋅97 -3⋅ 58)
= 3⋅97 -5⋅ 58 (=1)

Es gilt also: ggt(97,58)=1 = 3⋅97 -5⋅58

oder wenn man 3⋅97 auf die linke Seite bringt:

1 -3⋅97 = -5⋅58

-5⋅58 = -3⋅97 + 1 |+97⋅58

-5⋅58 + 97⋅58 = -3⋅97 + 97⋅58 + 1

(-5 + 97) ⋅ 58 = (-3 + 58) ⋅ 97 + 1

92⋅58 = 55⋅97 + 1

Es gilt also: 92⋅58 = 55⋅97 +1

Somit 92⋅58 = 1 mod 97

92 ist also das Inverse von 58 mod 97

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden