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: (25003 + 498) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(25003 + 498) mod 5 ≡ (25003 mod 5 + 498 mod 5) mod 5.

25003 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 25003 = 25000+3 = 5 ⋅ 5000 +3.

498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 498 = 400+98 = 5 ⋅ 80 +98.

Somit gilt:

(25003 + 498) mod 5 ≡ (3 + 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (74 ⋅ 38) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 38) mod 10 ≡ (74 mod 10 ⋅ 38 mod 10) mod 10.

74 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 74 = 70 + 4 = 7 ⋅ 10 + 4 ist.

38 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 38 = 30 + 8 = 3 ⋅ 10 + 8 ist.

Somit gilt:

(74 ⋅ 38) mod 10 ≡ (4 ⋅ 8) mod 10 ≡ 32 mod 10 ≡ 2 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 28064 mod 283.

Lösung einblenden

Die 64 im Exponent ist ja ein reine 2er-Potenz (26).

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. 280 -> x
2. mod(x²,283) -> 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: 2801=280

2: 2802=2801+1=2801⋅2801 ≡ 280⋅280=78400 ≡ 9 mod 283

4: 2804=2802+2=2802⋅2802 ≡ 9⋅9=81 ≡ 81 mod 283

8: 2808=2804+4=2804⋅2804 ≡ 81⋅81=6561 ≡ 52 mod 283

16: 28016=2808+8=2808⋅2808 ≡ 52⋅52=2704 ≡ 157 mod 283

32: 28032=28016+16=28016⋅28016 ≡ 157⋅157=24649 ≡ 28 mod 283

64: 28064=28032+32=28032⋅28032 ≡ 28⋅28=784 ≡ 218 mod 283

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 182179 mod 503.

Lösung einblenden

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

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

179 = 128+32+16+2+1

1: 1821=182

2: 1822=1821+1=1821⋅1821 ≡ 182⋅182=33124 ≡ 429 mod 503

4: 1824=1822+2=1822⋅1822 ≡ 429⋅429=184041 ≡ 446 mod 503

8: 1828=1824+4=1824⋅1824 ≡ 446⋅446=198916 ≡ 231 mod 503

16: 18216=1828+8=1828⋅1828 ≡ 231⋅231=53361 ≡ 43 mod 503

32: 18232=18216+16=18216⋅18216 ≡ 43⋅43=1849 ≡ 340 mod 503

64: 18264=18232+32=18232⋅18232 ≡ 340⋅340=115600 ≡ 413 mod 503

128: 182128=18264+64=18264⋅18264 ≡ 413⋅413=170569 ≡ 52 mod 503

182179

= 182128+32+16+2+1

= 182128⋅18232⋅18216⋅1822⋅1821

52 ⋅ 340 ⋅ 43 ⋅ 429 ⋅ 182 mod 503
17680 ⋅ 43 ⋅ 429 ⋅ 182 mod 503 ≡ 75 ⋅ 43 ⋅ 429 ⋅ 182 mod 503
3225 ⋅ 429 ⋅ 182 mod 503 ≡ 207 ⋅ 429 ⋅ 182 mod 503
88803 ⋅ 182 mod 503 ≡ 275 ⋅ 182 mod 503
50050 mod 503 ≡ 253 mod 503

Es gilt also: 182179 ≡ 253 mod 503

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>59 = 1⋅31 + 28
=>31 = 1⋅28 + 3
=>28 = 9⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(59,31)=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= 28-9⋅3
3= 31-1⋅28 eingesetzt in die Zeile drüber: 1 = 1⋅28 -9⋅(31 -1⋅ 28)
= 1⋅28 -9⋅31 +9⋅ 28)
= -9⋅31 +10⋅ 28 (=1)
28= 59-1⋅31 eingesetzt in die Zeile drüber: 1 = -9⋅31 +10⋅(59 -1⋅ 31)
= -9⋅31 +10⋅59 -10⋅ 31)
= 10⋅59 -19⋅ 31 (=1)

Es gilt also: ggt(59,31)=1 = 10⋅59 -19⋅31

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

1 -10⋅59 = -19⋅31

-19⋅31 = -10⋅59 + 1 |+59⋅31

-19⋅31 + 59⋅31 = -10⋅59 + 59⋅31 + 1

(-19 + 59) ⋅ 31 = (-10 + 31) ⋅ 59 + 1

40⋅31 = 21⋅59 + 1

Es gilt also: 40⋅31 = 21⋅59 +1

Somit 40⋅31 = 1 mod 59

40 ist also das Inverse von 31 mod 59

Schlüsselpaar für RSA

Beispiel:

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