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: (3001 + 14999) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3001 + 14999) mod 3 ≡ (3001 mod 3 + 14999 mod 3) mod 3.

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

14999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 14999 = 15000-1 = 3 ⋅ 5000 -1 = 3 ⋅ 5000 - 3 + 2.

Somit gilt:

(3001 + 14999) mod 3 ≡ (1 + 2) mod 3 ≡ 3 mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (59 ⋅ 63) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(59 ⋅ 63) mod 7 ≡ (59 mod 7 ⋅ 63 mod 7) mod 7.

59 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 59 = 56 + 3 = 8 ⋅ 7 + 3 ist.

63 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 63 = 63 + 0 = 9 ⋅ 7 + 0 ist.

Somit gilt:

(59 ⋅ 63) mod 7 ≡ (3 ⋅ 0) mod 7 ≡ 0 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 41132 mod 593.

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. 411 -> x
2. mod(x²,593) -> 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: 4111=411

2: 4112=4111+1=4111⋅4111 ≡ 411⋅411=168921 ≡ 509 mod 593

4: 4114=4112+2=4112⋅4112 ≡ 509⋅509=259081 ≡ 533 mod 593

8: 4118=4114+4=4114⋅4114 ≡ 533⋅533=284089 ≡ 42 mod 593

16: 41116=4118+8=4118⋅4118 ≡ 42⋅42=1764 ≡ 578 mod 593

32: 41132=41116+16=41116⋅41116 ≡ 578⋅578=334084 ≡ 225 mod 593

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 483220 mod 809.

Lösung einblenden

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

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

220 = 128+64+16+8+4

1: 4831=483

2: 4832=4831+1=4831⋅4831 ≡ 483⋅483=233289 ≡ 297 mod 809

4: 4834=4832+2=4832⋅4832 ≡ 297⋅297=88209 ≡ 28 mod 809

8: 4838=4834+4=4834⋅4834 ≡ 28⋅28=784 ≡ 784 mod 809

16: 48316=4838+8=4838⋅4838 ≡ 784⋅784=614656 ≡ 625 mod 809

32: 48332=48316+16=48316⋅48316 ≡ 625⋅625=390625 ≡ 687 mod 809

64: 48364=48332+32=48332⋅48332 ≡ 687⋅687=471969 ≡ 322 mod 809

128: 483128=48364+64=48364⋅48364 ≡ 322⋅322=103684 ≡ 132 mod 809

483220

= 483128+64+16+8+4

= 483128⋅48364⋅48316⋅4838⋅4834

132 ⋅ 322 ⋅ 625 ⋅ 784 ⋅ 28 mod 809
42504 ⋅ 625 ⋅ 784 ⋅ 28 mod 809 ≡ 436 ⋅ 625 ⋅ 784 ⋅ 28 mod 809
272500 ⋅ 784 ⋅ 28 mod 809 ≡ 676 ⋅ 784 ⋅ 28 mod 809
529984 ⋅ 28 mod 809 ≡ 89 ⋅ 28 mod 809
2492 mod 809 ≡ 65 mod 809

Es gilt also: 483220 ≡ 65 mod 809

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>67 = 1⋅44 + 23
=>44 = 1⋅23 + 21
=>23 = 1⋅21 + 2
=>21 = 10⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(67,44)=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= 21-10⋅2
2= 23-1⋅21 eingesetzt in die Zeile drüber: 1 = 1⋅21 -10⋅(23 -1⋅ 21)
= 1⋅21 -10⋅23 +10⋅ 21)
= -10⋅23 +11⋅ 21 (=1)
21= 44-1⋅23 eingesetzt in die Zeile drüber: 1 = -10⋅23 +11⋅(44 -1⋅ 23)
= -10⋅23 +11⋅44 -11⋅ 23)
= 11⋅44 -21⋅ 23 (=1)
23= 67-1⋅44 eingesetzt in die Zeile drüber: 1 = 11⋅44 -21⋅(67 -1⋅ 44)
= 11⋅44 -21⋅67 +21⋅ 44)
= -21⋅67 +32⋅ 44 (=1)

Es gilt also: ggt(67,44)=1 = -21⋅67 +32⋅44

oder wenn man -21⋅67 auf die linke Seite bringt:

1 +21⋅67 = +32⋅44

Es gilt also: 32⋅44 = 21⋅67 +1

Somit 32⋅44 = 1 mod 67

32 ist also das Inverse von 44 mod 67

Schlüsselpaar für RSA

Beispiel:

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