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: (1501 - 19997) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1501 - 19997) mod 5 ≡ (1501 mod 5 - 19997 mod 5) mod 5.

1501 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 1501 = 1500+1 = 5 ⋅ 300 +1.

19997 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 19997 = 19000+997 = 5 ⋅ 3800 +997.

Somit gilt:

(1501 - 19997) mod 5 ≡ (1 - 2) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (40 ⋅ 17) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(40 ⋅ 17) mod 10 ≡ (40 mod 10 ⋅ 17 mod 10) mod 10.

40 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 40 = 40 + 0 = 4 ⋅ 10 + 0 ist.

17 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 17 = 10 + 7 = 1 ⋅ 10 + 7 ist.

Somit gilt:

(40 ⋅ 17) mod 10 ≡ (0 ⋅ 7) mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 52764 mod 929.

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. 527 -> x
2. mod(x²,929) -> 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: 5271=527

2: 5272=5271+1=5271⋅5271 ≡ 527⋅527=277729 ≡ 887 mod 929

4: 5274=5272+2=5272⋅5272 ≡ 887⋅887=786769 ≡ 835 mod 929

8: 5278=5274+4=5274⋅5274 ≡ 835⋅835=697225 ≡ 475 mod 929

16: 52716=5278+8=5278⋅5278 ≡ 475⋅475=225625 ≡ 807 mod 929

32: 52732=52716+16=52716⋅52716 ≡ 807⋅807=651249 ≡ 20 mod 929

64: 52764=52732+32=52732⋅52732 ≡ 20⋅20=400 ≡ 400 mod 929

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 288122 mod 383.

Lösung einblenden

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

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

122 = 64+32+16+8+2

1: 2881=288

2: 2882=2881+1=2881⋅2881 ≡ 288⋅288=82944 ≡ 216 mod 383

4: 2884=2882+2=2882⋅2882 ≡ 216⋅216=46656 ≡ 313 mod 383

8: 2888=2884+4=2884⋅2884 ≡ 313⋅313=97969 ≡ 304 mod 383

16: 28816=2888+8=2888⋅2888 ≡ 304⋅304=92416 ≡ 113 mod 383

32: 28832=28816+16=28816⋅28816 ≡ 113⋅113=12769 ≡ 130 mod 383

64: 28864=28832+32=28832⋅28832 ≡ 130⋅130=16900 ≡ 48 mod 383

288122

= 28864+32+16+8+2

= 28864⋅28832⋅28816⋅2888⋅2882

48 ⋅ 130 ⋅ 113 ⋅ 304 ⋅ 216 mod 383
6240 ⋅ 113 ⋅ 304 ⋅ 216 mod 383 ≡ 112 ⋅ 113 ⋅ 304 ⋅ 216 mod 383
12656 ⋅ 304 ⋅ 216 mod 383 ≡ 17 ⋅ 304 ⋅ 216 mod 383
5168 ⋅ 216 mod 383 ≡ 189 ⋅ 216 mod 383
40824 mod 383 ≡ 226 mod 383

Es gilt also: 288122 ≡ 226 mod 383

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>61 = 3⋅18 + 7
=>18 = 2⋅7 + 4
=>7 = 1⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(61,18)=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= 7-1⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(7 -1⋅ 4)
= 1⋅4 -1⋅7 +1⋅ 4)
= -1⋅7 +2⋅ 4 (=1)
4= 18-2⋅7 eingesetzt in die Zeile drüber: 1 = -1⋅7 +2⋅(18 -2⋅ 7)
= -1⋅7 +2⋅18 -4⋅ 7)
= 2⋅18 -5⋅ 7 (=1)
7= 61-3⋅18 eingesetzt in die Zeile drüber: 1 = 2⋅18 -5⋅(61 -3⋅ 18)
= 2⋅18 -5⋅61 +15⋅ 18)
= -5⋅61 +17⋅ 18 (=1)

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

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

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61

Schlüsselpaar für RSA

Beispiel:

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