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: (25004 + 246) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(25004 + 246) mod 5 ≡ (25004 mod 5 + 246 mod 5) mod 5.

25004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 25004 = 25000+4 = 5 ⋅ 5000 +4.

246 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 246 = 240+6 = 5 ⋅ 48 +6.

Somit gilt:

(25004 + 246) mod 5 ≡ (4 + 1) mod 5 ≡ 5 mod 5 ≡ 0 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (19 ⋅ 61) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(19 ⋅ 61) mod 4 ≡ (19 mod 4 ⋅ 61 mod 4) mod 4.

19 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 19 = 16 + 3 = 4 ⋅ 4 + 3 ist.

61 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 61 = 60 + 1 = 15 ⋅ 4 + 1 ist.

Somit gilt:

(19 ⋅ 61) mod 4 ≡ (3 ⋅ 1) mod 4 ≡ 3 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 38716 mod 643.

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. 387 -> x
2. mod(x²,643) -> 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: 3871=387

2: 3872=3871+1=3871⋅3871 ≡ 387⋅387=149769 ≡ 593 mod 643

4: 3874=3872+2=3872⋅3872 ≡ 593⋅593=351649 ≡ 571 mod 643

8: 3878=3874+4=3874⋅3874 ≡ 571⋅571=326041 ≡ 40 mod 643

16: 38716=3878+8=3878⋅3878 ≡ 40⋅40=1600 ≡ 314 mod 643

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 283143 mod 719.

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: 2831=283

2: 2832=2831+1=2831⋅2831 ≡ 283⋅283=80089 ≡ 280 mod 719

4: 2834=2832+2=2832⋅2832 ≡ 280⋅280=78400 ≡ 29 mod 719

8: 2838=2834+4=2834⋅2834 ≡ 29⋅29=841 ≡ 122 mod 719

16: 28316=2838+8=2838⋅2838 ≡ 122⋅122=14884 ≡ 504 mod 719

32: 28332=28316+16=28316⋅28316 ≡ 504⋅504=254016 ≡ 209 mod 719

64: 28364=28332+32=28332⋅28332 ≡ 209⋅209=43681 ≡ 541 mod 719

128: 283128=28364+64=28364⋅28364 ≡ 541⋅541=292681 ≡ 48 mod 719

283143

= 283128+8+4+2+1

= 283128⋅2838⋅2834⋅2832⋅2831

48 ⋅ 122 ⋅ 29 ⋅ 280 ⋅ 283 mod 719
5856 ⋅ 29 ⋅ 280 ⋅ 283 mod 719 ≡ 104 ⋅ 29 ⋅ 280 ⋅ 283 mod 719
3016 ⋅ 280 ⋅ 283 mod 719 ≡ 140 ⋅ 280 ⋅ 283 mod 719
39200 ⋅ 283 mod 719 ≡ 374 ⋅ 283 mod 719
105842 mod 719 ≡ 149 mod 719

Es gilt also: 283143 ≡ 149 mod 719

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

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

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

Es gilt also: ggt(67,25)=1 = 3⋅67 -8⋅25

oder wenn man 3⋅67 auf die linke Seite bringt:

1 -3⋅67 = -8⋅25

-8⋅25 = -3⋅67 + 1 |+67⋅25

-8⋅25 + 67⋅25 = -3⋅67 + 67⋅25 + 1

(-8 + 67) ⋅ 25 = (-3 + 25) ⋅ 67 + 1

59⋅25 = 22⋅67 + 1

Es gilt also: 59⋅25 = 22⋅67 +1

Somit 59⋅25 = 1 mod 67

59 ist also das Inverse von 25 mod 67

Schlüsselpaar für RSA

Beispiel:

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