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: (23994 - 186) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(23994 - 186) mod 6 ≡ (23994 mod 6 - 186 mod 6) mod 6.

23994 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 23994 = 24000-6 = 6 ⋅ 4000 -6 = 6 ⋅ 4000 - 6 + 0.

186 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 186 = 180+6 = 6 ⋅ 30 +6.

Somit gilt:

(23994 - 186) mod 6 ≡ (0 - 0) mod 6 ≡ 0 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (81 ⋅ 48) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 48) mod 8 ≡ (81 mod 8 ⋅ 48 mod 8) mod 8.

81 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 10 ⋅ 8 + 1 ist.

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

Somit gilt:

(81 ⋅ 48) mod 8 ≡ (1 ⋅ 0) mod 8 ≡ 0 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 2728 mod 311.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 272 -> x
2. mod(x²,311) -> 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: 2721=272

2: 2722=2721+1=2721⋅2721 ≡ 272⋅272=73984 ≡ 277 mod 311

4: 2724=2722+2=2722⋅2722 ≡ 277⋅277=76729 ≡ 223 mod 311

8: 2728=2724+4=2724⋅2724 ≡ 223⋅223=49729 ≡ 280 mod 311

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 289241 mod 523.

Lösung einblenden

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

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

241 = 128+64+32+16+1

1: 2891=289

2: 2892=2891+1=2891⋅2891 ≡ 289⋅289=83521 ≡ 364 mod 523

4: 2894=2892+2=2892⋅2892 ≡ 364⋅364=132496 ≡ 177 mod 523

8: 2898=2894+4=2894⋅2894 ≡ 177⋅177=31329 ≡ 472 mod 523

16: 28916=2898+8=2898⋅2898 ≡ 472⋅472=222784 ≡ 509 mod 523

32: 28932=28916+16=28916⋅28916 ≡ 509⋅509=259081 ≡ 196 mod 523

64: 28964=28932+32=28932⋅28932 ≡ 196⋅196=38416 ≡ 237 mod 523

128: 289128=28964+64=28964⋅28964 ≡ 237⋅237=56169 ≡ 208 mod 523

289241

= 289128+64+32+16+1

= 289128⋅28964⋅28932⋅28916⋅2891

208 ⋅ 237 ⋅ 196 ⋅ 509 ⋅ 289 mod 523
49296 ⋅ 196 ⋅ 509 ⋅ 289 mod 523 ≡ 134 ⋅ 196 ⋅ 509 ⋅ 289 mod 523
26264 ⋅ 509 ⋅ 289 mod 523 ≡ 114 ⋅ 509 ⋅ 289 mod 523
58026 ⋅ 289 mod 523 ≡ 496 ⋅ 289 mod 523
143344 mod 523 ≡ 42 mod 523

Es gilt also: 289241 ≡ 42 mod 523

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>59 = 1⋅54 + 5
=>54 = 10⋅5 + 4
=>5 = 1⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(59,54)=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= 5-1⋅4
4= 54-10⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -1⋅(54 -10⋅ 5)
= 1⋅5 -1⋅54 +10⋅ 5)
= -1⋅54 +11⋅ 5 (=1)
5= 59-1⋅54 eingesetzt in die Zeile drüber: 1 = -1⋅54 +11⋅(59 -1⋅ 54)
= -1⋅54 +11⋅59 -11⋅ 54)
= 11⋅59 -12⋅ 54 (=1)

Es gilt also: ggt(59,54)=1 = 11⋅59 -12⋅54

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

1 -11⋅59 = -12⋅54

-12⋅54 = -11⋅59 + 1 |+59⋅54

-12⋅54 + 59⋅54 = -11⋅59 + 59⋅54 + 1

(-12 + 59) ⋅ 54 = (-11 + 54) ⋅ 59 + 1

47⋅54 = 43⋅59 + 1

Es gilt also: 47⋅54 = 43⋅59 +1

Somit 47⋅54 = 1 mod 59

47 ist also das Inverse von 54 mod 59

Schlüsselpaar für RSA

Beispiel:

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