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: (606 + 126) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(606 + 126) mod 6 ≡ (606 mod 6 + 126 mod 6) mod 6.

606 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 606 = 600+6 = 6 ⋅ 100 +6.

126 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 126 = 120+6 = 6 ⋅ 20 +6.

Somit gilt:

(606 + 126) mod 6 ≡ (0 + 0) mod 6 ≡ 0 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (86 ⋅ 73) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(86 ⋅ 73) mod 6 ≡ (86 mod 6 ⋅ 73 mod 6) mod 6.

86 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 86 = 84 + 2 = 14 ⋅ 6 + 2 ist.

73 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 73 = 72 + 1 = 12 ⋅ 6 + 1 ist.

Somit gilt:

(86 ⋅ 73) mod 6 ≡ (2 ⋅ 1) mod 6 ≡ 2 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 80532 mod 859.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 805 -> x
2. mod(x²,859) -> 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: 8051=805

2: 8052=8051+1=8051⋅8051 ≡ 805⋅805=648025 ≡ 339 mod 859

4: 8054=8052+2=8052⋅8052 ≡ 339⋅339=114921 ≡ 674 mod 859

8: 8058=8054+4=8054⋅8054 ≡ 674⋅674=454276 ≡ 724 mod 859

16: 80516=8058+8=8058⋅8058 ≡ 724⋅724=524176 ≡ 186 mod 859

32: 80532=80516+16=80516⋅80516 ≡ 186⋅186=34596 ≡ 236 mod 859

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 442155 mod 491.

Lösung einblenden

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

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

155 = 128+16+8+2+1

1: 4421=442

2: 4422=4421+1=4421⋅4421 ≡ 442⋅442=195364 ≡ 437 mod 491

4: 4424=4422+2=4422⋅4422 ≡ 437⋅437=190969 ≡ 461 mod 491

8: 4428=4424+4=4424⋅4424 ≡ 461⋅461=212521 ≡ 409 mod 491

16: 44216=4428+8=4428⋅4428 ≡ 409⋅409=167281 ≡ 341 mod 491

32: 44232=44216+16=44216⋅44216 ≡ 341⋅341=116281 ≡ 405 mod 491

64: 44264=44232+32=44232⋅44232 ≡ 405⋅405=164025 ≡ 31 mod 491

128: 442128=44264+64=44264⋅44264 ≡ 31⋅31=961 ≡ 470 mod 491

442155

= 442128+16+8+2+1

= 442128⋅44216⋅4428⋅4422⋅4421

≡ 470 ⋅ 341 ⋅ 409 ⋅ 437 ⋅ 442 mod 491
≡ 160270 ⋅ 409 ⋅ 437 ⋅ 442 mod 491 ≡ 204 ⋅ 409 ⋅ 437 ⋅ 442 mod 491
≡ 83436 ⋅ 437 ⋅ 442 mod 491 ≡ 457 ⋅ 437 ⋅ 442 mod 491
≡ 199709 ⋅ 442 mod 491 ≡ 363 ⋅ 442 mod 491
≡ 160446 mod 491 ≡ 380 mod 491

Es gilt also: 442155 ≡ 380 mod 491

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 54 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 54

=>67 = 1⋅54 + 13
=>54 = 4⋅13 + 2
=>13 = 6⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(67,54)=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= 13-6⋅2
2= 54-4⋅13 eingesetzt in die Zeile drüber: 1 = 1⋅13 -6⋅(54 -4⋅ 13)
= 1⋅13 -6⋅54 +24⋅ 13)
= -6⋅54 +25⋅ 13 (=1)
13= 67-1⋅54 eingesetzt in die Zeile drüber: 1 = -6⋅54 +25⋅(67 -1⋅ 54)
= -6⋅54 +25⋅67 -25⋅ 54)
= 25⋅67 -31⋅ 54 (=1)

Es gilt also: ggt(67,54)=1 = 25⋅67 -31⋅54

oder wenn man 25⋅67 auf die linke Seite bringt:

1 -25⋅67 = -31⋅54

-31⋅54 = -25⋅67 + 1 |+67⋅54

-31⋅54 + 67⋅54 = -25⋅67 + 67⋅54 + 1

(-31 + 67) ⋅ 54 = (-25 + 54) ⋅ 67 + 1

36⋅54 = 29⋅67 + 1

Es gilt also: 36⋅54 = 29⋅67 +1

Somit 36⋅54 = 1 mod 67

36 ist also das Inverse von 54 mod 67

Schlüsselpaar für RSA

Beispiel:

Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 71 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