Aufgabenbeispiele von MGK Klasse 10

Durch Aktualisieren des Browsers (z.B. mit Taste F5) kann man neue Beispielaufgaben sehen


Modulo addieren

Beispiel:

Berechne ohne WTR: (15999 + 160) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(15999 + 160) mod 4 ≡ (15999 mod 4 + 160 mod 4) mod 4.

15999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 15999 = 15000+999 = 4 ⋅ 3750 +999.

160 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 160 = 160+0 = 4 ⋅ 40 +0.

Somit gilt:

(15999 + 160) mod 4 ≡ (3 + 0) mod 4 ≡ 3 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (89 ⋅ 43) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(89 ⋅ 43) mod 4 ≡ (89 mod 4 ⋅ 43 mod 4) mod 4.

89 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 89 = 88 + 1 = 22 ⋅ 4 + 1 ist.

43 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 43 = 40 + 3 = 10 ⋅ 4 + 3 ist.

Somit gilt:

(89 ⋅ 43) mod 4 ≡ (1 ⋅ 3) mod 4 ≡ 3 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 23564 mod 433.

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. 235 -> x
2. mod(x²,433) -> 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: 2351=235

2: 2352=2351+1=2351⋅2351 ≡ 235⋅235=55225 ≡ 234 mod 433

4: 2354=2352+2=2352⋅2352 ≡ 234⋅234=54756 ≡ 198 mod 433

8: 2358=2354+4=2354⋅2354 ≡ 198⋅198=39204 ≡ 234 mod 433

16: 23516=2358+8=2358⋅2358 ≡ 234⋅234=54756 ≡ 198 mod 433

32: 23532=23516+16=23516⋅23516 ≡ 198⋅198=39204 ≡ 234 mod 433

64: 23564=23532+32=23532⋅23532 ≡ 234⋅234=54756 ≡ 198 mod 433

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 264233 mod 271.

Lösung einblenden

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

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

233 = 128+64+32+8+1

1: 2641=264

2: 2642=2641+1=2641⋅2641 ≡ 264⋅264=69696 ≡ 49 mod 271

4: 2644=2642+2=2642⋅2642 ≡ 49⋅49=2401 ≡ 233 mod 271

8: 2648=2644+4=2644⋅2644 ≡ 233⋅233=54289 ≡ 89 mod 271

16: 26416=2648+8=2648⋅2648 ≡ 89⋅89=7921 ≡ 62 mod 271

32: 26432=26416+16=26416⋅26416 ≡ 62⋅62=3844 ≡ 50 mod 271

64: 26464=26432+32=26432⋅26432 ≡ 50⋅50=2500 ≡ 61 mod 271

128: 264128=26464+64=26464⋅26464 ≡ 61⋅61=3721 ≡ 198 mod 271

264233

= 264128+64+32+8+1

= 264128⋅26464⋅26432⋅2648⋅2641

198 ⋅ 61 ⋅ 50 ⋅ 89 ⋅ 264 mod 271
12078 ⋅ 50 ⋅ 89 ⋅ 264 mod 271 ≡ 154 ⋅ 50 ⋅ 89 ⋅ 264 mod 271
7700 ⋅ 89 ⋅ 264 mod 271 ≡ 112 ⋅ 89 ⋅ 264 mod 271
9968 ⋅ 264 mod 271 ≡ 212 ⋅ 264 mod 271
55968 mod 271 ≡ 142 mod 271

Es gilt also: 264233 ≡ 142 mod 271

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>97 = 1⋅87 + 10
=>87 = 8⋅10 + 7
=>10 = 1⋅7 + 3
=>7 = 2⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(97,87)=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-2⋅3
3= 10-1⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -2⋅(10 -1⋅ 7)
= 1⋅7 -2⋅10 +2⋅ 7)
= -2⋅10 +3⋅ 7 (=1)
7= 87-8⋅10 eingesetzt in die Zeile drüber: 1 = -2⋅10 +3⋅(87 -8⋅ 10)
= -2⋅10 +3⋅87 -24⋅ 10)
= 3⋅87 -26⋅ 10 (=1)
10= 97-1⋅87 eingesetzt in die Zeile drüber: 1 = 3⋅87 -26⋅(97 -1⋅ 87)
= 3⋅87 -26⋅97 +26⋅ 87)
= -26⋅97 +29⋅ 87 (=1)

Es gilt also: ggt(97,87)=1 = -26⋅97 +29⋅87

oder wenn man -26⋅97 auf die linke Seite bringt:

1 +26⋅97 = +29⋅87

Es gilt also: 29⋅87 = 26⋅97 +1

Somit 29⋅87 = 1 mod 97

29 ist also das Inverse von 87 mod 97

Schlüsselpaar für RSA

Beispiel:

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