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: (245 + 1608) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(245 + 1608) mod 8 ≡ (245 mod 8 + 1608 mod 8) mod 8.

245 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 245 = 240+5 = 8 ⋅ 30 +5.

1608 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 1608 = 1600+8 = 8 ⋅ 200 +8.

Somit gilt:

(245 + 1608) mod 8 ≡ (5 + 0) mod 8 ≡ 5 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (26 ⋅ 56) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(26 ⋅ 56) mod 10 ≡ (26 mod 10 ⋅ 56 mod 10) mod 10.

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

56 mod 10 ≡ 6 mod 10 kann man relativ leicht bestimmen, weil ja 56 = 50 + 6 = 5 ⋅ 10 + 6 ist.

Somit gilt:

(26 ⋅ 56) mod 10 ≡ (6 ⋅ 6) mod 10 ≡ 36 mod 10 ≡ 6 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 7778 mod 857.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 777 -> x
2. mod(x²,857) -> 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: 7771=777

2: 7772=7771+1=7771⋅7771 ≡ 777⋅777=603729 ≡ 401 mod 857

4: 7774=7772+2=7772⋅7772 ≡ 401⋅401=160801 ≡ 542 mod 857

8: 7778=7774+4=7774⋅7774 ≡ 542⋅542=293764 ≡ 670 mod 857

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 696221 mod 733.

Lösung einblenden

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

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

221 = 128+64+16+8+4+1

1: 6961=696

2: 6962=6961+1=6961⋅6961 ≡ 696⋅696=484416 ≡ 636 mod 733

4: 6964=6962+2=6962⋅6962 ≡ 636⋅636=404496 ≡ 613 mod 733

8: 6968=6964+4=6964⋅6964 ≡ 613⋅613=375769 ≡ 473 mod 733

16: 69616=6968+8=6968⋅6968 ≡ 473⋅473=223729 ≡ 164 mod 733

32: 69632=69616+16=69616⋅69616 ≡ 164⋅164=26896 ≡ 508 mod 733

64: 69664=69632+32=69632⋅69632 ≡ 508⋅508=258064 ≡ 48 mod 733

128: 696128=69664+64=69664⋅69664 ≡ 48⋅48=2304 ≡ 105 mod 733

696221

= 696128+64+16+8+4+1

= 696128⋅69664⋅69616⋅6968⋅6964⋅6961

105 ⋅ 48 ⋅ 164 ⋅ 473 ⋅ 613 ⋅ 696 mod 733
5040 ⋅ 164 ⋅ 473 ⋅ 613 ⋅ 696 mod 733 ≡ 642 ⋅ 164 ⋅ 473 ⋅ 613 ⋅ 696 mod 733
105288 ⋅ 473 ⋅ 613 ⋅ 696 mod 733 ≡ 469 ⋅ 473 ⋅ 613 ⋅ 696 mod 733
221837 ⋅ 613 ⋅ 696 mod 733 ≡ 471 ⋅ 613 ⋅ 696 mod 733
288723 ⋅ 696 mod 733 ≡ 654 ⋅ 696 mod 733
455184 mod 733 ≡ 724 mod 733

Es gilt also: 696221 ≡ 724 mod 733

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 30 ⋅ x ≡ 1 mod 83 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 83 und 30

=>83 = 2⋅30 + 23
=>30 = 1⋅23 + 7
=>23 = 3⋅7 + 2
=>7 = 3⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(83,30)=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-3⋅2
2= 23-3⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -3⋅(23 -3⋅ 7)
= 1⋅7 -3⋅23 +9⋅ 7)
= -3⋅23 +10⋅ 7 (=1)
7= 30-1⋅23 eingesetzt in die Zeile drüber: 1 = -3⋅23 +10⋅(30 -1⋅ 23)
= -3⋅23 +10⋅30 -10⋅ 23)
= 10⋅30 -13⋅ 23 (=1)
23= 83-2⋅30 eingesetzt in die Zeile drüber: 1 = 10⋅30 -13⋅(83 -2⋅ 30)
= 10⋅30 -13⋅83 +26⋅ 30)
= -13⋅83 +36⋅ 30 (=1)

Es gilt also: ggt(83,30)=1 = -13⋅83 +36⋅30

oder wenn man -13⋅83 auf die linke Seite bringt:

1 +13⋅83 = +36⋅30

Es gilt also: 36⋅30 = 13⋅83 +1

Somit 36⋅30 = 1 mod 83

36 ist also das Inverse von 30 mod 83

Schlüsselpaar für RSA

Beispiel:

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