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: (1800 - 84) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1800 - 84) mod 9 ≡ (1800 mod 9 - 84 mod 9) mod 9.

1800 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 1800 = 1800+0 = 9 ⋅ 200 +0.

84 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 84 = 90-6 = 9 ⋅ 10 -6 = 9 ⋅ 10 - 9 + 3.

Somit gilt:

(1800 - 84) mod 9 ≡ (0 - 3) mod 9 ≡ -3 mod 9 ≡ 6 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (52 ⋅ 60) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(52 ⋅ 60) mod 7 ≡ (52 mod 7 ⋅ 60 mod 7) mod 7.

52 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 52 = 49 + 3 = 7 ⋅ 7 + 3 ist.

60 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 60 = 56 + 4 = 8 ⋅ 7 + 4 ist.

Somit gilt:

(52 ⋅ 60) mod 7 ≡ (3 ⋅ 4) mod 7 ≡ 12 mod 7 ≡ 5 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 83764 mod 971.

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. 837 -> x
2. mod(x²,971) -> 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: 8371=837

2: 8372=8371+1=8371⋅8371 ≡ 837⋅837=700569 ≡ 478 mod 971

4: 8374=8372+2=8372⋅8372 ≡ 478⋅478=228484 ≡ 299 mod 971

8: 8378=8374+4=8374⋅8374 ≡ 299⋅299=89401 ≡ 69 mod 971

16: 83716=8378+8=8378⋅8378 ≡ 69⋅69=4761 ≡ 877 mod 971

32: 83732=83716+16=83716⋅83716 ≡ 877⋅877=769129 ≡ 97 mod 971

64: 83764=83732+32=83732⋅83732 ≡ 97⋅97=9409 ≡ 670 mod 971

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 726229 mod 739.

Lösung einblenden

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

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

229 = 128+64+32+4+1

1: 7261=726

2: 7262=7261+1=7261⋅7261 ≡ 726⋅726=527076 ≡ 169 mod 739

4: 7264=7262+2=7262⋅7262 ≡ 169⋅169=28561 ≡ 479 mod 739

8: 7268=7264+4=7264⋅7264 ≡ 479⋅479=229441 ≡ 351 mod 739

16: 72616=7268+8=7268⋅7268 ≡ 351⋅351=123201 ≡ 527 mod 739

32: 72632=72616+16=72616⋅72616 ≡ 527⋅527=277729 ≡ 604 mod 739

64: 72664=72632+32=72632⋅72632 ≡ 604⋅604=364816 ≡ 489 mod 739

128: 726128=72664+64=72664⋅72664 ≡ 489⋅489=239121 ≡ 424 mod 739

726229

= 726128+64+32+4+1

= 726128⋅72664⋅72632⋅7264⋅7261

424 ⋅ 489 ⋅ 604 ⋅ 479 ⋅ 726 mod 739
207336 ⋅ 604 ⋅ 479 ⋅ 726 mod 739 ≡ 416 ⋅ 604 ⋅ 479 ⋅ 726 mod 739
251264 ⋅ 479 ⋅ 726 mod 739 ≡ 4 ⋅ 479 ⋅ 726 mod 739
1916 ⋅ 726 mod 739 ≡ 438 ⋅ 726 mod 739
317988 mod 739 ≡ 218 mod 739

Es gilt also: 726229 ≡ 218 mod 739

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 = 73 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.