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: (392 - 248) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(392 - 248) mod 8 ≡ (392 mod 8 - 248 mod 8) mod 8.

392 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 392 = 400-8 = 8 ⋅ 50 -8 = 8 ⋅ 50 - 8 + 0.

248 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 248 = 240+8 = 8 ⋅ 30 +8.

Somit gilt:

(392 - 248) mod 8 ≡ (0 - 0) mod 8 ≡ 0 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (94 ⋅ 85) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 85) mod 5 ≡ (94 mod 5 ⋅ 85 mod 5) mod 5.

94 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 94 = 90 + 4 = 18 ⋅ 5 + 4 ist.

85 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 85 = 85 + 0 = 17 ⋅ 5 + 0 ist.

Somit gilt:

(94 ⋅ 85) mod 5 ≡ (4 ⋅ 0) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 13364 mod 293.

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. 133 -> x
2. mod(x²,293) -> 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: 1331=133

2: 1332=1331+1=1331⋅1331 ≡ 133⋅133=17689 ≡ 109 mod 293

4: 1334=1332+2=1332⋅1332 ≡ 109⋅109=11881 ≡ 161 mod 293

8: 1338=1334+4=1334⋅1334 ≡ 161⋅161=25921 ≡ 137 mod 293

16: 13316=1338+8=1338⋅1338 ≡ 137⋅137=18769 ≡ 17 mod 293

32: 13332=13316+16=13316⋅13316 ≡ 17⋅17=289 ≡ 289 mod 293

64: 13364=13332+32=13332⋅13332 ≡ 289⋅289=83521 ≡ 16 mod 293

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 113203 mod 313.

Lösung einblenden

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

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

203 = 128+64+8+2+1

1: 1131=113

2: 1132=1131+1=1131⋅1131 ≡ 113⋅113=12769 ≡ 249 mod 313

4: 1134=1132+2=1132⋅1132 ≡ 249⋅249=62001 ≡ 27 mod 313

8: 1138=1134+4=1134⋅1134 ≡ 27⋅27=729 ≡ 103 mod 313

16: 11316=1138+8=1138⋅1138 ≡ 103⋅103=10609 ≡ 280 mod 313

32: 11332=11316+16=11316⋅11316 ≡ 280⋅280=78400 ≡ 150 mod 313

64: 11364=11332+32=11332⋅11332 ≡ 150⋅150=22500 ≡ 277 mod 313

128: 113128=11364+64=11364⋅11364 ≡ 277⋅277=76729 ≡ 44 mod 313

113203

= 113128+64+8+2+1

= 113128⋅11364⋅1138⋅1132⋅1131

≡ 44 ⋅ 277 ⋅ 103 ⋅ 249 ⋅ 113 mod 313
≡ 12188 ⋅ 103 ⋅ 249 ⋅ 113 mod 313 ≡ 294 ⋅ 103 ⋅ 249 ⋅ 113 mod 313
≡ 30282 ⋅ 249 ⋅ 113 mod 313 ≡ 234 ⋅ 249 ⋅ 113 mod 313
≡ 58266 ⋅ 113 mod 313 ≡ 48 ⋅ 113 mod 313
≡ 5424 mod 313 ≡ 103 mod 313

Es gilt also: 113203 ≡ 103 mod 313

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>79 = 1⋅63 + 16
=>63 = 3⋅16 + 15
=>16 = 1⋅15 + 1
=>15 = 15⋅1 + 0

also gilt: ggt(79,63)=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= 16-1⋅15
15= 63-3⋅16 eingesetzt in die Zeile drüber: 1 = 1⋅16 -1⋅(63 -3⋅ 16)
= 1⋅16 -1⋅63 +3⋅ 16)
= -1⋅63 +4⋅ 16 (=1)
16= 79-1⋅63 eingesetzt in die Zeile drüber: 1 = -1⋅63 +4⋅(79 -1⋅ 63)
= -1⋅63 +4⋅79 -4⋅ 63)
= 4⋅79 -5⋅ 63 (=1)

Es gilt also: ggt(79,63)=1 = 4⋅79 -5⋅63

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

1 -4⋅79 = -5⋅63

-5⋅63 = -4⋅79 + 1 |+79⋅63

-5⋅63 + 79⋅63 = -4⋅79 + 79⋅63 + 1

(-5 + 79) ⋅ 63 = (-4 + 63) ⋅ 79 + 1

74⋅63 = 59⋅79 + 1

Es gilt also: 74⋅63 = 59⋅79 +1

Somit 74⋅63 = 1 mod 79

74 ist also das Inverse von 63 mod 79

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden