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: (1999 - 2503) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1999 - 2503) mod 5 ≡ (1999 mod 5 - 2503 mod 5) mod 5.

1999 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1999 = 1900+99 = 5 ⋅ 380 +99.

2503 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2503 = 2500+3 = 5 ⋅ 500 +3.

Somit gilt:

(1999 - 2503) mod 5 ≡ (4 - 3) mod 5 ≡ 1 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (21 ⋅ 30) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 30) mod 7 ≡ (21 mod 7 ⋅ 30 mod 7) mod 7.

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

30 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 30 = 28 + 2 = 4 ⋅ 7 + 2 ist.

Somit gilt:

(21 ⋅ 30) mod 7 ≡ (0 ⋅ 2) mod 7 ≡ 0 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 10364 mod 271.

Lösung einblenden

Die 64 im Exponent ist ja ein reine 2er-Potenz (26).

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. 103 -> x
2. mod(x²,271) -> 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: 1031=103

2: 1032=1031+1=1031⋅1031 ≡ 103⋅103=10609 ≡ 40 mod 271

4: 1034=1032+2=1032⋅1032 ≡ 40⋅40=1600 ≡ 245 mod 271

8: 1038=1034+4=1034⋅1034 ≡ 245⋅245=60025 ≡ 134 mod 271

16: 10316=1038+8=1038⋅1038 ≡ 134⋅134=17956 ≡ 70 mod 271

32: 10332=10316+16=10316⋅10316 ≡ 70⋅70=4900 ≡ 22 mod 271

64: 10364=10332+32=10332⋅10332 ≡ 22⋅22=484 ≡ 213 mod 271

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 263192 mod 827.

Lösung einblenden

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

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

192 = 128+64

1: 2631=263

2: 2632=2631+1=2631⋅2631 ≡ 263⋅263=69169 ≡ 528 mod 827

4: 2634=2632+2=2632⋅2632 ≡ 528⋅528=278784 ≡ 85 mod 827

8: 2638=2634+4=2634⋅2634 ≡ 85⋅85=7225 ≡ 609 mod 827

16: 26316=2638+8=2638⋅2638 ≡ 609⋅609=370881 ≡ 385 mod 827

32: 26332=26316+16=26316⋅26316 ≡ 385⋅385=148225 ≡ 192 mod 827

64: 26364=26332+32=26332⋅26332 ≡ 192⋅192=36864 ≡ 476 mod 827

128: 263128=26364+64=26364⋅26364 ≡ 476⋅476=226576 ≡ 805 mod 827

263192

= 263128+64

= 263128⋅26364

805 ⋅ 476 mod 827
383180 mod 827 ≡ 279 mod 827

Es gilt also: 263192 ≡ 279 mod 827

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 1⋅98 + 3
=>98 = 32⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(101,98)=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= 98-32⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(98 -32⋅ 3)
= 1⋅3 -1⋅98 +32⋅ 3)
= -1⋅98 +33⋅ 3 (=1)
3= 101-1⋅98 eingesetzt in die Zeile drüber: 1 = -1⋅98 +33⋅(101 -1⋅ 98)
= -1⋅98 +33⋅101 -33⋅ 98)
= 33⋅101 -34⋅ 98 (=1)

Es gilt also: ggt(101,98)=1 = 33⋅101 -34⋅98

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

1 -33⋅101 = -34⋅98

-34⋅98 = -33⋅101 + 1 |+101⋅98

-34⋅98 + 101⋅98 = -33⋅101 + 101⋅98 + 1

(-34 + 101) ⋅ 98 = (-33 + 98) ⋅ 101 + 1

67⋅98 = 65⋅101 + 1

Es gilt also: 67⋅98 = 65⋅101 +1

Somit 67⋅98 = 1 mod 101

67 ist also das Inverse von 98 mod 101

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.