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: (17994 + 18002) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(17994 + 18002) mod 6 ≡ (17994 mod 6 + 18002 mod 6) mod 6.

17994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 17994 = 18000-6 = 6 ⋅ 3000 -6 = 6 ⋅ 3000 - 6 + 0.

18002 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 18002 = 18000+2 = 6 ⋅ 3000 +2.

Somit gilt:

(17994 + 18002) mod 6 ≡ (0 + 2) mod 6 ≡ 2 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (20 ⋅ 41) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(20 ⋅ 41) mod 7 ≡ (20 mod 7 ⋅ 41 mod 7) mod 7.

20 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 20 = 14 + 6 = 2 ⋅ 7 + 6 ist.

41 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 41 = 35 + 6 = 5 ⋅ 7 + 6 ist.

Somit gilt:

(20 ⋅ 41) mod 7 ≡ (6 ⋅ 6) mod 7 ≡ 36 mod 7 ≡ 1 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 297128 mod 509.

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. 297 -> 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: 2971=297

2: 2972=2971+1=2971⋅2971 ≡ 297⋅297=88209 ≡ 152 mod 509

4: 2974=2972+2=2972⋅2972 ≡ 152⋅152=23104 ≡ 199 mod 509

8: 2978=2974+4=2974⋅2974 ≡ 199⋅199=39601 ≡ 408 mod 509

16: 29716=2978+8=2978⋅2978 ≡ 408⋅408=166464 ≡ 21 mod 509

32: 29732=29716+16=29716⋅29716 ≡ 21⋅21=441 ≡ 441 mod 509

64: 29764=29732+32=29732⋅29732 ≡ 441⋅441=194481 ≡ 43 mod 509

128: 297128=29764+64=29764⋅29764 ≡ 43⋅43=1849 ≡ 322 mod 509

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 43391 mod 503.

Lösung einblenden

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

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

91 = 64+16+8+2+1

1: 4331=433

2: 4332=4331+1=4331⋅4331 ≡ 433⋅433=187489 ≡ 373 mod 503

4: 4334=4332+2=4332⋅4332 ≡ 373⋅373=139129 ≡ 301 mod 503

8: 4338=4334+4=4334⋅4334 ≡ 301⋅301=90601 ≡ 61 mod 503

16: 43316=4338+8=4338⋅4338 ≡ 61⋅61=3721 ≡ 200 mod 503

32: 43332=43316+16=43316⋅43316 ≡ 200⋅200=40000 ≡ 263 mod 503

64: 43364=43332+32=43332⋅43332 ≡ 263⋅263=69169 ≡ 258 mod 503

43391

= 43364+16+8+2+1

= 43364⋅43316⋅4338⋅4332⋅4331

258 ⋅ 200 ⋅ 61 ⋅ 373 ⋅ 433 mod 503
51600 ⋅ 61 ⋅ 373 ⋅ 433 mod 503 ≡ 294 ⋅ 61 ⋅ 373 ⋅ 433 mod 503
17934 ⋅ 373 ⋅ 433 mod 503 ≡ 329 ⋅ 373 ⋅ 433 mod 503
122717 ⋅ 433 mod 503 ≡ 488 ⋅ 433 mod 503
211304 mod 503 ≡ 44 mod 503

Es gilt also: 43391 ≡ 44 mod 503

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 53 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 53

=>89 = 1⋅53 + 36
=>53 = 1⋅36 + 17
=>36 = 2⋅17 + 2
=>17 = 8⋅2 + 1
=>2 = 2⋅1 + 0

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

Es gilt also: ggt(89,53)=1 = -25⋅89 +42⋅53

oder wenn man -25⋅89 auf die linke Seite bringt:

1 +25⋅89 = +42⋅53

Es gilt also: 42⋅53 = 25⋅89 +1

Somit 42⋅53 = 1 mod 89

42 ist also das Inverse von 53 mod 89

Schlüsselpaar für RSA

Beispiel:

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