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: (1204 - 19996) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1204 - 19996) mod 4 ≡ (1204 mod 4 - 19996 mod 4) mod 4.

1204 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1204 = 1200+4 = 4 ⋅ 300 +4.

19996 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 19996 = 19000+996 = 4 ⋅ 4750 +996.

Somit gilt:

(1204 - 19996) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (50 ⋅ 100) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(50 ⋅ 100) mod 6 ≡ (50 mod 6 ⋅ 100 mod 6) mod 6.

50 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 50 = 48 + 2 = 8 ⋅ 6 + 2 ist.

100 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 100 = 96 + 4 = 16 ⋅ 6 + 4 ist.

Somit gilt:

(50 ⋅ 100) mod 6 ≡ (2 ⋅ 4) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 49232 mod 887.

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. 492 -> x
2. mod(x²,887) -> 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: 4921=492

2: 4922=4921+1=4921⋅4921 ≡ 492⋅492=242064 ≡ 800 mod 887

4: 4924=4922+2=4922⋅4922 ≡ 800⋅800=640000 ≡ 473 mod 887

8: 4928=4924+4=4924⋅4924 ≡ 473⋅473=223729 ≡ 205 mod 887

16: 49216=4928+8=4928⋅4928 ≡ 205⋅205=42025 ≡ 336 mod 887

32: 49232=49216+16=49216⋅49216 ≡ 336⋅336=112896 ≡ 247 mod 887

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 285146 mod 461.

Lösung einblenden

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

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

146 = 128+16+2

1: 2851=285

2: 2852=2851+1=2851⋅2851 ≡ 285⋅285=81225 ≡ 89 mod 461

4: 2854=2852+2=2852⋅2852 ≡ 89⋅89=7921 ≡ 84 mod 461

8: 2858=2854+4=2854⋅2854 ≡ 84⋅84=7056 ≡ 141 mod 461

16: 28516=2858+8=2858⋅2858 ≡ 141⋅141=19881 ≡ 58 mod 461

32: 28532=28516+16=28516⋅28516 ≡ 58⋅58=3364 ≡ 137 mod 461

64: 28564=28532+32=28532⋅28532 ≡ 137⋅137=18769 ≡ 329 mod 461

128: 285128=28564+64=28564⋅28564 ≡ 329⋅329=108241 ≡ 367 mod 461

285146

= 285128+16+2

= 285128⋅28516⋅2852

367 ⋅ 58 ⋅ 89 mod 461
21286 ⋅ 89 mod 461 ≡ 80 ⋅ 89 mod 461
7120 mod 461 ≡ 205 mod 461

Es gilt also: 285146 ≡ 205 mod 461

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>73 = 2⋅26 + 21
=>26 = 1⋅21 + 5
=>21 = 4⋅5 + 1
=>5 = 5⋅1 + 0

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

Es gilt also: ggt(73,26)=1 = 5⋅73 -14⋅26

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

1 -5⋅73 = -14⋅26

-14⋅26 = -5⋅73 + 1 |+73⋅26

-14⋅26 + 73⋅26 = -5⋅73 + 73⋅26 + 1

(-14 + 73) ⋅ 26 = (-5 + 26) ⋅ 73 + 1

59⋅26 = 21⋅73 + 1

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

Somit 59⋅26 = 1 mod 73

59 ist also das Inverse von 26 mod 73

Schlüsselpaar für RSA

Beispiel:

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