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: (27004 - 99) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(27004 - 99) mod 9 ≡ (27004 mod 9 - 99 mod 9) mod 9.

27004 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 27004 = 27000+4 = 9 ⋅ 3000 +4.

99 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 99 = 90+9 = 9 ⋅ 10 +9.

Somit gilt:

(27004 - 99) mod 9 ≡ (4 - 0) mod 9 ≡ 4 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (27 ⋅ 33) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(27 ⋅ 33) mod 6 ≡ (27 mod 6 ⋅ 33 mod 6) mod 6.

27 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 27 = 24 + 3 = 4 ⋅ 6 + 3 ist.

33 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 33 = 30 + 3 = 5 ⋅ 6 + 3 ist.

Somit gilt:

(27 ⋅ 33) mod 6 ≡ (3 ⋅ 3) mod 6 ≡ 9 mod 6 ≡ 3 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 45264 mod 829.

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. 452 -> x
2. mod(x²,829) -> 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: 4521=452

2: 4522=4521+1=4521⋅4521 ≡ 452⋅452=204304 ≡ 370 mod 829

4: 4524=4522+2=4522⋅4522 ≡ 370⋅370=136900 ≡ 115 mod 829

8: 4528=4524+4=4524⋅4524 ≡ 115⋅115=13225 ≡ 790 mod 829

16: 45216=4528+8=4528⋅4528 ≡ 790⋅790=624100 ≡ 692 mod 829

32: 45232=45216+16=45216⋅45216 ≡ 692⋅692=478864 ≡ 531 mod 829

64: 45264=45232+32=45232⋅45232 ≡ 531⋅531=281961 ≡ 101 mod 829

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 698131 mod 727.

Lösung einblenden

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

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

131 = 128+2+1

1: 6981=698

2: 6982=6981+1=6981⋅6981 ≡ 698⋅698=487204 ≡ 114 mod 727

4: 6984=6982+2=6982⋅6982 ≡ 114⋅114=12996 ≡ 637 mod 727

8: 6988=6984+4=6984⋅6984 ≡ 637⋅637=405769 ≡ 103 mod 727

16: 69816=6988+8=6988⋅6988 ≡ 103⋅103=10609 ≡ 431 mod 727

32: 69832=69816+16=69816⋅69816 ≡ 431⋅431=185761 ≡ 376 mod 727

64: 69864=69832+32=69832⋅69832 ≡ 376⋅376=141376 ≡ 338 mod 727

128: 698128=69864+64=69864⋅69864 ≡ 338⋅338=114244 ≡ 105 mod 727

698131

= 698128+2+1

= 698128⋅6982⋅6981

≡ 105 ⋅ 114 ⋅ 698 mod 727
≡ 11970 ⋅ 698 mod 727 ≡ 338 ⋅ 698 mod 727
≡ 235924 mod 727 ≡ 376 mod 727

Es gilt also: 698131 ≡ 376 mod 727

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>73 = 1⋅68 + 5
=>68 = 13⋅5 + 3
=>5 = 1⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(73,68)=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= 3-1⋅2
2= 5-1⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(5 -1⋅ 3)
= 1⋅3 -1⋅5 +1⋅ 3)
= -1⋅5 +2⋅ 3 (=1)
3= 68-13⋅5 eingesetzt in die Zeile drüber: 1 = -1⋅5 +2⋅(68 -13⋅ 5)
= -1⋅5 +2⋅68 -26⋅ 5)
= 2⋅68 -27⋅ 5 (=1)
5= 73-1⋅68 eingesetzt in die Zeile drüber: 1 = 2⋅68 -27⋅(73 -1⋅ 68)
= 2⋅68 -27⋅73 +27⋅ 68)
= -27⋅73 +29⋅ 68 (=1)

Es gilt also: ggt(73,68)=1 = -27⋅73 +29⋅68

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

1 +27⋅73 = +29⋅68

Es gilt also: 29⋅68 = 27⋅73 +1

Somit 29⋅68 = 1 mod 73

29 ist also das Inverse von 68 mod 73

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden