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: (16000 + 4006) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(16000 + 4006) mod 8 ≡ (16000 mod 8 + 4006 mod 8) mod 8.

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

4006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 4006 = 4000+6 = 8 ⋅ 500 +6.

Somit gilt:

(16000 + 4006) mod 8 ≡ (0 + 6) mod 8 ≡ 6 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (100 ⋅ 20) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(100 ⋅ 20) mod 10 ≡ (100 mod 10 ⋅ 20 mod 10) mod 10.

100 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 100 = 100 + 0 = 10 ⋅ 10 + 0 ist.

20 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 20 = 20 + 0 = 2 ⋅ 10 + 0 ist.

Somit gilt:

(100 ⋅ 20) mod 10 ≡ (0 ⋅ 0) mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 42832 mod 563.

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. 428 -> x
2. mod(x²,563) -> 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: 4281=428

2: 4282=4281+1=4281⋅4281 ≡ 428⋅428=183184 ≡ 209 mod 563

4: 4284=4282+2=4282⋅4282 ≡ 209⋅209=43681 ≡ 330 mod 563

8: 4288=4284+4=4284⋅4284 ≡ 330⋅330=108900 ≡ 241 mod 563

16: 42816=4288+8=4288⋅4288 ≡ 241⋅241=58081 ≡ 92 mod 563

32: 42832=42816+16=42816⋅42816 ≡ 92⋅92=8464 ≡ 19 mod 563

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 369152 mod 857.

Lösung einblenden

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

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

152 = 128+16+8

1: 3691=369

2: 3692=3691+1=3691⋅3691 ≡ 369⋅369=136161 ≡ 755 mod 857

4: 3694=3692+2=3692⋅3692 ≡ 755⋅755=570025 ≡ 120 mod 857

8: 3698=3694+4=3694⋅3694 ≡ 120⋅120=14400 ≡ 688 mod 857

16: 36916=3698+8=3698⋅3698 ≡ 688⋅688=473344 ≡ 280 mod 857

32: 36932=36916+16=36916⋅36916 ≡ 280⋅280=78400 ≡ 413 mod 857

64: 36964=36932+32=36932⋅36932 ≡ 413⋅413=170569 ≡ 26 mod 857

128: 369128=36964+64=36964⋅36964 ≡ 26⋅26=676 ≡ 676 mod 857

369152

= 369128+16+8

= 369128⋅36916⋅3698

≡ 676 ⋅ 280 ⋅ 688 mod 857
≡ 189280 ⋅ 688 mod 857 ≡ 740 ⋅ 688 mod 857
≡ 509120 mod 857 ≡ 62 mod 857

Es gilt also: 369152 ≡ 62 mod 857

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>67 = 1⋅47 + 20
=>47 = 2⋅20 + 7
=>20 = 2⋅7 + 6
=>7 = 1⋅6 + 1
=>6 = 6⋅1 + 0

also gilt: ggt(67,47)=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= 7-1⋅6
6= 20-2⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -1⋅(20 -2⋅ 7)
= 1⋅7 -1⋅20 +2⋅ 7)
= -1⋅20 +3⋅ 7 (=1)
7= 47-2⋅20 eingesetzt in die Zeile drüber: 1 = -1⋅20 +3⋅(47 -2⋅ 20)
= -1⋅20 +3⋅47 -6⋅ 20)
= 3⋅47 -7⋅ 20 (=1)
20= 67-1⋅47 eingesetzt in die Zeile drüber: 1 = 3⋅47 -7⋅(67 -1⋅ 47)
= 3⋅47 -7⋅67 +7⋅ 47)
= -7⋅67 +10⋅ 47 (=1)

Es gilt also: ggt(67,47)=1 = -7⋅67 +10⋅47

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

1 +7⋅67 = +10⋅47

Es gilt also: 10⋅47 = 7⋅67 +1

Somit 10⋅47 = 1 mod 67

10 ist also das Inverse von 47 mod 67

Schlüsselpaar für RSA

Beispiel:

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