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: (403 - 1608) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(403 - 1608) mod 8 ≡ (403 mod 8 - 1608 mod 8) mod 8.

403 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 403 = 400+3 = 8 ⋅ 50 +3.

1608 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 1608 = 1600+8 = 8 ⋅ 200 +8.

Somit gilt:

(403 - 1608) mod 8 ≡ (3 - 0) mod 8 ≡ 3 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (28 ⋅ 71) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(28 ⋅ 71) mod 6 ≡ (28 mod 6 ⋅ 71 mod 6) mod 6.

28 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 28 = 24 + 4 = 4 ⋅ 6 + 4 ist.

71 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 71 = 66 + 5 = 11 ⋅ 6 + 5 ist.

Somit gilt:

(28 ⋅ 71) mod 6 ≡ (4 ⋅ 5) mod 6 ≡ 20 mod 6 ≡ 2 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 733128 mod 983.

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. 733 -> x
2. mod(x²,983) -> 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: 7331=733

2: 7332=7331+1=7331⋅7331 ≡ 733⋅733=537289 ≡ 571 mod 983

4: 7334=7332+2=7332⋅7332 ≡ 571⋅571=326041 ≡ 668 mod 983

8: 7338=7334+4=7334⋅7334 ≡ 668⋅668=446224 ≡ 925 mod 983

16: 73316=7338+8=7338⋅7338 ≡ 925⋅925=855625 ≡ 415 mod 983

32: 73332=73316+16=73316⋅73316 ≡ 415⋅415=172225 ≡ 200 mod 983

64: 73364=73332+32=73332⋅73332 ≡ 200⋅200=40000 ≡ 680 mod 983

128: 733128=73364+64=73364⋅73364 ≡ 680⋅680=462400 ≡ 390 mod 983

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 194153 mod 389.

Lösung einblenden

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

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

153 = 128+16+8+1

1: 1941=194

2: 1942=1941+1=1941⋅1941 ≡ 194⋅194=37636 ≡ 292 mod 389

4: 1944=1942+2=1942⋅1942 ≡ 292⋅292=85264 ≡ 73 mod 389

8: 1948=1944+4=1944⋅1944 ≡ 73⋅73=5329 ≡ 272 mod 389

16: 19416=1948+8=1948⋅1948 ≡ 272⋅272=73984 ≡ 74 mod 389

32: 19432=19416+16=19416⋅19416 ≡ 74⋅74=5476 ≡ 30 mod 389

64: 19464=19432+32=19432⋅19432 ≡ 30⋅30=900 ≡ 122 mod 389

128: 194128=19464+64=19464⋅19464 ≡ 122⋅122=14884 ≡ 102 mod 389

194153

= 194128+16+8+1

= 194128⋅19416⋅1948⋅1941

102 ⋅ 74 ⋅ 272 ⋅ 194 mod 389
7548 ⋅ 272 ⋅ 194 mod 389 ≡ 157 ⋅ 272 ⋅ 194 mod 389
42704 ⋅ 194 mod 389 ≡ 303 ⋅ 194 mod 389
58782 mod 389 ≡ 43 mod 389

Es gilt also: 194153 ≡ 43 mod 389

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 59 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 59

=>73 = 1⋅59 + 14
=>59 = 4⋅14 + 3
=>14 = 4⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(73,59)=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= 14-4⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(14 -4⋅ 3)
= 1⋅3 -1⋅14 +4⋅ 3)
= -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14 eingesetzt in die Zeile drüber: 1 = -1⋅14 +5⋅(59 -4⋅ 14)
= -1⋅14 +5⋅59 -20⋅ 14)
= 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59 eingesetzt in die Zeile drüber: 1 = 5⋅59 -21⋅(73 -1⋅ 59)
= 5⋅59 -21⋅73 +21⋅ 59)
= -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73

Schlüsselpaar für RSA

Beispiel:

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