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: (30005 - 24002) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(30005 - 24002) mod 6 ≡ (30005 mod 6 - 24002 mod 6) mod 6.

30005 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 30005 = 30000+5 = 6 ⋅ 5000 +5.

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

Somit gilt:

(30005 - 24002) mod 6 ≡ (5 - 2) mod 6 ≡ 3 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (38 ⋅ 33) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 33) mod 6 ≡ (38 mod 6 ⋅ 33 mod 6) mod 6.

38 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 38 = 36 + 2 = 6 ⋅ 6 + 2 ist.

33 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 33 = 30 + 3 = 5 ⋅ 6 + 3 ist.

Somit gilt:

(38 ⋅ 33) mod 6 ≡ (2 ⋅ 3) mod 6 ≡ 6 mod 6 ≡ 0 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 3348 mod 599.

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. 334 -> x
2. mod(x²,599) -> 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: 3341=334

2: 3342=3341+1=3341⋅3341 ≡ 334⋅334=111556 ≡ 142 mod 599

4: 3344=3342+2=3342⋅3342 ≡ 142⋅142=20164 ≡ 397 mod 599

8: 3348=3344+4=3344⋅3344 ≡ 397⋅397=157609 ≡ 72 mod 599

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 434250 mod 449.

Lösung einblenden

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

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

250 = 128+64+32+16+8+2

1: 4341=434

2: 4342=4341+1=4341⋅4341 ≡ 434⋅434=188356 ≡ 225 mod 449

4: 4344=4342+2=4342⋅4342 ≡ 225⋅225=50625 ≡ 337 mod 449

8: 4348=4344+4=4344⋅4344 ≡ 337⋅337=113569 ≡ 421 mod 449

16: 43416=4348+8=4348⋅4348 ≡ 421⋅421=177241 ≡ 335 mod 449

32: 43432=43416+16=43416⋅43416 ≡ 335⋅335=112225 ≡ 424 mod 449

64: 43464=43432+32=43432⋅43432 ≡ 424⋅424=179776 ≡ 176 mod 449

128: 434128=43464+64=43464⋅43464 ≡ 176⋅176=30976 ≡ 444 mod 449

434250

= 434128+64+32+16+8+2

= 434128⋅43464⋅43432⋅43416⋅4348⋅4342

444 ⋅ 176 ⋅ 424 ⋅ 335 ⋅ 421 ⋅ 225 mod 449
78144 ⋅ 424 ⋅ 335 ⋅ 421 ⋅ 225 mod 449 ≡ 18 ⋅ 424 ⋅ 335 ⋅ 421 ⋅ 225 mod 449
7632 ⋅ 335 ⋅ 421 ⋅ 225 mod 449 ≡ 448 ⋅ 335 ⋅ 421 ⋅ 225 mod 449
150080 ⋅ 421 ⋅ 225 mod 449 ≡ 114 ⋅ 421 ⋅ 225 mod 449
47994 ⋅ 225 mod 449 ≡ 400 ⋅ 225 mod 449
90000 mod 449 ≡ 200 mod 449

Es gilt also: 434250 ≡ 200 mod 449

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 2⋅48 + 5
=>48 = 9⋅5 + 3
=>5 = 1⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(101,48)=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= 3-1⋅2
2= 5-1⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(5 -1⋅ 3)
= 1⋅3 -1⋅5 +1⋅ 3)
= -1⋅5 +2⋅ 3 (=1)
3= 48-9⋅5 eingesetzt in die Zeile drüber: 1 = -1⋅5 +2⋅(48 -9⋅ 5)
= -1⋅5 +2⋅48 -18⋅ 5)
= 2⋅48 -19⋅ 5 (=1)
5= 101-2⋅48 eingesetzt in die Zeile drüber: 1 = 2⋅48 -19⋅(101 -2⋅ 48)
= 2⋅48 -19⋅101 +38⋅ 48)
= -19⋅101 +40⋅ 48 (=1)

Es gilt also: ggt(101,48)=1 = -19⋅101 +40⋅48

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +40⋅48

Es gilt also: 40⋅48 = 19⋅101 +1

Somit 40⋅48 = 1 mod 101

40 ist also das Inverse von 48 mod 101

Schlüsselpaar für RSA

Beispiel:

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