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: (29994 - 181) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(29994 - 181) mod 6 ≡ (29994 mod 6 - 181 mod 6) mod 6.

29994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 29994 = 30000-6 = 6 ⋅ 5000 -6 = 6 ⋅ 5000 - 6 + 0.

181 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 181 = 180+1 = 6 ⋅ 30 +1.

Somit gilt:

(29994 - 181) mod 6 ≡ (0 - 1) mod 6 ≡ -1 mod 6 ≡ 5 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (85 ⋅ 69) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(85 ⋅ 69) mod 5 ≡ (85 mod 5 ⋅ 69 mod 5) mod 5.

85 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 85 = 85 + 0 = 17 ⋅ 5 + 0 ist.

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

Somit gilt:

(85 ⋅ 69) mod 5 ≡ (0 ⋅ 4) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 21716 mod 509.

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. 217 -> x
2. mod(x²,509) -> 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: 2171=217

2: 2172=2171+1=2171⋅2171 ≡ 217⋅217=47089 ≡ 261 mod 509

4: 2174=2172+2=2172⋅2172 ≡ 261⋅261=68121 ≡ 424 mod 509

8: 2178=2174+4=2174⋅2174 ≡ 424⋅424=179776 ≡ 99 mod 509

16: 21716=2178+8=2178⋅2178 ≡ 99⋅99=9801 ≡ 130 mod 509

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 401183 mod 787.

Lösung einblenden

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

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

183 = 128+32+16+4+2+1

1: 4011=401

2: 4012=4011+1=4011⋅4011 ≡ 401⋅401=160801 ≡ 253 mod 787

4: 4014=4012+2=4012⋅4012 ≡ 253⋅253=64009 ≡ 262 mod 787

8: 4018=4014+4=4014⋅4014 ≡ 262⋅262=68644 ≡ 175 mod 787

16: 40116=4018+8=4018⋅4018 ≡ 175⋅175=30625 ≡ 719 mod 787

32: 40132=40116+16=40116⋅40116 ≡ 719⋅719=516961 ≡ 689 mod 787

64: 40164=40132+32=40132⋅40132 ≡ 689⋅689=474721 ≡ 160 mod 787

128: 401128=40164+64=40164⋅40164 ≡ 160⋅160=25600 ≡ 416 mod 787

401183

= 401128+32+16+4+2+1

= 401128⋅40132⋅40116⋅4014⋅4012⋅4011

416 ⋅ 689 ⋅ 719 ⋅ 262 ⋅ 253 ⋅ 401 mod 787
286624 ⋅ 719 ⋅ 262 ⋅ 253 ⋅ 401 mod 787 ≡ 156 ⋅ 719 ⋅ 262 ⋅ 253 ⋅ 401 mod 787
112164 ⋅ 262 ⋅ 253 ⋅ 401 mod 787 ≡ 410 ⋅ 262 ⋅ 253 ⋅ 401 mod 787
107420 ⋅ 253 ⋅ 401 mod 787 ≡ 388 ⋅ 253 ⋅ 401 mod 787
98164 ⋅ 401 mod 787 ≡ 576 ⋅ 401 mod 787
230976 mod 787 ≡ 385 mod 787

Es gilt also: 401183 ≡ 385 mod 787

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 33 ⋅ x ≡ 1 mod 71 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 71 und 33

=>71 = 2⋅33 + 5
=>33 = 6⋅5 + 3
=>5 = 1⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(71,33)=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= 3-1⋅2
2= 5-1⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(5 -1⋅ 3)
= 1⋅3 -1⋅5 +1⋅ 3)
= -1⋅5 +2⋅ 3 (=1)
3= 33-6⋅5 eingesetzt in die Zeile drüber: 1 = -1⋅5 +2⋅(33 -6⋅ 5)
= -1⋅5 +2⋅33 -12⋅ 5)
= 2⋅33 -13⋅ 5 (=1)
5= 71-2⋅33 eingesetzt in die Zeile drüber: 1 = 2⋅33 -13⋅(71 -2⋅ 33)
= 2⋅33 -13⋅71 +26⋅ 33)
= -13⋅71 +28⋅ 33 (=1)

Es gilt also: ggt(71,33)=1 = -13⋅71 +28⋅33

oder wenn man -13⋅71 auf die linke Seite bringt:

1 +13⋅71 = +28⋅33

Es gilt also: 28⋅33 = 13⋅71 +1

Somit 28⋅33 = 1 mod 71

28 ist also das Inverse von 33 mod 71

Schlüsselpaar für RSA

Beispiel:

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