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: (19997 - 2497) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(19997 - 2497) mod 5 ≡ (19997 mod 5 - 2497 mod 5) mod 5.

19997 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 19997 = 19000+997 = 5 ⋅ 3800 +997.

2497 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 2497 = 2400+97 = 5 ⋅ 480 +97.

Somit gilt:

(19997 - 2497) mod 5 ≡ (2 - 2) mod 5 ≡ 0 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (63 ⋅ 95) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 95) mod 10 ≡ (63 mod 10 ⋅ 95 mod 10) mod 10.

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

95 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 95 = 90 + 5 = 9 ⋅ 10 + 5 ist.

Somit gilt:

(63 ⋅ 95) mod 10 ≡ (3 ⋅ 5) mod 10 ≡ 15 mod 10 ≡ 5 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 58164 mod 631.

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. 581 -> x
2. mod(x²,631) -> 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: 5811=581

2: 5812=5811+1=5811⋅5811 ≡ 581⋅581=337561 ≡ 607 mod 631

4: 5814=5812+2=5812⋅5812 ≡ 607⋅607=368449 ≡ 576 mod 631

8: 5818=5814+4=5814⋅5814 ≡ 576⋅576=331776 ≡ 501 mod 631

16: 58116=5818+8=5818⋅5818 ≡ 501⋅501=251001 ≡ 494 mod 631

32: 58132=58116+16=58116⋅58116 ≡ 494⋅494=244036 ≡ 470 mod 631

64: 58164=58132+32=58132⋅58132 ≡ 470⋅470=220900 ≡ 50 mod 631

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 263236 mod 463.

Lösung einblenden

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

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

236 = 128+64+32+8+4

1: 2631=263

2: 2632=2631+1=2631⋅2631 ≡ 263⋅263=69169 ≡ 182 mod 463

4: 2634=2632+2=2632⋅2632 ≡ 182⋅182=33124 ≡ 251 mod 463

8: 2638=2634+4=2634⋅2634 ≡ 251⋅251=63001 ≡ 33 mod 463

16: 26316=2638+8=2638⋅2638 ≡ 33⋅33=1089 ≡ 163 mod 463

32: 26332=26316+16=26316⋅26316 ≡ 163⋅163=26569 ≡ 178 mod 463

64: 26364=26332+32=26332⋅26332 ≡ 178⋅178=31684 ≡ 200 mod 463

128: 263128=26364+64=26364⋅26364 ≡ 200⋅200=40000 ≡ 182 mod 463

263236

= 263128+64+32+8+4

= 263128⋅26364⋅26332⋅2638⋅2634

182 ⋅ 200 ⋅ 178 ⋅ 33 ⋅ 251 mod 463
36400 ⋅ 178 ⋅ 33 ⋅ 251 mod 463 ≡ 286 ⋅ 178 ⋅ 33 ⋅ 251 mod 463
50908 ⋅ 33 ⋅ 251 mod 463 ≡ 441 ⋅ 33 ⋅ 251 mod 463
14553 ⋅ 251 mod 463 ≡ 200 ⋅ 251 mod 463
50200 mod 463 ≡ 196 mod 463

Es gilt also: 263236 ≡ 196 mod 463

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>59 = 2⋅22 + 15
=>22 = 1⋅15 + 7
=>15 = 2⋅7 + 1
=>7 = 7⋅1 + 0

also gilt: ggt(59,22)=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= 15-2⋅7
7= 22-1⋅15 eingesetzt in die Zeile drüber: 1 = 1⋅15 -2⋅(22 -1⋅ 15)
= 1⋅15 -2⋅22 +2⋅ 15)
= -2⋅22 +3⋅ 15 (=1)
15= 59-2⋅22 eingesetzt in die Zeile drüber: 1 = -2⋅22 +3⋅(59 -2⋅ 22)
= -2⋅22 +3⋅59 -6⋅ 22)
= 3⋅59 -8⋅ 22 (=1)

Es gilt also: ggt(59,22)=1 = 3⋅59 -8⋅22

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

1 -3⋅59 = -8⋅22

-8⋅22 = -3⋅59 + 1 |+59⋅22

-8⋅22 + 59⋅22 = -3⋅59 + 59⋅22 + 1

(-8 + 59) ⋅ 22 = (-3 + 22) ⋅ 59 + 1

51⋅22 = 19⋅59 + 1

Es gilt also: 51⋅22 = 19⋅59 +1

Somit 51⋅22 = 1 mod 59

51 ist also das Inverse von 22 mod 59

Schlüsselpaar für RSA

Beispiel:

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