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: (68 + 279) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(68 + 279) mod 7 ≡ (68 mod 7 + 279 mod 7) mod 7.

68 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 68 = 70-2 = 7 ⋅ 10 -2 = 7 ⋅ 10 - 7 + 5.

279 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 279 = 280-1 = 7 ⋅ 40 -1 = 7 ⋅ 40 - 7 + 6.

Somit gilt:

(68 + 279) mod 7 ≡ (5 + 6) mod 7 ≡ 11 mod 7 ≡ 4 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (80 ⋅ 56) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(80 ⋅ 56) mod 5 ≡ (80 mod 5 ⋅ 56 mod 5) mod 5.

80 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 80 = 80 + 0 = 16 ⋅ 5 + 0 ist.

56 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 56 = 55 + 1 = 11 ⋅ 5 + 1 ist.

Somit gilt:

(80 ⋅ 56) mod 5 ≡ (0 ⋅ 1) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 58964 mod 719.

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. 589 -> x
2. mod(x²,719) -> 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: 5891=589

2: 5892=5891+1=5891⋅5891 ≡ 589⋅589=346921 ≡ 363 mod 719

4: 5894=5892+2=5892⋅5892 ≡ 363⋅363=131769 ≡ 192 mod 719

8: 5898=5894+4=5894⋅5894 ≡ 192⋅192=36864 ≡ 195 mod 719

16: 58916=5898+8=5898⋅5898 ≡ 195⋅195=38025 ≡ 637 mod 719

32: 58932=58916+16=58916⋅58916 ≡ 637⋅637=405769 ≡ 253 mod 719

64: 58964=58932+32=58932⋅58932 ≡ 253⋅253=64009 ≡ 18 mod 719

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 406207 mod 433.

Lösung einblenden

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

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

207 = 128+64+8+4+2+1

1: 4061=406

2: 4062=4061+1=4061⋅4061 ≡ 406⋅406=164836 ≡ 296 mod 433

4: 4064=4062+2=4062⋅4062 ≡ 296⋅296=87616 ≡ 150 mod 433

8: 4068=4064+4=4064⋅4064 ≡ 150⋅150=22500 ≡ 417 mod 433

16: 40616=4068+8=4068⋅4068 ≡ 417⋅417=173889 ≡ 256 mod 433

32: 40632=40616+16=40616⋅40616 ≡ 256⋅256=65536 ≡ 153 mod 433

64: 40664=40632+32=40632⋅40632 ≡ 153⋅153=23409 ≡ 27 mod 433

128: 406128=40664+64=40664⋅40664 ≡ 27⋅27=729 ≡ 296 mod 433

406207

= 406128+64+8+4+2+1

= 406128⋅40664⋅4068⋅4064⋅4062⋅4061

296 ⋅ 27 ⋅ 417 ⋅ 150 ⋅ 296 ⋅ 406 mod 433
7992 ⋅ 417 ⋅ 150 ⋅ 296 ⋅ 406 mod 433 ≡ 198 ⋅ 417 ⋅ 150 ⋅ 296 ⋅ 406 mod 433
82566 ⋅ 150 ⋅ 296 ⋅ 406 mod 433 ≡ 296 ⋅ 150 ⋅ 296 ⋅ 406 mod 433
44400 ⋅ 296 ⋅ 406 mod 433 ≡ 234 ⋅ 296 ⋅ 406 mod 433
69264 ⋅ 406 mod 433 ≡ 417 ⋅ 406 mod 433
169302 mod 433 ≡ 432 mod 433

Es gilt also: 406207 ≡ 432 mod 433

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 79 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 79

=>89 = 1⋅79 + 10
=>79 = 7⋅10 + 9
=>10 = 1⋅9 + 1
=>9 = 9⋅1 + 0

also gilt: ggt(89,79)=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= 10-1⋅9
9= 79-7⋅10 eingesetzt in die Zeile drüber: 1 = 1⋅10 -1⋅(79 -7⋅ 10)
= 1⋅10 -1⋅79 +7⋅ 10)
= -1⋅79 +8⋅ 10 (=1)
10= 89-1⋅79 eingesetzt in die Zeile drüber: 1 = -1⋅79 +8⋅(89 -1⋅ 79)
= -1⋅79 +8⋅89 -8⋅ 79)
= 8⋅89 -9⋅ 79 (=1)

Es gilt also: ggt(89,79)=1 = 8⋅89 -9⋅79

oder wenn man 8⋅89 auf die linke Seite bringt:

1 -8⋅89 = -9⋅79

-9⋅79 = -8⋅89 + 1 |+89⋅79

-9⋅79 + 89⋅79 = -8⋅89 + 89⋅79 + 1

(-9 + 89) ⋅ 79 = (-8 + 79) ⋅ 89 + 1

80⋅79 = 71⋅89 + 1

Es gilt also: 80⋅79 = 71⋅89 +1

Somit 80⋅79 = 1 mod 89

80 ist also das Inverse von 79 mod 89

Schlüsselpaar für RSA

Beispiel:

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