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: (2001 + 400) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2001 + 400) mod 4 ≡ (2001 mod 4 + 400 mod 4) mod 4.

2001 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 2001 = 2000+1 = 4 ⋅ 500 +1.

400 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 400 = 400+0 = 4 ⋅ 100 +0.

Somit gilt:

(2001 + 400) mod 4 ≡ (1 + 0) mod 4 ≡ 1 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (22 ⋅ 75) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(22 ⋅ 75) mod 11 ≡ (22 mod 11 ⋅ 75 mod 11) mod 11.

22 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 22 = 22 + 0 = 2 ⋅ 11 + 0 ist.

75 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 75 = 66 + 9 = 6 ⋅ 11 + 9 ist.

Somit gilt:

(22 ⋅ 75) mod 11 ≡ (0 ⋅ 9) mod 11 ≡ 0 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 65616 mod 709.

Lösung einblenden

Die 16 im Exponent ist ja ein reine 2er-Potenz (24).

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. 656 -> x
2. mod(x²,709) -> 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: 6561=656

2: 6562=6561+1=6561⋅6561 ≡ 656⋅656=430336 ≡ 682 mod 709

4: 6564=6562+2=6562⋅6562 ≡ 682⋅682=465124 ≡ 20 mod 709

8: 6568=6564+4=6564⋅6564 ≡ 20⋅20=400 ≡ 400 mod 709

16: 65616=6568+8=6568⋅6568 ≡ 400⋅400=160000 ≡ 475 mod 709

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 161153 mod 211.

Lösung einblenden

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

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

153 = 128+16+8+1

1: 1611=161

2: 1612=1611+1=1611⋅1611 ≡ 161⋅161=25921 ≡ 179 mod 211

4: 1614=1612+2=1612⋅1612 ≡ 179⋅179=32041 ≡ 180 mod 211

8: 1618=1614+4=1614⋅1614 ≡ 180⋅180=32400 ≡ 117 mod 211

16: 16116=1618+8=1618⋅1618 ≡ 117⋅117=13689 ≡ 185 mod 211

32: 16132=16116+16=16116⋅16116 ≡ 185⋅185=34225 ≡ 43 mod 211

64: 16164=16132+32=16132⋅16132 ≡ 43⋅43=1849 ≡ 161 mod 211

128: 161128=16164+64=16164⋅16164 ≡ 161⋅161=25921 ≡ 179 mod 211

161153

= 161128+16+8+1

= 161128⋅16116⋅1618⋅1611

179 ⋅ 185 ⋅ 117 ⋅ 161 mod 211
33115 ⋅ 117 ⋅ 161 mod 211 ≡ 199 ⋅ 117 ⋅ 161 mod 211
23283 ⋅ 161 mod 211 ≡ 73 ⋅ 161 mod 211
11753 mod 211 ≡ 148 mod 211

Es gilt also: 161153 ≡ 148 mod 211

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 1⋅82 + 19
=>82 = 4⋅19 + 6
=>19 = 3⋅6 + 1
=>6 = 6⋅1 + 0

also gilt: ggt(101,82)=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= 19-3⋅6
6= 82-4⋅19 eingesetzt in die Zeile drüber: 1 = 1⋅19 -3⋅(82 -4⋅ 19)
= 1⋅19 -3⋅82 +12⋅ 19)
= -3⋅82 +13⋅ 19 (=1)
19= 101-1⋅82 eingesetzt in die Zeile drüber: 1 = -3⋅82 +13⋅(101 -1⋅ 82)
= -3⋅82 +13⋅101 -13⋅ 82)
= 13⋅101 -16⋅ 82 (=1)

Es gilt also: ggt(101,82)=1 = 13⋅101 -16⋅82

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

1 -13⋅101 = -16⋅82

-16⋅82 = -13⋅101 + 1 |+101⋅82

-16⋅82 + 101⋅82 = -13⋅101 + 101⋅82 + 1

(-16 + 101) ⋅ 82 = (-13 + 82) ⋅ 101 + 1

85⋅82 = 69⋅101 + 1

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

Somit 85⋅82 = 1 mod 101

85 ist also das Inverse von 82 mod 101

Schlüsselpaar für RSA

Beispiel:

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