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: (9002 - 3000) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(9002 - 3000) mod 3 ≡ (9002 mod 3 - 3000 mod 3) mod 3.

9002 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 9002 = 9000+2 = 3 ⋅ 3000 +2.

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

Somit gilt:

(9002 - 3000) mod 3 ≡ (2 - 0) mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (87 ⋅ 82) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(87 ⋅ 82) mod 4 ≡ (87 mod 4 ⋅ 82 mod 4) mod 4.

87 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 87 = 84 + 3 = 21 ⋅ 4 + 3 ist.

82 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 82 = 80 + 2 = 20 ⋅ 4 + 2 ist.

Somit gilt:

(87 ⋅ 82) mod 4 ≡ (3 ⋅ 2) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 31316 mod 547.

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. 313 -> x
2. mod(x²,547) -> 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: 3131=313

2: 3132=3131+1=3131⋅3131 ≡ 313⋅313=97969 ≡ 56 mod 547

4: 3134=3132+2=3132⋅3132 ≡ 56⋅56=3136 ≡ 401 mod 547

8: 3138=3134+4=3134⋅3134 ≡ 401⋅401=160801 ≡ 530 mod 547

16: 31316=3138+8=3138⋅3138 ≡ 530⋅530=280900 ≡ 289 mod 547

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 401185 mod 487.

Lösung einblenden

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

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

185 = 128+32+16+8+1

1: 4011=401

2: 4012=4011+1=4011⋅4011 ≡ 401⋅401=160801 ≡ 91 mod 487

4: 4014=4012+2=4012⋅4012 ≡ 91⋅91=8281 ≡ 2 mod 487

8: 4018=4014+4=4014⋅4014 ≡ 2⋅2=4 ≡ 4 mod 487

16: 40116=4018+8=4018⋅4018 ≡ 4⋅4=16 ≡ 16 mod 487

32: 40132=40116+16=40116⋅40116 ≡ 16⋅16=256 ≡ 256 mod 487

64: 40164=40132+32=40132⋅40132 ≡ 256⋅256=65536 ≡ 278 mod 487

128: 401128=40164+64=40164⋅40164 ≡ 278⋅278=77284 ≡ 338 mod 487

401185

= 401128+32+16+8+1

= 401128⋅40132⋅40116⋅4018⋅4011

338 ⋅ 256 ⋅ 16 ⋅ 4 ⋅ 401 mod 487
86528 ⋅ 16 ⋅ 4 ⋅ 401 mod 487 ≡ 329 ⋅ 16 ⋅ 4 ⋅ 401 mod 487
5264 ⋅ 4 ⋅ 401 mod 487 ≡ 394 ⋅ 4 ⋅ 401 mod 487
1576 ⋅ 401 mod 487 ≡ 115 ⋅ 401 mod 487
46115 mod 487 ≡ 337 mod 487

Es gilt also: 401185 ≡ 337 mod 487

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 82 ⋅ x ≡ 1 mod 101 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 101 und 82

=>101 = 1⋅82 + 19
=>82 = 4⋅19 + 6
=>19 = 3⋅6 + 1
=>6 = 6⋅1 + 0

also gilt: ggt(101,82)=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= 19-3⋅6
6= 82-4⋅19 eingesetzt in die Zeile drüber: 1 = 1⋅19 -3⋅(82 -4⋅ 19)
= 1⋅19 -3⋅82 +12⋅ 19)
= -3⋅82 +13⋅ 19 (=1)
19= 101-1⋅82 eingesetzt in die Zeile drüber: 1 = -3⋅82 +13⋅(101 -1⋅ 82)
= -3⋅82 +13⋅101 -13⋅ 82)
= 13⋅101 -16⋅ 82 (=1)

Es gilt also: ggt(101,82)=1 = 13⋅101 -16⋅82

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

1 -13⋅101 = -16⋅82

-16⋅82 = -13⋅101 + 1 |+101⋅82

-16⋅82 + 101⋅82 = -13⋅101 + 101⋅82 + 1

(-16 + 101) ⋅ 82 = (-13 + 82) ⋅ 101 + 1

85⋅82 = 69⋅101 + 1

Es gilt also: 85⋅82 = 69⋅101 +1

Somit 85⋅82 = 1 mod 101

85 ist also das Inverse von 82 mod 101

Schlüsselpaar für RSA

Beispiel:

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