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: (17993 - 36007) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(17993 - 36007) mod 9 ≡ (17993 mod 9 - 36007 mod 9) mod 9.

17993 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 17993 = 18000-7 = 9 ⋅ 2000 -7 = 9 ⋅ 2000 - 9 + 2.

36007 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 36007 = 36000+7 = 9 ⋅ 4000 +7.

Somit gilt:

(17993 - 36007) mod 9 ≡ (2 - 7) mod 9 ≡ -5 mod 9 ≡ 4 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (85 ⋅ 73) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(85 ⋅ 73) mod 7 ≡ (85 mod 7 ⋅ 73 mod 7) mod 7.

85 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 12 ⋅ 7 + 1 ist.

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

Somit gilt:

(85 ⋅ 73) mod 7 ≡ (1 ⋅ 3) mod 7 ≡ 3 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 39364 mod 547.

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. 393 -> x
2. mod(x²,547) -> 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: 3931=393

2: 3932=3931+1=3931⋅3931 ≡ 393⋅393=154449 ≡ 195 mod 547

4: 3934=3932+2=3932⋅3932 ≡ 195⋅195=38025 ≡ 282 mod 547

8: 3938=3934+4=3934⋅3934 ≡ 282⋅282=79524 ≡ 209 mod 547

16: 39316=3938+8=3938⋅3938 ≡ 209⋅209=43681 ≡ 468 mod 547

32: 39332=39316+16=39316⋅39316 ≡ 468⋅468=219024 ≡ 224 mod 547

64: 39364=39332+32=39332⋅39332 ≡ 224⋅224=50176 ≡ 399 mod 547

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 959141 mod 977.

Lösung einblenden

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

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

141 = 128+8+4+1

1: 9591=959

2: 9592=9591+1=9591⋅9591 ≡ 959⋅959=919681 ≡ 324 mod 977

4: 9594=9592+2=9592⋅9592 ≡ 324⋅324=104976 ≡ 437 mod 977

8: 9598=9594+4=9594⋅9594 ≡ 437⋅437=190969 ≡ 454 mod 977

16: 95916=9598+8=9598⋅9598 ≡ 454⋅454=206116 ≡ 946 mod 977

32: 95932=95916+16=95916⋅95916 ≡ 946⋅946=894916 ≡ 961 mod 977

64: 95964=95932+32=95932⋅95932 ≡ 961⋅961=923521 ≡ 256 mod 977

128: 959128=95964+64=95964⋅95964 ≡ 256⋅256=65536 ≡ 77 mod 977

959141

= 959128+8+4+1

= 959128⋅9598⋅9594⋅9591

77 ⋅ 454 ⋅ 437 ⋅ 959 mod 977
34958 ⋅ 437 ⋅ 959 mod 977 ≡ 763 ⋅ 437 ⋅ 959 mod 977
333431 ⋅ 959 mod 977 ≡ 274 ⋅ 959 mod 977
262766 mod 977 ≡ 930 mod 977

Es gilt also: 959141 ≡ 930 mod 977

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 57 ⋅ x ≡ 1 mod 83 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 83 und 57

=>83 = 1⋅57 + 26
=>57 = 2⋅26 + 5
=>26 = 5⋅5 + 1
=>5 = 5⋅1 + 0

also gilt: ggt(83,57)=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= 26-5⋅5
5= 57-2⋅26 eingesetzt in die Zeile drüber: 1 = 1⋅26 -5⋅(57 -2⋅ 26)
= 1⋅26 -5⋅57 +10⋅ 26)
= -5⋅57 +11⋅ 26 (=1)
26= 83-1⋅57 eingesetzt in die Zeile drüber: 1 = -5⋅57 +11⋅(83 -1⋅ 57)
= -5⋅57 +11⋅83 -11⋅ 57)
= 11⋅83 -16⋅ 57 (=1)

Es gilt also: ggt(83,57)=1 = 11⋅83 -16⋅57

oder wenn man 11⋅83 auf die linke Seite bringt:

1 -11⋅83 = -16⋅57

-16⋅57 = -11⋅83 + 1 |+83⋅57

-16⋅57 + 83⋅57 = -11⋅83 + 83⋅57 + 1

(-16 + 83) ⋅ 57 = (-11 + 57) ⋅ 83 + 1

67⋅57 = 46⋅83 + 1

Es gilt also: 67⋅57 = 46⋅83 +1

Somit 67⋅57 = 1 mod 83

67 ist also das Inverse von 57 mod 83

Schlüsselpaar für RSA

Beispiel:

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