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: (48 + 25000) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(48 + 25000) mod 5 ≡ (48 mod 5 + 25000 mod 5) mod 5.

48 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 48 = 40+8 = 5 ⋅ 8 +8.

25000 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 25000 = 25000+0 = 5 ⋅ 5000 +0.

Somit gilt:

(48 + 25000) mod 5 ≡ (3 + 0) mod 5 ≡ 3 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (39 ⋅ 53) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(39 ⋅ 53) mod 7 ≡ (39 mod 7 ⋅ 53 mod 7) mod 7.

39 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 39 = 35 + 4 = 5 ⋅ 7 + 4 ist.

53 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 53 = 49 + 4 = 7 ⋅ 7 + 4 ist.

Somit gilt:

(39 ⋅ 53) mod 7 ≡ (4 ⋅ 4) mod 7 ≡ 16 mod 7 ≡ 2 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 610128 mod 773.

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. 610 -> x
2. mod(x²,773) -> 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: 6101=610

2: 6102=6101+1=6101⋅6101 ≡ 610⋅610=372100 ≡ 287 mod 773

4: 6104=6102+2=6102⋅6102 ≡ 287⋅287=82369 ≡ 431 mod 773

8: 6108=6104+4=6104⋅6104 ≡ 431⋅431=185761 ≡ 241 mod 773

16: 61016=6108+8=6108⋅6108 ≡ 241⋅241=58081 ≡ 106 mod 773

32: 61032=61016+16=61016⋅61016 ≡ 106⋅106=11236 ≡ 414 mod 773

64: 61064=61032+32=61032⋅61032 ≡ 414⋅414=171396 ≡ 563 mod 773

128: 610128=61064+64=61064⋅61064 ≡ 563⋅563=316969 ≡ 39 mod 773

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 668189 mod 797.

Lösung einblenden

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

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

189 = 128+32+16+8+4+1

1: 6681=668

2: 6682=6681+1=6681⋅6681 ≡ 668⋅668=446224 ≡ 701 mod 797

4: 6684=6682+2=6682⋅6682 ≡ 701⋅701=491401 ≡ 449 mod 797

8: 6688=6684+4=6684⋅6684 ≡ 449⋅449=201601 ≡ 757 mod 797

16: 66816=6688+8=6688⋅6688 ≡ 757⋅757=573049 ≡ 6 mod 797

32: 66832=66816+16=66816⋅66816 ≡ 6⋅6=36 ≡ 36 mod 797

64: 66864=66832+32=66832⋅66832 ≡ 36⋅36=1296 ≡ 499 mod 797

128: 668128=66864+64=66864⋅66864 ≡ 499⋅499=249001 ≡ 337 mod 797

668189

= 668128+32+16+8+4+1

= 668128⋅66832⋅66816⋅6688⋅6684⋅6681

337 ⋅ 36 ⋅ 6 ⋅ 757 ⋅ 449 ⋅ 668 mod 797
12132 ⋅ 6 ⋅ 757 ⋅ 449 ⋅ 668 mod 797 ≡ 177 ⋅ 6 ⋅ 757 ⋅ 449 ⋅ 668 mod 797
1062 ⋅ 757 ⋅ 449 ⋅ 668 mod 797 ≡ 265 ⋅ 757 ⋅ 449 ⋅ 668 mod 797
200605 ⋅ 449 ⋅ 668 mod 797 ≡ 558 ⋅ 449 ⋅ 668 mod 797
250542 ⋅ 668 mod 797 ≡ 284 ⋅ 668 mod 797
189712 mod 797 ≡ 26 mod 797

Es gilt also: 668189 ≡ 26 mod 797

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>79 = 2⋅32 + 15
=>32 = 2⋅15 + 2
=>15 = 7⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(79,32)=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-7⋅2
2= 32-2⋅15 eingesetzt in die Zeile drüber: 1 = 1⋅15 -7⋅(32 -2⋅ 15)
= 1⋅15 -7⋅32 +14⋅ 15)
= -7⋅32 +15⋅ 15 (=1)
15= 79-2⋅32 eingesetzt in die Zeile drüber: 1 = -7⋅32 +15⋅(79 -2⋅ 32)
= -7⋅32 +15⋅79 -30⋅ 32)
= 15⋅79 -37⋅ 32 (=1)

Es gilt also: ggt(79,32)=1 = 15⋅79 -37⋅32

oder wenn man 15⋅79 auf die linke Seite bringt:

1 -15⋅79 = -37⋅32

-37⋅32 = -15⋅79 + 1 |+79⋅32

-37⋅32 + 79⋅32 = -15⋅79 + 79⋅32 + 1

(-37 + 79) ⋅ 32 = (-15 + 32) ⋅ 79 + 1

42⋅32 = 17⋅79 + 1

Es gilt also: 42⋅32 = 17⋅79 +1

Somit 42⋅32 = 1 mod 79

42 ist also das Inverse von 32 mod 79

Schlüsselpaar für RSA

Beispiel:

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