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: (120 + 151) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(120 + 151) mod 3 ≡ (120 mod 3 + 151 mod 3) mod 3.

120 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 120 = 120+0 = 3 ⋅ 40 +0.

151 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 151 = 150+1 = 3 ⋅ 50 +1.

Somit gilt:

(120 + 151) mod 3 ≡ (0 + 1) mod 3 ≡ 1 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (38 ⋅ 76) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(38 ⋅ 76) mod 3 ≡ (38 mod 3 ⋅ 76 mod 3) mod 3.

38 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 38 = 36 + 2 = 12 ⋅ 3 + 2 ist.

76 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 76 = 75 + 1 = 25 ⋅ 3 + 1 ist.

Somit gilt:

(38 ⋅ 76) mod 3 ≡ (2 ⋅ 1) mod 3 ≡ 2 mod 3.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 317128 mod 827.

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. 317 -> x
2. mod(x²,827) -> 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: 3171=317

2: 3172=3171+1=3171⋅3171 ≡ 317⋅317=100489 ≡ 422 mod 827

4: 3174=3172+2=3172⋅3172 ≡ 422⋅422=178084 ≡ 279 mod 827

8: 3178=3174+4=3174⋅3174 ≡ 279⋅279=77841 ≡ 103 mod 827

16: 31716=3178+8=3178⋅3178 ≡ 103⋅103=10609 ≡ 685 mod 827

32: 31732=31716+16=31716⋅31716 ≡ 685⋅685=469225 ≡ 316 mod 827

64: 31764=31732+32=31732⋅31732 ≡ 316⋅316=99856 ≡ 616 mod 827

128: 317128=31764+64=31764⋅31764 ≡ 616⋅616=379456 ≡ 690 mod 827

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 211231 mod 223.

Lösung einblenden

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

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

231 = 128+64+32+4+2+1

1: 2111=211

2: 2112=2111+1=2111⋅2111 ≡ 211⋅211=44521 ≡ 144 mod 223

4: 2114=2112+2=2112⋅2112 ≡ 144⋅144=20736 ≡ 220 mod 223

8: 2118=2114+4=2114⋅2114 ≡ 220⋅220=48400 ≡ 9 mod 223

16: 21116=2118+8=2118⋅2118 ≡ 9⋅9=81 ≡ 81 mod 223

32: 21132=21116+16=21116⋅21116 ≡ 81⋅81=6561 ≡ 94 mod 223

64: 21164=21132+32=21132⋅21132 ≡ 94⋅94=8836 ≡ 139 mod 223

128: 211128=21164+64=21164⋅21164 ≡ 139⋅139=19321 ≡ 143 mod 223

211231

= 211128+64+32+4+2+1

= 211128⋅21164⋅21132⋅2114⋅2112⋅2111

143 ⋅ 139 ⋅ 94 ⋅ 220 ⋅ 144 ⋅ 211 mod 223
19877 ⋅ 94 ⋅ 220 ⋅ 144 ⋅ 211 mod 223 ≡ 30 ⋅ 94 ⋅ 220 ⋅ 144 ⋅ 211 mod 223
2820 ⋅ 220 ⋅ 144 ⋅ 211 mod 223 ≡ 144 ⋅ 220 ⋅ 144 ⋅ 211 mod 223
31680 ⋅ 144 ⋅ 211 mod 223 ≡ 14 ⋅ 144 ⋅ 211 mod 223
2016 ⋅ 211 mod 223 ≡ 9 ⋅ 211 mod 223
1899 mod 223 ≡ 115 mod 223

Es gilt also: 211231 ≡ 115 mod 223

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>73 = 2⋅29 + 15
=>29 = 1⋅15 + 14
=>15 = 1⋅14 + 1
=>14 = 14⋅1 + 0

also gilt: ggt(73,29)=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-1⋅14
14= 29-1⋅15 eingesetzt in die Zeile drüber: 1 = 1⋅15 -1⋅(29 -1⋅ 15)
= 1⋅15 -1⋅29 +1⋅ 15)
= -1⋅29 +2⋅ 15 (=1)
15= 73-2⋅29 eingesetzt in die Zeile drüber: 1 = -1⋅29 +2⋅(73 -2⋅ 29)
= -1⋅29 +2⋅73 -4⋅ 29)
= 2⋅73 -5⋅ 29 (=1)

Es gilt also: ggt(73,29)=1 = 2⋅73 -5⋅29

oder wenn man 2⋅73 auf die linke Seite bringt:

1 -2⋅73 = -5⋅29

-5⋅29 = -2⋅73 + 1 |+73⋅29

-5⋅29 + 73⋅29 = -2⋅73 + 73⋅29 + 1

(-5 + 73) ⋅ 29 = (-2 + 29) ⋅ 73 + 1

68⋅29 = 27⋅73 + 1

Es gilt also: 68⋅29 = 27⋅73 +1

Somit 68⋅29 = 1 mod 73

68 ist also das Inverse von 29 mod 73

Schlüsselpaar für RSA

Beispiel:

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