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: (63 + 5999) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 + 5999) mod 3 ≡ (63 mod 3 + 5999 mod 3) mod 3.

63 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 63 = 60+3 = 3 ⋅ 20 +3.

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

Somit gilt:

(63 + 5999) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (66 ⋅ 98) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(66 ⋅ 98) mod 5 ≡ (66 mod 5 ⋅ 98 mod 5) mod 5.

66 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 66 = 65 + 1 = 13 ⋅ 5 + 1 ist.

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 95 + 3 = 19 ⋅ 5 + 3 ist.

Somit gilt:

(66 ⋅ 98) mod 5 ≡ (1 ⋅ 3) mod 5 ≡ 3 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 68164 mod 877.

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. 681 -> x
2. mod(x²,877) -> 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: 6811=681

2: 6812=6811+1=6811⋅6811 ≡ 681⋅681=463761 ≡ 705 mod 877

4: 6814=6812+2=6812⋅6812 ≡ 705⋅705=497025 ≡ 643 mod 877

8: 6818=6814+4=6814⋅6814 ≡ 643⋅643=413449 ≡ 382 mod 877

16: 68116=6818+8=6818⋅6818 ≡ 382⋅382=145924 ≡ 342 mod 877

32: 68132=68116+16=68116⋅68116 ≡ 342⋅342=116964 ≡ 323 mod 877

64: 68164=68132+32=68132⋅68132 ≡ 323⋅323=104329 ≡ 843 mod 877

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 266209 mod 547.

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: 2661=266

2: 2662=2661+1=2661⋅2661 ≡ 266⋅266=70756 ≡ 193 mod 547

4: 2664=2662+2=2662⋅2662 ≡ 193⋅193=37249 ≡ 53 mod 547

8: 2668=2664+4=2664⋅2664 ≡ 53⋅53=2809 ≡ 74 mod 547

16: 26616=2668+8=2668⋅2668 ≡ 74⋅74=5476 ≡ 6 mod 547

32: 26632=26616+16=26616⋅26616 ≡ 6⋅6=36 ≡ 36 mod 547

64: 26664=26632+32=26632⋅26632 ≡ 36⋅36=1296 ≡ 202 mod 547

128: 266128=26664+64=26664⋅26664 ≡ 202⋅202=40804 ≡ 326 mod 547

266209

= 266128+64+16+1

= 266128⋅26664⋅26616⋅2661

326 ⋅ 202 ⋅ 6 ⋅ 266 mod 547
65852 ⋅ 6 ⋅ 266 mod 547 ≡ 212 ⋅ 6 ⋅ 266 mod 547
1272 ⋅ 266 mod 547 ≡ 178 ⋅ 266 mod 547
47348 mod 547 ≡ 306 mod 547

Es gilt also: 266209 ≡ 306 mod 547

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 80 ⋅ x ≡ 1 mod 101 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 101 und 80

=>101 = 1⋅80 + 21
=>80 = 3⋅21 + 17
=>21 = 1⋅17 + 4
=>17 = 4⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(101,80)=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-4⋅4
4= 21-1⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -4⋅(21 -1⋅ 17)
= 1⋅17 -4⋅21 +4⋅ 17)
= -4⋅21 +5⋅ 17 (=1)
17= 80-3⋅21 eingesetzt in die Zeile drüber: 1 = -4⋅21 +5⋅(80 -3⋅ 21)
= -4⋅21 +5⋅80 -15⋅ 21)
= 5⋅80 -19⋅ 21 (=1)
21= 101-1⋅80 eingesetzt in die Zeile drüber: 1 = 5⋅80 -19⋅(101 -1⋅ 80)
= 5⋅80 -19⋅101 +19⋅ 80)
= -19⋅101 +24⋅ 80 (=1)

Es gilt also: ggt(101,80)=1 = -19⋅101 +24⋅80

oder wenn man -19⋅101 auf die linke Seite bringt:

1 +19⋅101 = +24⋅80

Es gilt also: 24⋅80 = 19⋅101 +1

Somit 24⋅80 = 1 mod 101

24 ist also das Inverse von 80 mod 101

Schlüsselpaar für RSA

Beispiel:

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