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: (28003 + 210) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(28003 + 210) mod 7 ≡ (28003 mod 7 + 210 mod 7) mod 7.

28003 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 28003 = 28000+3 = 7 ⋅ 4000 +3.

210 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 210 = 210+0 = 7 ⋅ 30 +0.

Somit gilt:

(28003 + 210) mod 7 ≡ (3 + 0) mod 7 ≡ 3 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (79 ⋅ 47) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(79 ⋅ 47) mod 7 ≡ (79 mod 7 ⋅ 47 mod 7) mod 7.

79 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 79 = 77 + 2 = 11 ⋅ 7 + 2 ist.

47 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 47 = 42 + 5 = 6 ⋅ 7 + 5 ist.

Somit gilt:

(79 ⋅ 47) mod 7 ≡ (2 ⋅ 5) mod 7 ≡ 10 mod 7 ≡ 3 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 270128 mod 509.

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. 270 -> x
2. mod(x²,509) -> 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: 2701=270

2: 2702=2701+1=2701⋅2701 ≡ 270⋅270=72900 ≡ 113 mod 509

4: 2704=2702+2=2702⋅2702 ≡ 113⋅113=12769 ≡ 44 mod 509

8: 2708=2704+4=2704⋅2704 ≡ 44⋅44=1936 ≡ 409 mod 509

16: 27016=2708+8=2708⋅2708 ≡ 409⋅409=167281 ≡ 329 mod 509

32: 27032=27016+16=27016⋅27016 ≡ 329⋅329=108241 ≡ 333 mod 509

64: 27064=27032+32=27032⋅27032 ≡ 333⋅333=110889 ≡ 436 mod 509

128: 270128=27064+64=27064⋅27064 ≡ 436⋅436=190096 ≡ 239 mod 509

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 568225 mod 641.

Lösung einblenden

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

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

225 = 128+64+32+1

1: 5681=568

2: 5682=5681+1=5681⋅5681 ≡ 568⋅568=322624 ≡ 201 mod 641

4: 5684=5682+2=5682⋅5682 ≡ 201⋅201=40401 ≡ 18 mod 641

8: 5688=5684+4=5684⋅5684 ≡ 18⋅18=324 ≡ 324 mod 641

16: 56816=5688+8=5688⋅5688 ≡ 324⋅324=104976 ≡ 493 mod 641

32: 56832=56816+16=56816⋅56816 ≡ 493⋅493=243049 ≡ 110 mod 641

64: 56864=56832+32=56832⋅56832 ≡ 110⋅110=12100 ≡ 562 mod 641

128: 568128=56864+64=56864⋅56864 ≡ 562⋅562=315844 ≡ 472 mod 641

568225

= 568128+64+32+1

= 568128⋅56864⋅56832⋅5681

472 ⋅ 562 ⋅ 110 ⋅ 568 mod 641
265264 ⋅ 110 ⋅ 568 mod 641 ≡ 531 ⋅ 110 ⋅ 568 mod 641
58410 ⋅ 568 mod 641 ≡ 79 ⋅ 568 mod 641
44872 mod 641 ≡ 2 mod 641

Es gilt also: 568225 ≡ 2 mod 641

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 85 ⋅ x ≡ 1 mod 101 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 101 und 85

=>101 = 1⋅85 + 16
=>85 = 5⋅16 + 5
=>16 = 3⋅5 + 1
=>5 = 5⋅1 + 0

also gilt: ggt(101,85)=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= 16-3⋅5
5= 85-5⋅16 eingesetzt in die Zeile drüber: 1 = 1⋅16 -3⋅(85 -5⋅ 16)
= 1⋅16 -3⋅85 +15⋅ 16)
= -3⋅85 +16⋅ 16 (=1)
16= 101-1⋅85 eingesetzt in die Zeile drüber: 1 = -3⋅85 +16⋅(101 -1⋅ 85)
= -3⋅85 +16⋅101 -16⋅ 85)
= 16⋅101 -19⋅ 85 (=1)

Es gilt also: ggt(101,85)=1 = 16⋅101 -19⋅85

oder wenn man 16⋅101 auf die linke Seite bringt:

1 -16⋅101 = -19⋅85

-19⋅85 = -16⋅101 + 1 |+101⋅85

-19⋅85 + 101⋅85 = -16⋅101 + 101⋅85 + 1

(-19 + 101) ⋅ 85 = (-16 + 85) ⋅ 101 + 1

82⋅85 = 69⋅101 + 1

Es gilt also: 82⋅85 = 69⋅101 +1

Somit 82⋅85 = 1 mod 101

82 ist also das Inverse von 85 mod 101

Schlüsselpaar für RSA

Beispiel:

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