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: (1499 + 15000) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1499 + 15000) mod 5 ≡ (1499 mod 5 + 15000 mod 5) mod 5.

1499 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1499 = 1400+99 = 5 ⋅ 280 +99.

15000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 15000 = 15000+0 = 5 ⋅ 3000 +0.

Somit gilt:

(1499 + 15000) mod 5 ≡ (4 + 0) mod 5 ≡ 4 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (91 ⋅ 77) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(91 ⋅ 77) mod 4 ≡ (91 mod 4 ⋅ 77 mod 4) mod 4.

91 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 91 = 88 + 3 = 22 ⋅ 4 + 3 ist.

77 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 77 = 76 + 1 = 19 ⋅ 4 + 1 ist.

Somit gilt:

(91 ⋅ 77) mod 4 ≡ (3 ⋅ 1) mod 4 ≡ 3 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 626128 mod 773.

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. 626 -> x
2. mod(x²,773) -> 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: 6261=626

2: 6262=6261+1=6261⋅6261 ≡ 626⋅626=391876 ≡ 738 mod 773

4: 6264=6262+2=6262⋅6262 ≡ 738⋅738=544644 ≡ 452 mod 773

8: 6268=6264+4=6264⋅6264 ≡ 452⋅452=204304 ≡ 232 mod 773

16: 62616=6268+8=6268⋅6268 ≡ 232⋅232=53824 ≡ 487 mod 773

32: 62632=62616+16=62616⋅62616 ≡ 487⋅487=237169 ≡ 631 mod 773

64: 62664=62632+32=62632⋅62632 ≡ 631⋅631=398161 ≡ 66 mod 773

128: 626128=62664+64=62664⋅62664 ≡ 66⋅66=4356 ≡ 491 mod 773

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 700187 mod 733.

Lösung einblenden

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

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

187 = 128+32+16+8+2+1

1: 7001=700

2: 7002=7001+1=7001⋅7001 ≡ 700⋅700=490000 ≡ 356 mod 733

4: 7004=7002+2=7002⋅7002 ≡ 356⋅356=126736 ≡ 660 mod 733

8: 7008=7004+4=7004⋅7004 ≡ 660⋅660=435600 ≡ 198 mod 733

16: 70016=7008+8=7008⋅7008 ≡ 198⋅198=39204 ≡ 355 mod 733

32: 70032=70016+16=70016⋅70016 ≡ 355⋅355=126025 ≡ 682 mod 733

64: 70064=70032+32=70032⋅70032 ≡ 682⋅682=465124 ≡ 402 mod 733

128: 700128=70064+64=70064⋅70064 ≡ 402⋅402=161604 ≡ 344 mod 733

700187

= 700128+32+16+8+2+1

= 700128⋅70032⋅70016⋅7008⋅7002⋅7001

344 ⋅ 682 ⋅ 355 ⋅ 198 ⋅ 356 ⋅ 700 mod 733
234608 ⋅ 355 ⋅ 198 ⋅ 356 ⋅ 700 mod 733 ≡ 48 ⋅ 355 ⋅ 198 ⋅ 356 ⋅ 700 mod 733
17040 ⋅ 198 ⋅ 356 ⋅ 700 mod 733 ≡ 181 ⋅ 198 ⋅ 356 ⋅ 700 mod 733
35838 ⋅ 356 ⋅ 700 mod 733 ≡ 654 ⋅ 356 ⋅ 700 mod 733
232824 ⋅ 700 mod 733 ≡ 463 ⋅ 700 mod 733
324100 mod 733 ≡ 114 mod 733

Es gilt also: 700187 ≡ 114 mod 733

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 66 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 66

=>73 = 1⋅66 + 7
=>66 = 9⋅7 + 3
=>7 = 2⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(73,66)=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-2⋅3
3= 66-9⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -2⋅(66 -9⋅ 7)
= 1⋅7 -2⋅66 +18⋅ 7)
= -2⋅66 +19⋅ 7 (=1)
7= 73-1⋅66 eingesetzt in die Zeile drüber: 1 = -2⋅66 +19⋅(73 -1⋅ 66)
= -2⋅66 +19⋅73 -19⋅ 66)
= 19⋅73 -21⋅ 66 (=1)

Es gilt also: ggt(73,66)=1 = 19⋅73 -21⋅66

oder wenn man 19⋅73 auf die linke Seite bringt:

1 -19⋅73 = -21⋅66

-21⋅66 = -19⋅73 + 1 |+73⋅66

-21⋅66 + 73⋅66 = -19⋅73 + 73⋅66 + 1

(-21 + 73) ⋅ 66 = (-19 + 66) ⋅ 73 + 1

52⋅66 = 47⋅73 + 1

Es gilt also: 52⋅66 = 47⋅73 +1

Somit 52⋅66 = 1 mod 73

52 ist also das Inverse von 66 mod 73

Schlüsselpaar für RSA

Beispiel:

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