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: (1202 - 8997) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1202 - 8997) mod 3 ≡ (1202 mod 3 - 8997 mod 3) mod 3.

1202 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1202 = 1200+2 = 3 ⋅ 400 +2.

8997 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 8997 = 9000-3 = 3 ⋅ 3000 -3 = 3 ⋅ 3000 - 3 + 0.

Somit gilt:

(1202 - 8997) mod 3 ≡ (2 - 0) mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (100 ⋅ 85) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(100 ⋅ 85) mod 3 ≡ (100 mod 3 ⋅ 85 mod 3) mod 3.

100 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 100 = 99 + 1 = 33 ⋅ 3 + 1 ist.

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

Somit gilt:

(100 ⋅ 85) mod 3 ≡ (1 ⋅ 1) mod 3 ≡ 1 mod 3.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 61332 mod 829.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 613 -> 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: 6131=613

2: 6132=6131+1=6131⋅6131 ≡ 613⋅613=375769 ≡ 232 mod 829

4: 6134=6132+2=6132⋅6132 ≡ 232⋅232=53824 ≡ 768 mod 829

8: 6138=6134+4=6134⋅6134 ≡ 768⋅768=589824 ≡ 405 mod 829

16: 61316=6138+8=6138⋅6138 ≡ 405⋅405=164025 ≡ 712 mod 829

32: 61332=61316+16=61316⋅61316 ≡ 712⋅712=506944 ≡ 425 mod 829

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 782209 mod 787.

Lösung einblenden

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

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

209 = 128+64+16+1

1: 7821=782

2: 7822=7821+1=7821⋅7821 ≡ 782⋅782=611524 ≡ 25 mod 787

4: 7824=7822+2=7822⋅7822 ≡ 25⋅25=625 ≡ 625 mod 787

8: 7828=7824+4=7824⋅7824 ≡ 625⋅625=390625 ≡ 273 mod 787

16: 78216=7828+8=7828⋅7828 ≡ 273⋅273=74529 ≡ 551 mod 787

32: 78232=78216+16=78216⋅78216 ≡ 551⋅551=303601 ≡ 606 mod 787

64: 78264=78232+32=78232⋅78232 ≡ 606⋅606=367236 ≡ 494 mod 787

128: 782128=78264+64=78264⋅78264 ≡ 494⋅494=244036 ≡ 66 mod 787

782209

= 782128+64+16+1

= 782128⋅78264⋅78216⋅7821

≡ 66 ⋅ 494 ⋅ 551 ⋅ 782 mod 787
≡ 32604 ⋅ 551 ⋅ 782 mod 787 ≡ 337 ⋅ 551 ⋅ 782 mod 787
≡ 185687 ⋅ 782 mod 787 ≡ 742 ⋅ 782 mod 787
≡ 580244 mod 787 ≡ 225 mod 787

Es gilt also: 782209 ≡ 225 mod 787

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 83 ⋅ x ≡ 1 mod 97 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 97 und 83

=>97 = 1⋅83 + 14
=>83 = 5⋅14 + 13
=>14 = 1⋅13 + 1
=>13 = 13⋅1 + 0

also gilt: ggt(97,83)=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= 14-1⋅13
13= 83-5⋅14 eingesetzt in die Zeile drüber: 1 = 1⋅14 -1⋅(83 -5⋅ 14)
= 1⋅14 -1⋅83 +5⋅ 14)
= -1⋅83 +6⋅ 14 (=1)
14= 97-1⋅83 eingesetzt in die Zeile drüber: 1 = -1⋅83 +6⋅(97 -1⋅ 83)
= -1⋅83 +6⋅97 -6⋅ 83)
= 6⋅97 -7⋅ 83 (=1)

Es gilt also: ggt(97,83)=1 = 6⋅97 -7⋅83

oder wenn man 6⋅97 auf die linke Seite bringt:

1 -6⋅97 = -7⋅83

-7⋅83 = -6⋅97 + 1 |+97⋅83

-7⋅83 + 97⋅83 = -6⋅97 + 97⋅83 + 1

(-7 + 97) ⋅ 83 = (-6 + 83) ⋅ 97 + 1

90⋅83 = 77⋅97 + 1

Es gilt also: 90⋅83 = 77⋅97 +1

Somit 90⋅83 = 1 mod 97

90 ist also das Inverse von 83 mod 97

Schlüsselpaar für RSA

Beispiel:

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

Lösung einblenden