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: (44994 - 902) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(44994 - 902) mod 9 ≡ (44994 mod 9 - 902 mod 9) mod 9.

44994 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 44994 = 45000-6 = 9 ⋅ 5000 -6 = 9 ⋅ 5000 - 9 + 3.

902 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 902 = 900+2 = 9 ⋅ 100 +2.

Somit gilt:

(44994 - 902) mod 9 ≡ (3 - 2) mod 9 ≡ 1 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (79 ⋅ 17) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(79 ⋅ 17) mod 11 ≡ (79 mod 11 ⋅ 17 mod 11) mod 11.

79 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 79 = 77 + 2 = 7 ⋅ 11 + 2 ist.

17 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 17 = 11 + 6 = 1 ⋅ 11 + 6 ist.

Somit gilt:

(79 ⋅ 17) mod 11 ≡ (2 ⋅ 6) mod 11 ≡ 12 mod 11 ≡ 1 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 63964 mod 727.

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. 639 -> x
2. mod(x²,727) -> 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: 6391=639

2: 6392=6391+1=6391⋅6391 ≡ 639⋅639=408321 ≡ 474 mod 727

4: 6394=6392+2=6392⋅6392 ≡ 474⋅474=224676 ≡ 33 mod 727

8: 6398=6394+4=6394⋅6394 ≡ 33⋅33=1089 ≡ 362 mod 727

16: 63916=6398+8=6398⋅6398 ≡ 362⋅362=131044 ≡ 184 mod 727

32: 63932=63916+16=63916⋅63916 ≡ 184⋅184=33856 ≡ 414 mod 727

64: 63964=63932+32=63932⋅63932 ≡ 414⋅414=171396 ≡ 551 mod 727

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 548164 mod 577.

Lösung einblenden

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

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

164 = 128+32+4

1: 5481=548

2: 5482=5481+1=5481⋅5481 ≡ 548⋅548=300304 ≡ 264 mod 577

4: 5484=5482+2=5482⋅5482 ≡ 264⋅264=69696 ≡ 456 mod 577

8: 5488=5484+4=5484⋅5484 ≡ 456⋅456=207936 ≡ 216 mod 577

16: 54816=5488+8=5488⋅5488 ≡ 216⋅216=46656 ≡ 496 mod 577

32: 54832=54816+16=54816⋅54816 ≡ 496⋅496=246016 ≡ 214 mod 577

64: 54864=54832+32=54832⋅54832 ≡ 214⋅214=45796 ≡ 213 mod 577

128: 548128=54864+64=54864⋅54864 ≡ 213⋅213=45369 ≡ 363 mod 577

548164

= 548128+32+4

= 548128⋅54832⋅5484

≡ 363 ⋅ 214 ⋅ 456 mod 577
≡ 77682 ⋅ 456 mod 577 ≡ 364 ⋅ 456 mod 577
≡ 165984 mod 577 ≡ 385 mod 577

Es gilt also: 548164 ≡ 385 mod 577

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>67 = 1⋅48 + 19
=>48 = 2⋅19 + 10
=>19 = 1⋅10 + 9
=>10 = 1⋅9 + 1
=>9 = 9⋅1 + 0

also gilt: ggt(67,48)=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= 10-1⋅9
9= 19-1⋅10 eingesetzt in die Zeile drüber: 1 = 1⋅10 -1⋅(19 -1⋅ 10)
= 1⋅10 -1⋅19 +1⋅ 10)
= -1⋅19 +2⋅ 10 (=1)
10= 48-2⋅19 eingesetzt in die Zeile drüber: 1 = -1⋅19 +2⋅(48 -2⋅ 19)
= -1⋅19 +2⋅48 -4⋅ 19)
= 2⋅48 -5⋅ 19 (=1)
19= 67-1⋅48 eingesetzt in die Zeile drüber: 1 = 2⋅48 -5⋅(67 -1⋅ 48)
= 2⋅48 -5⋅67 +5⋅ 48)
= -5⋅67 +7⋅ 48 (=1)

Es gilt also: ggt(67,48)=1 = -5⋅67 +7⋅48

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

1 +5⋅67 = +7⋅48

Es gilt also: 7⋅48 = 5⋅67 +1

Somit 7⋅48 = 1 mod 67

7 ist also das Inverse von 48 mod 67

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden