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: (3592 - 9003) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3592 - 9003) mod 9 ≡ (3592 mod 9 - 9003 mod 9) mod 9.

3592 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 3592 = 3600-8 = 9 ⋅ 400 -8 = 9 ⋅ 400 - 9 + 1.

9003 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 9003 = 9000+3 = 9 ⋅ 1000 +3.

Somit gilt:

(3592 - 9003) mod 9 ≡ (1 - 3) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (79 ⋅ 62) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(79 ⋅ 62) mod 9 ≡ (79 mod 9 ⋅ 62 mod 9) mod 9.

79 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 79 = 72 + 7 = 8 ⋅ 9 + 7 ist.

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

Somit gilt:

(79 ⋅ 62) mod 9 ≡ (7 ⋅ 8) mod 9 ≡ 56 mod 9 ≡ 2 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 73732 mod 739.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 737 -> x
2. mod(x²,739) -> 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: 7371=737

2: 7372=7371+1=7371⋅7371 ≡ 737⋅737=543169 ≡ 4 mod 739

4: 7374=7372+2=7372⋅7372 ≡ 4⋅4=16 ≡ 16 mod 739

8: 7378=7374+4=7374⋅7374 ≡ 16⋅16=256 ≡ 256 mod 739

16: 73716=7378+8=7378⋅7378 ≡ 256⋅256=65536 ≡ 504 mod 739

32: 73732=73716+16=73716⋅73716 ≡ 504⋅504=254016 ≡ 539 mod 739

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 321246 mod 521.

Lösung einblenden

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

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

246 = 128+64+32+16+4+2

1: 3211=321

2: 3212=3211+1=3211⋅3211 ≡ 321⋅321=103041 ≡ 404 mod 521

4: 3214=3212+2=3212⋅3212 ≡ 404⋅404=163216 ≡ 143 mod 521

8: 3218=3214+4=3214⋅3214 ≡ 143⋅143=20449 ≡ 130 mod 521

16: 32116=3218+8=3218⋅3218 ≡ 130⋅130=16900 ≡ 228 mod 521

32: 32132=32116+16=32116⋅32116 ≡ 228⋅228=51984 ≡ 405 mod 521

64: 32164=32132+32=32132⋅32132 ≡ 405⋅405=164025 ≡ 431 mod 521

128: 321128=32164+64=32164⋅32164 ≡ 431⋅431=185761 ≡ 285 mod 521

321246

= 321128+64+32+16+4+2

= 321128⋅32164⋅32132⋅32116⋅3214⋅3212

285 ⋅ 431 ⋅ 405 ⋅ 228 ⋅ 143 ⋅ 404 mod 521
122835 ⋅ 405 ⋅ 228 ⋅ 143 ⋅ 404 mod 521 ≡ 400 ⋅ 405 ⋅ 228 ⋅ 143 ⋅ 404 mod 521
162000 ⋅ 228 ⋅ 143 ⋅ 404 mod 521 ≡ 490 ⋅ 228 ⋅ 143 ⋅ 404 mod 521
111720 ⋅ 143 ⋅ 404 mod 521 ≡ 226 ⋅ 143 ⋅ 404 mod 521
32318 ⋅ 404 mod 521 ≡ 16 ⋅ 404 mod 521
6464 mod 521 ≡ 212 mod 521

Es gilt also: 321246 ≡ 212 mod 521

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>61 = 1⋅42 + 19
=>42 = 2⋅19 + 4
=>19 = 4⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(61,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= 4-1⋅3
3= 19-4⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(19 -4⋅ 4)
= 1⋅4 -1⋅19 +4⋅ 4)
= -1⋅19 +5⋅ 4 (=1)
4= 42-2⋅19 eingesetzt in die Zeile drüber: 1 = -1⋅19 +5⋅(42 -2⋅ 19)
= -1⋅19 +5⋅42 -10⋅ 19)
= 5⋅42 -11⋅ 19 (=1)
19= 61-1⋅42 eingesetzt in die Zeile drüber: 1 = 5⋅42 -11⋅(61 -1⋅ 42)
= 5⋅42 -11⋅61 +11⋅ 42)
= -11⋅61 +16⋅ 42 (=1)

Es gilt also: ggt(61,42)=1 = -11⋅61 +16⋅42

oder wenn man -11⋅61 auf die linke Seite bringt:

1 +11⋅61 = +16⋅42

Es gilt also: 16⋅42 = 11⋅61 +1

Somit 16⋅42 = 1 mod 61

16 ist also das Inverse von 42 mod 61

Schlüsselpaar für RSA

Beispiel:

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