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: (1800 + 3604) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1800 + 3604) mod 9 ≡ (1800 mod 9 + 3604 mod 9) mod 9.

1800 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 1800 = 1800+0 = 9 ⋅ 200 +0.

3604 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 3604 = 3600+4 = 9 ⋅ 400 +4.

Somit gilt:

(1800 + 3604) mod 9 ≡ (0 + 4) mod 9 ≡ 4 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (99 ⋅ 97) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 97) mod 4 ≡ (99 mod 4 ⋅ 97 mod 4) mod 4.

99 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 99 = 96 + 3 = 24 ⋅ 4 + 3 ist.

97 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 97 = 96 + 1 = 24 ⋅ 4 + 1 ist.

Somit gilt:

(99 ⋅ 97) mod 4 ≡ (3 ⋅ 1) mod 4 ≡ 3 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 635128 mod 991.

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. 635 -> x
2. mod(x²,991) -> 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: 6351=635

2: 6352=6351+1=6351⋅6351 ≡ 635⋅635=403225 ≡ 879 mod 991

4: 6354=6352+2=6352⋅6352 ≡ 879⋅879=772641 ≡ 652 mod 991

8: 6358=6354+4=6354⋅6354 ≡ 652⋅652=425104 ≡ 956 mod 991

16: 63516=6358+8=6358⋅6358 ≡ 956⋅956=913936 ≡ 234 mod 991

32: 63532=63516+16=63516⋅63516 ≡ 234⋅234=54756 ≡ 251 mod 991

64: 63564=63532+32=63532⋅63532 ≡ 251⋅251=63001 ≡ 568 mod 991

128: 635128=63564+64=63564⋅63564 ≡ 568⋅568=322624 ≡ 549 mod 991

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 249106 mod 617.

Lösung einblenden

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

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

106 = 64+32+8+2

1: 2491=249

2: 2492=2491+1=2491⋅2491 ≡ 249⋅249=62001 ≡ 301 mod 617

4: 2494=2492+2=2492⋅2492 ≡ 301⋅301=90601 ≡ 519 mod 617

8: 2498=2494+4=2494⋅2494 ≡ 519⋅519=269361 ≡ 349 mod 617

16: 24916=2498+8=2498⋅2498 ≡ 349⋅349=121801 ≡ 252 mod 617

32: 24932=24916+16=24916⋅24916 ≡ 252⋅252=63504 ≡ 570 mod 617

64: 24964=24932+32=24932⋅24932 ≡ 570⋅570=324900 ≡ 358 mod 617

249106

= 24964+32+8+2

= 24964⋅24932⋅2498⋅2492

358 ⋅ 570 ⋅ 349 ⋅ 301 mod 617
204060 ⋅ 349 ⋅ 301 mod 617 ≡ 450 ⋅ 349 ⋅ 301 mod 617
157050 ⋅ 301 mod 617 ≡ 332 ⋅ 301 mod 617
99932 mod 617 ≡ 595 mod 617

Es gilt also: 249106 ≡ 595 mod 617

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>79 = 1⋅42 + 37
=>42 = 1⋅37 + 5
=>37 = 7⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(79,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= 5-2⋅2
2= 37-7⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(37 -7⋅ 5)
= 1⋅5 -2⋅37 +14⋅ 5)
= -2⋅37 +15⋅ 5 (=1)
5= 42-1⋅37 eingesetzt in die Zeile drüber: 1 = -2⋅37 +15⋅(42 -1⋅ 37)
= -2⋅37 +15⋅42 -15⋅ 37)
= 15⋅42 -17⋅ 37 (=1)
37= 79-1⋅42 eingesetzt in die Zeile drüber: 1 = 15⋅42 -17⋅(79 -1⋅ 42)
= 15⋅42 -17⋅79 +17⋅ 42)
= -17⋅79 +32⋅ 42 (=1)

Es gilt also: ggt(79,42)=1 = -17⋅79 +32⋅42

oder wenn man -17⋅79 auf die linke Seite bringt:

1 +17⋅79 = +32⋅42

Es gilt also: 32⋅42 = 17⋅79 +1

Somit 32⋅42 = 1 mod 79

32 ist also das Inverse von 42 mod 79

Schlüsselpaar für RSA

Beispiel:

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