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: (1498 - 2000) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1498 - 2000) mod 5 ≡ (1498 mod 5 - 2000 mod 5) mod 5.

1498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 1498 = 1400+98 = 5 ⋅ 280 +98.

2000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2000 = 2000+0 = 5 ⋅ 400 +0.

Somit gilt:

(1498 - 2000) mod 5 ≡ (3 - 0) mod 5 ≡ 3 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (36 ⋅ 32) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(36 ⋅ 32) mod 9 ≡ (36 mod 9 ⋅ 32 mod 9) mod 9.

36 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 36 = 36 + 0 = 4 ⋅ 9 + 0 ist.

32 mod 9 ≡ 5 mod 9 kann man relativ leicht bestimmen, weil ja 32 = 27 + 5 = 3 ⋅ 9 + 5 ist.

Somit gilt:

(36 ⋅ 32) mod 9 ≡ (0 ⋅ 5) mod 9 ≡ 0 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 192128 mod 557.

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. 192 -> x
2. mod(x²,557) -> 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: 1921=192

2: 1922=1921+1=1921⋅1921 ≡ 192⋅192=36864 ≡ 102 mod 557

4: 1924=1922+2=1922⋅1922 ≡ 102⋅102=10404 ≡ 378 mod 557

8: 1928=1924+4=1924⋅1924 ≡ 378⋅378=142884 ≡ 292 mod 557

16: 19216=1928+8=1928⋅1928 ≡ 292⋅292=85264 ≡ 43 mod 557

32: 19232=19216+16=19216⋅19216 ≡ 43⋅43=1849 ≡ 178 mod 557

64: 19264=19232+32=19232⋅19232 ≡ 178⋅178=31684 ≡ 492 mod 557

128: 192128=19264+64=19264⋅19264 ≡ 492⋅492=242064 ≡ 326 mod 557

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 11778 mod 229.

Lösung einblenden

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

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

78 = 64+8+4+2

1: 1171=117

2: 1172=1171+1=1171⋅1171 ≡ 117⋅117=13689 ≡ 178 mod 229

4: 1174=1172+2=1172⋅1172 ≡ 178⋅178=31684 ≡ 82 mod 229

8: 1178=1174+4=1174⋅1174 ≡ 82⋅82=6724 ≡ 83 mod 229

16: 11716=1178+8=1178⋅1178 ≡ 83⋅83=6889 ≡ 19 mod 229

32: 11732=11716+16=11716⋅11716 ≡ 19⋅19=361 ≡ 132 mod 229

64: 11764=11732+32=11732⋅11732 ≡ 132⋅132=17424 ≡ 20 mod 229

11778

= 11764+8+4+2

= 11764⋅1178⋅1174⋅1172

20 ⋅ 83 ⋅ 82 ⋅ 178 mod 229
1660 ⋅ 82 ⋅ 178 mod 229 ≡ 57 ⋅ 82 ⋅ 178 mod 229
4674 ⋅ 178 mod 229 ≡ 94 ⋅ 178 mod 229
16732 mod 229 ≡ 15 mod 229

Es gilt also: 11778 ≡ 15 mod 229

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 25

=>67 = 2⋅25 + 17
=>25 = 1⋅17 + 8
=>17 = 2⋅8 + 1
=>8 = 8⋅1 + 0

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

Es gilt also: ggt(67,25)=1 = 3⋅67 -8⋅25

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

1 -3⋅67 = -8⋅25

-8⋅25 = -3⋅67 + 1 |+67⋅25

-8⋅25 + 67⋅25 = -3⋅67 + 67⋅25 + 1

(-8 + 67) ⋅ 25 = (-3 + 25) ⋅ 67 + 1

59⋅25 = 22⋅67 + 1

Es gilt also: 59⋅25 = 22⋅67 +1

Somit 59⋅25 = 1 mod 67

59 ist also das Inverse von 25 mod 67

Schlüsselpaar für RSA

Beispiel:

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