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: (1600 - 23997) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1600 - 23997) mod 8 ≡ (1600 mod 8 - 23997 mod 8) mod 8.

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

23997 mod 8 ≡ 5 mod 8 kann man relativ leicht bestimmen, weil ja 23997 = 23000+997 = 8 ⋅ 2875 +997.

Somit gilt:

(1600 - 23997) mod 8 ≡ (0 - 5) mod 8 ≡ -5 mod 8 ≡ 3 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (92 ⋅ 65) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(92 ⋅ 65) mod 6 ≡ (92 mod 6 ⋅ 65 mod 6) mod 6.

92 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 92 = 90 + 2 = 15 ⋅ 6 + 2 ist.

65 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 65 = 60 + 5 = 10 ⋅ 6 + 5 ist.

Somit gilt:

(92 ⋅ 65) mod 6 ≡ (2 ⋅ 5) mod 6 ≡ 10 mod 6 ≡ 4 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 20932 mod 337.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 209 -> x
2. mod(x²,337) -> 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: 2091=209

2: 2092=2091+1=2091⋅2091 ≡ 209⋅209=43681 ≡ 208 mod 337

4: 2094=2092+2=2092⋅2092 ≡ 208⋅208=43264 ≡ 128 mod 337

8: 2098=2094+4=2094⋅2094 ≡ 128⋅128=16384 ≡ 208 mod 337

16: 20916=2098+8=2098⋅2098 ≡ 208⋅208=43264 ≡ 128 mod 337

32: 20932=20916+16=20916⋅20916 ≡ 128⋅128=16384 ≡ 208 mod 337

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 95153 mod 233.

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: 951=95

2: 952=951+1=951⋅951 ≡ 95⋅95=9025 ≡ 171 mod 233

4: 954=952+2=952⋅952 ≡ 171⋅171=29241 ≡ 116 mod 233

8: 958=954+4=954⋅954 ≡ 116⋅116=13456 ≡ 175 mod 233

16: 9516=958+8=958⋅958 ≡ 175⋅175=30625 ≡ 102 mod 233

32: 9532=9516+16=9516⋅9516 ≡ 102⋅102=10404 ≡ 152 mod 233

64: 9564=9532+32=9532⋅9532 ≡ 152⋅152=23104 ≡ 37 mod 233

128: 95128=9564+64=9564⋅9564 ≡ 37⋅37=1369 ≡ 204 mod 233

95153

= 95128+16+8+1

= 95128⋅9516⋅958⋅951

204 ⋅ 102 ⋅ 175 ⋅ 95 mod 233
20808 ⋅ 175 ⋅ 95 mod 233 ≡ 71 ⋅ 175 ⋅ 95 mod 233
12425 ⋅ 95 mod 233 ≡ 76 ⋅ 95 mod 233
7220 mod 233 ≡ 230 mod 233

Es gilt also: 95153 ≡ 230 mod 233

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>59 = 2⋅22 + 15
=>22 = 1⋅15 + 7
=>15 = 2⋅7 + 1
=>7 = 7⋅1 + 0

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

Es gilt also: ggt(59,22)=1 = 3⋅59 -8⋅22

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

1 -3⋅59 = -8⋅22

-8⋅22 = -3⋅59 + 1 |+59⋅22

-8⋅22 + 59⋅22 = -3⋅59 + 59⋅22 + 1

(-8 + 59) ⋅ 22 = (-3 + 22) ⋅ 59 + 1

51⋅22 = 19⋅59 + 1

Es gilt also: 51⋅22 = 19⋅59 +1

Somit 51⋅22 = 1 mod 59

51 ist also das Inverse von 22 mod 59

Schlüsselpaar für RSA

Beispiel:

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