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: (27999 + 1407) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(27999 + 1407) mod 7 ≡ (27999 mod 7 + 1407 mod 7) mod 7.

27999 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 27999 = 28000-1 = 7 ⋅ 4000 -1 = 7 ⋅ 4000 - 7 + 6.

1407 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 1407 = 1400+7 = 7 ⋅ 200 +7.

Somit gilt:

(27999 + 1407) mod 7 ≡ (6 + 0) mod 7 ≡ 6 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (71 ⋅ 67) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(71 ⋅ 67) mod 10 ≡ (71 mod 10 ⋅ 67 mod 10) mod 10.

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

67 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 67 = 60 + 7 = 6 ⋅ 10 + 7 ist.

Somit gilt:

(71 ⋅ 67) mod 10 ≡ (1 ⋅ 7) mod 10 ≡ 7 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 284128 mod 421.

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. 284 -> x
2. mod(x²,421) -> 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: 2841=284

2: 2842=2841+1=2841⋅2841 ≡ 284⋅284=80656 ≡ 245 mod 421

4: 2844=2842+2=2842⋅2842 ≡ 245⋅245=60025 ≡ 243 mod 421

8: 2848=2844+4=2844⋅2844 ≡ 243⋅243=59049 ≡ 109 mod 421

16: 28416=2848+8=2848⋅2848 ≡ 109⋅109=11881 ≡ 93 mod 421

32: 28432=28416+16=28416⋅28416 ≡ 93⋅93=8649 ≡ 229 mod 421

64: 28464=28432+32=28432⋅28432 ≡ 229⋅229=52441 ≡ 237 mod 421

128: 284128=28464+64=28464⋅28464 ≡ 237⋅237=56169 ≡ 176 mod 421

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 563198 mod 829.

Lösung einblenden

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

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

198 = 128+64+4+2

1: 5631=563

2: 5632=5631+1=5631⋅5631 ≡ 563⋅563=316969 ≡ 291 mod 829

4: 5634=5632+2=5632⋅5632 ≡ 291⋅291=84681 ≡ 123 mod 829

8: 5638=5634+4=5634⋅5634 ≡ 123⋅123=15129 ≡ 207 mod 829

16: 56316=5638+8=5638⋅5638 ≡ 207⋅207=42849 ≡ 570 mod 829

32: 56332=56316+16=56316⋅56316 ≡ 570⋅570=324900 ≡ 761 mod 829

64: 56364=56332+32=56332⋅56332 ≡ 761⋅761=579121 ≡ 479 mod 829

128: 563128=56364+64=56364⋅56364 ≡ 479⋅479=229441 ≡ 637 mod 829

563198

= 563128+64+4+2

= 563128⋅56364⋅5634⋅5632

637 ⋅ 479 ⋅ 123 ⋅ 291 mod 829
305123 ⋅ 123 ⋅ 291 mod 829 ≡ 51 ⋅ 123 ⋅ 291 mod 829
6273 ⋅ 291 mod 829 ≡ 470 ⋅ 291 mod 829
136770 mod 829 ≡ 814 mod 829

Es gilt also: 563198 ≡ 814 mod 829

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>89 = 2⋅42 + 5
=>42 = 8⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(89,42)=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-2⋅2
2= 42-8⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(42 -8⋅ 5)
= 1⋅5 -2⋅42 +16⋅ 5)
= -2⋅42 +17⋅ 5 (=1)
5= 89-2⋅42 eingesetzt in die Zeile drüber: 1 = -2⋅42 +17⋅(89 -2⋅ 42)
= -2⋅42 +17⋅89 -34⋅ 42)
= 17⋅89 -36⋅ 42 (=1)

Es gilt also: ggt(89,42)=1 = 17⋅89 -36⋅42

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

1 -17⋅89 = -36⋅42

-36⋅42 = -17⋅89 + 1 |+89⋅42

-36⋅42 + 89⋅42 = -17⋅89 + 89⋅42 + 1

(-36 + 89) ⋅ 42 = (-17 + 42) ⋅ 89 + 1

53⋅42 = 25⋅89 + 1

Es gilt also: 53⋅42 = 25⋅89 +1

Somit 53⋅42 = 1 mod 89

53 ist also das Inverse von 42 mod 89

Schlüsselpaar für RSA

Beispiel:

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