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: (8000 - 83) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(8000 - 83) mod 4 ≡ (8000 mod 4 - 83 mod 4) mod 4.

8000 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 8000 = 8000+0 = 4 ⋅ 2000 +0.

83 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 83 = 80+3 = 4 ⋅ 20 +3.

Somit gilt:

(8000 - 83) mod 4 ≡ (0 - 3) mod 4 ≡ -3 mod 4 ≡ 1 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (17 ⋅ 52) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(17 ⋅ 52) mod 4 ≡ (17 mod 4 ⋅ 52 mod 4) mod 4.

17 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 17 = 16 + 1 = 4 ⋅ 4 + 1 ist.

52 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 52 = 52 + 0 = 13 ⋅ 4 + 0 ist.

Somit gilt:

(17 ⋅ 52) mod 4 ≡ (1 ⋅ 0) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 257128 mod 641.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 257 -> x
2. mod(x²,641) -> 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: 2571=257

2: 2572=2571+1=2571⋅2571 ≡ 257⋅257=66049 ≡ 26 mod 641

4: 2574=2572+2=2572⋅2572 ≡ 26⋅26=676 ≡ 35 mod 641

8: 2578=2574+4=2574⋅2574 ≡ 35⋅35=1225 ≡ 584 mod 641

16: 25716=2578+8=2578⋅2578 ≡ 584⋅584=341056 ≡ 44 mod 641

32: 25732=25716+16=25716⋅25716 ≡ 44⋅44=1936 ≡ 13 mod 641

64: 25764=25732+32=25732⋅25732 ≡ 13⋅13=169 ≡ 169 mod 641

128: 257128=25764+64=25764⋅25764 ≡ 169⋅169=28561 ≡ 357 mod 641

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 390203 mod 751.

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: 3901=390

2: 3902=3901+1=3901⋅3901 ≡ 390⋅390=152100 ≡ 398 mod 751

4: 3904=3902+2=3902⋅3902 ≡ 398⋅398=158404 ≡ 694 mod 751

8: 3908=3904+4=3904⋅3904 ≡ 694⋅694=481636 ≡ 245 mod 751

16: 39016=3908+8=3908⋅3908 ≡ 245⋅245=60025 ≡ 696 mod 751

32: 39032=39016+16=39016⋅39016 ≡ 696⋅696=484416 ≡ 21 mod 751

64: 39064=39032+32=39032⋅39032 ≡ 21⋅21=441 ≡ 441 mod 751

128: 390128=39064+64=39064⋅39064 ≡ 441⋅441=194481 ≡ 723 mod 751

390203

= 390128+64+8+2+1

= 390128⋅39064⋅3908⋅3902⋅3901

≡ 723 ⋅ 441 ⋅ 245 ⋅ 398 ⋅ 390 mod 751
≡ 318843 ⋅ 245 ⋅ 398 ⋅ 390 mod 751 ≡ 419 ⋅ 245 ⋅ 398 ⋅ 390 mod 751
≡ 102655 ⋅ 398 ⋅ 390 mod 751 ≡ 519 ⋅ 398 ⋅ 390 mod 751
≡ 206562 ⋅ 390 mod 751 ≡ 37 ⋅ 390 mod 751
≡ 14430 mod 751 ≡ 161 mod 751

Es gilt also: 390203 ≡ 161 mod 751

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 22 ⋅ x ≡ 1 mod 71 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 71 und 22

=>71 = 3⋅22 + 5
=>22 = 4⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(71,22)=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= 5-2⋅2
2= 22-4⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(22 -4⋅ 5)
= 1⋅5 -2⋅22 +8⋅ 5)
= -2⋅22 +9⋅ 5 (=1)
5= 71-3⋅22 eingesetzt in die Zeile drüber: 1 = -2⋅22 +9⋅(71 -3⋅ 22)
= -2⋅22 +9⋅71 -27⋅ 22)
= 9⋅71 -29⋅ 22 (=1)

Es gilt also: ggt(71,22)=1 = 9⋅71 -29⋅22

oder wenn man 9⋅71 auf die linke Seite bringt:

1 -9⋅71 = -29⋅22

-29⋅22 = -9⋅71 + 1 |+71⋅22

-29⋅22 + 71⋅22 = -9⋅71 + 71⋅22 + 1

(-29 + 71) ⋅ 22 = (-9 + 22) ⋅ 71 + 1

42⋅22 = 13⋅71 + 1

Es gilt also: 42⋅22 = 13⋅71 +1

Somit 42⋅22 = 1 mod 71

42 ist also das Inverse von 22 mod 71

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden