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: (5998 + 8999) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(5998 + 8999) mod 3 ≡ (5998 mod 3 + 8999 mod 3) mod 3.

5998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 5998 = 6000-2 = 3 ⋅ 2000 -2 = 3 ⋅ 2000 - 3 + 1.

8999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 8999 = 9000-1 = 3 ⋅ 3000 -1 = 3 ⋅ 3000 - 3 + 2.

Somit gilt:

(5998 + 8999) mod 3 ≡ (1 + 2) mod 3 ≡ 3 mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (67 ⋅ 96) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(67 ⋅ 96) mod 9 ≡ (67 mod 9 ⋅ 96 mod 9) mod 9.

67 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 67 = 63 + 4 = 7 ⋅ 9 + 4 ist.

96 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 96 = 90 + 6 = 10 ⋅ 9 + 6 ist.

Somit gilt:

(67 ⋅ 96) mod 9 ≡ (4 ⋅ 6) mod 9 ≡ 24 mod 9 ≡ 6 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 605128 mod 907.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 605 -> x
2. mod(x²,907) -> 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: 6051=605

2: 6052=6051+1=6051⋅6051 ≡ 605⋅605=366025 ≡ 504 mod 907

4: 6054=6052+2=6052⋅6052 ≡ 504⋅504=254016 ≡ 56 mod 907

8: 6058=6054+4=6054⋅6054 ≡ 56⋅56=3136 ≡ 415 mod 907

16: 60516=6058+8=6058⋅6058 ≡ 415⋅415=172225 ≡ 802 mod 907

32: 60532=60516+16=60516⋅60516 ≡ 802⋅802=643204 ≡ 141 mod 907

64: 60564=60532+32=60532⋅60532 ≡ 141⋅141=19881 ≡ 834 mod 907

128: 605128=60564+64=60564⋅60564 ≡ 834⋅834=695556 ≡ 794 mod 907

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 326143 mod 359.

Lösung einblenden

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

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

143 = 128+8+4+2+1

1: 3261=326

2: 3262=3261+1=3261⋅3261 ≡ 326⋅326=106276 ≡ 12 mod 359

4: 3264=3262+2=3262⋅3262 ≡ 12⋅12=144 ≡ 144 mod 359

8: 3268=3264+4=3264⋅3264 ≡ 144⋅144=20736 ≡ 273 mod 359

16: 32616=3268+8=3268⋅3268 ≡ 273⋅273=74529 ≡ 216 mod 359

32: 32632=32616+16=32616⋅32616 ≡ 216⋅216=46656 ≡ 345 mod 359

64: 32664=32632+32=32632⋅32632 ≡ 345⋅345=119025 ≡ 196 mod 359

128: 326128=32664+64=32664⋅32664 ≡ 196⋅196=38416 ≡ 3 mod 359

326143

= 326128+8+4+2+1

= 326128⋅3268⋅3264⋅3262⋅3261

3 ⋅ 273 ⋅ 144 ⋅ 12 ⋅ 326 mod 359
819 ⋅ 144 ⋅ 12 ⋅ 326 mod 359 ≡ 101 ⋅ 144 ⋅ 12 ⋅ 326 mod 359
14544 ⋅ 12 ⋅ 326 mod 359 ≡ 184 ⋅ 12 ⋅ 326 mod 359
2208 ⋅ 326 mod 359 ≡ 54 ⋅ 326 mod 359
17604 mod 359 ≡ 13 mod 359

Es gilt also: 326143 ≡ 13 mod 359

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 18 ⋅ x ≡ 1 mod 61 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 61 und 18

=>61 = 3⋅18 + 7
=>18 = 2⋅7 + 4
=>7 = 1⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(61,18)=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= 4-1⋅3
3= 7-1⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(7 -1⋅ 4)
= 1⋅4 -1⋅7 +1⋅ 4)
= -1⋅7 +2⋅ 4 (=1)
4= 18-2⋅7 eingesetzt in die Zeile drüber: 1 = -1⋅7 +2⋅(18 -2⋅ 7)
= -1⋅7 +2⋅18 -4⋅ 7)
= 2⋅18 -5⋅ 7 (=1)
7= 61-3⋅18 eingesetzt in die Zeile drüber: 1 = 2⋅18 -5⋅(61 -3⋅ 18)
= 2⋅18 -5⋅61 +15⋅ 18)
= -5⋅61 +17⋅ 18 (=1)

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

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

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61

Schlüsselpaar für RSA

Beispiel:

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