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: (16003 + 232) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(16003 + 232) mod 8 ≡ (16003 mod 8 + 232 mod 8) mod 8.

16003 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 16003 = 16000+3 = 8 ⋅ 2000 +3.

232 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 232 = 240-8 = 8 ⋅ 30 -8 = 8 ⋅ 30 - 8 + 0.

Somit gilt:

(16003 + 232) mod 8 ≡ (3 + 0) mod 8 ≡ 3 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (20 ⋅ 62) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(20 ⋅ 62) mod 7 ≡ (20 mod 7 ⋅ 62 mod 7) mod 7.

20 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 20 = 14 + 6 = 2 ⋅ 7 + 6 ist.

62 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 62 = 56 + 6 = 8 ⋅ 7 + 6 ist.

Somit gilt:

(20 ⋅ 62) mod 7 ≡ (6 ⋅ 6) mod 7 ≡ 36 mod 7 ≡ 1 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 588128 mod 617.

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. 588 -> x
2. mod(x²,617) -> 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: 5881=588

2: 5882=5881+1=5881⋅5881 ≡ 588⋅588=345744 ≡ 224 mod 617

4: 5884=5882+2=5882⋅5882 ≡ 224⋅224=50176 ≡ 199 mod 617

8: 5888=5884+4=5884⋅5884 ≡ 199⋅199=39601 ≡ 113 mod 617

16: 58816=5888+8=5888⋅5888 ≡ 113⋅113=12769 ≡ 429 mod 617

32: 58832=58816+16=58816⋅58816 ≡ 429⋅429=184041 ≡ 175 mod 617

64: 58864=58832+32=58832⋅58832 ≡ 175⋅175=30625 ≡ 392 mod 617

128: 588128=58864+64=58864⋅58864 ≡ 392⋅392=153664 ≡ 31 mod 617

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 317229 mod 937.

Lösung einblenden

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

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

229 = 128+64+32+4+1

1: 3171=317

2: 3172=3171+1=3171⋅3171 ≡ 317⋅317=100489 ≡ 230 mod 937

4: 3174=3172+2=3172⋅3172 ≡ 230⋅230=52900 ≡ 428 mod 937

8: 3178=3174+4=3174⋅3174 ≡ 428⋅428=183184 ≡ 469 mod 937

16: 31716=3178+8=3178⋅3178 ≡ 469⋅469=219961 ≡ 703 mod 937

32: 31732=31716+16=31716⋅31716 ≡ 703⋅703=494209 ≡ 410 mod 937

64: 31764=31732+32=31732⋅31732 ≡ 410⋅410=168100 ≡ 377 mod 937

128: 317128=31764+64=31764⋅31764 ≡ 377⋅377=142129 ≡ 642 mod 937

317229

= 317128+64+32+4+1

= 317128⋅31764⋅31732⋅3174⋅3171

642 ⋅ 377 ⋅ 410 ⋅ 428 ⋅ 317 mod 937
242034 ⋅ 410 ⋅ 428 ⋅ 317 mod 937 ≡ 288 ⋅ 410 ⋅ 428 ⋅ 317 mod 937
118080 ⋅ 428 ⋅ 317 mod 937 ≡ 18 ⋅ 428 ⋅ 317 mod 937
7704 ⋅ 317 mod 937 ≡ 208 ⋅ 317 mod 937
65936 mod 937 ≡ 346 mod 937

Es gilt also: 317229 ≡ 346 mod 937

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>59 = 1⋅40 + 19
=>40 = 2⋅19 + 2
=>19 = 9⋅2 + 1
=>2 = 2⋅1 + 0

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

Es gilt also: ggt(59,40)=1 = 19⋅59 -28⋅40

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

1 -19⋅59 = -28⋅40

-28⋅40 = -19⋅59 + 1 |+59⋅40

-28⋅40 + 59⋅40 = -19⋅59 + 59⋅40 + 1

(-28 + 59) ⋅ 40 = (-19 + 40) ⋅ 59 + 1

31⋅40 = 21⋅59 + 1

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

Somit 31⋅40 = 1 mod 59

31 ist also das Inverse von 40 mod 59

Schlüsselpaar für RSA

Beispiel:

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