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: (353 + 277) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(353 + 277) mod 9 ≡ (353 mod 9 + 277 mod 9) mod 9.

353 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 353 = 360-7 = 9 ⋅ 40 -7 = 9 ⋅ 40 - 9 + 2.

277 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 277 = 270+7 = 9 ⋅ 30 +7.

Somit gilt:

(353 + 277) mod 9 ≡ (2 + 7) mod 9 ≡ 9 mod 9 ≡ 0 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (23 ⋅ 85) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(23 ⋅ 85) mod 4 ≡ (23 mod 4 ⋅ 85 mod 4) mod 4.

23 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 23 = 20 + 3 = 5 ⋅ 4 + 3 ist.

85 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 21 ⋅ 4 + 1 ist.

Somit gilt:

(23 ⋅ 85) mod 4 ≡ (3 ⋅ 1) mod 4 ≡ 3 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 505128 mod 509.

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. 505 -> x
2. mod(x²,509) -> 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: 5051=505

2: 5052=5051+1=5051⋅5051 ≡ 505⋅505=255025 ≡ 16 mod 509

4: 5054=5052+2=5052⋅5052 ≡ 16⋅16=256 ≡ 256 mod 509

8: 5058=5054+4=5054⋅5054 ≡ 256⋅256=65536 ≡ 384 mod 509

16: 50516=5058+8=5058⋅5058 ≡ 384⋅384=147456 ≡ 355 mod 509

32: 50532=50516+16=50516⋅50516 ≡ 355⋅355=126025 ≡ 302 mod 509

64: 50564=50532+32=50532⋅50532 ≡ 302⋅302=91204 ≡ 93 mod 509

128: 505128=50564+64=50564⋅50564 ≡ 93⋅93=8649 ≡ 505 mod 509

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 866162 mod 877.

Lösung einblenden

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

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

162 = 128+32+2

1: 8661=866

2: 8662=8661+1=8661⋅8661 ≡ 866⋅866=749956 ≡ 121 mod 877

4: 8664=8662+2=8662⋅8662 ≡ 121⋅121=14641 ≡ 609 mod 877

8: 8668=8664+4=8664⋅8664 ≡ 609⋅609=370881 ≡ 787 mod 877

16: 86616=8668+8=8668⋅8668 ≡ 787⋅787=619369 ≡ 207 mod 877

32: 86632=86616+16=86616⋅86616 ≡ 207⋅207=42849 ≡ 753 mod 877

64: 86664=86632+32=86632⋅86632 ≡ 753⋅753=567009 ≡ 467 mod 877

128: 866128=86664+64=86664⋅86664 ≡ 467⋅467=218089 ≡ 593 mod 877

866162

= 866128+32+2

= 866128⋅86632⋅8662

593 ⋅ 753 ⋅ 121 mod 877
446529 ⋅ 121 mod 877 ≡ 136 ⋅ 121 mod 877
16456 mod 877 ≡ 670 mod 877

Es gilt also: 866162 ≡ 670 mod 877

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>73 = 1⋅39 + 34
=>39 = 1⋅34 + 5
=>34 = 6⋅5 + 4
=>5 = 1⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(73,39)=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-1⋅4
4= 34-6⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -1⋅(34 -6⋅ 5)
= 1⋅5 -1⋅34 +6⋅ 5)
= -1⋅34 +7⋅ 5 (=1)
5= 39-1⋅34 eingesetzt in die Zeile drüber: 1 = -1⋅34 +7⋅(39 -1⋅ 34)
= -1⋅34 +7⋅39 -7⋅ 34)
= 7⋅39 -8⋅ 34 (=1)
34= 73-1⋅39 eingesetzt in die Zeile drüber: 1 = 7⋅39 -8⋅(73 -1⋅ 39)
= 7⋅39 -8⋅73 +8⋅ 39)
= -8⋅73 +15⋅ 39 (=1)

Es gilt also: ggt(73,39)=1 = -8⋅73 +15⋅39

oder wenn man -8⋅73 auf die linke Seite bringt:

1 +8⋅73 = +15⋅39

Es gilt also: 15⋅39 = 8⋅73 +1

Somit 15⋅39 = 1 mod 73

15 ist also das Inverse von 39 mod 73

Schlüsselpaar für RSA

Beispiel:

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