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: (93 + 3002) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 + 3002) mod 3 ≡ (93 mod 3 + 3002 mod 3) mod 3.

93 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 93 = 90+3 = 3 ⋅ 30 +3.

3002 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 3002 = 3000+2 = 3 ⋅ 1000 +2.

Somit gilt:

(93 + 3002) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (17 ⋅ 56) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(17 ⋅ 56) mod 6 ≡ (17 mod 6 ⋅ 56 mod 6) mod 6.

17 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 17 = 12 + 5 = 2 ⋅ 6 + 5 ist.

56 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 56 = 54 + 2 = 9 ⋅ 6 + 2 ist.

Somit gilt:

(17 ⋅ 56) mod 6 ≡ (5 ⋅ 2) mod 6 ≡ 10 mod 6 ≡ 4 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 56816 mod 701.

Lösung einblenden

Die 16 im Exponent ist ja ein reine 2er-Potenz (24).

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. 568 -> x
2. mod(x²,701) -> 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: 5681=568

2: 5682=5681+1=5681⋅5681 ≡ 568⋅568=322624 ≡ 164 mod 701

4: 5684=5682+2=5682⋅5682 ≡ 164⋅164=26896 ≡ 258 mod 701

8: 5688=5684+4=5684⋅5684 ≡ 258⋅258=66564 ≡ 670 mod 701

16: 56816=5688+8=5688⋅5688 ≡ 670⋅670=448900 ≡ 260 mod 701

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 361229 mod 971.

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: 3611=361

2: 3612=3611+1=3611⋅3611 ≡ 361⋅361=130321 ≡ 207 mod 971

4: 3614=3612+2=3612⋅3612 ≡ 207⋅207=42849 ≡ 125 mod 971

8: 3618=3614+4=3614⋅3614 ≡ 125⋅125=15625 ≡ 89 mod 971

16: 36116=3618+8=3618⋅3618 ≡ 89⋅89=7921 ≡ 153 mod 971

32: 36132=36116+16=36116⋅36116 ≡ 153⋅153=23409 ≡ 105 mod 971

64: 36164=36132+32=36132⋅36132 ≡ 105⋅105=11025 ≡ 344 mod 971

128: 361128=36164+64=36164⋅36164 ≡ 344⋅344=118336 ≡ 845 mod 971

361229

= 361128+64+32+4+1

= 361128⋅36164⋅36132⋅3614⋅3611

845 ⋅ 344 ⋅ 105 ⋅ 125 ⋅ 361 mod 971
290680 ⋅ 105 ⋅ 125 ⋅ 361 mod 971 ≡ 351 ⋅ 105 ⋅ 125 ⋅ 361 mod 971
36855 ⋅ 125 ⋅ 361 mod 971 ≡ 928 ⋅ 125 ⋅ 361 mod 971
116000 ⋅ 361 mod 971 ≡ 451 ⋅ 361 mod 971
162811 mod 971 ≡ 654 mod 971

Es gilt also: 361229 ≡ 654 mod 971

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 42 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 42

=>67 = 1⋅42 + 25
=>42 = 1⋅25 + 17
=>25 = 1⋅17 + 8
=>17 = 2⋅8 + 1
=>8 = 8⋅1 + 0

also gilt: ggt(67,42)=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= 17-2⋅8
8= 25-1⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -2⋅(25 -1⋅ 17)
= 1⋅17 -2⋅25 +2⋅ 17)
= -2⋅25 +3⋅ 17 (=1)
17= 42-1⋅25 eingesetzt in die Zeile drüber: 1 = -2⋅25 +3⋅(42 -1⋅ 25)
= -2⋅25 +3⋅42 -3⋅ 25)
= 3⋅42 -5⋅ 25 (=1)
25= 67-1⋅42 eingesetzt in die Zeile drüber: 1 = 3⋅42 -5⋅(67 -1⋅ 42)
= 3⋅42 -5⋅67 +5⋅ 42)
= -5⋅67 +8⋅ 42 (=1)

Es gilt also: ggt(67,42)=1 = -5⋅67 +8⋅42

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

1 +5⋅67 = +8⋅42

Es gilt also: 8⋅42 = 5⋅67 +1

Somit 8⋅42 = 1 mod 67

8 ist also das Inverse von 42 mod 67

Schlüsselpaar für RSA

Beispiel:

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