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: (5997 - 11999) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(5997 - 11999) mod 3 ≡ (5997 mod 3 - 11999 mod 3) mod 3.

5997 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 5997 = 6000-3 = 3 ⋅ 2000 -3 = 3 ⋅ 2000 - 3 + 0.

11999 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 11999 = 12000-1 = 3 ⋅ 4000 -1 = 3 ⋅ 4000 - 3 + 2.

Somit gilt:

(5997 - 11999) mod 3 ≡ (0 - 2) mod 3 ≡ -2 mod 3 ≡ 1 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (20 ⋅ 56) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(20 ⋅ 56) mod 4 ≡ (20 mod 4 ⋅ 56 mod 4) mod 4.

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

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

Somit gilt:

(20 ⋅ 56) mod 4 ≡ (0 ⋅ 0) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 43516 mod 733.

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. 435 -> x
2. mod(x²,733) -> 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: 4351=435

2: 4352=4351+1=4351⋅4351 ≡ 435⋅435=189225 ≡ 111 mod 733

4: 4354=4352+2=4352⋅4352 ≡ 111⋅111=12321 ≡ 593 mod 733

8: 4358=4354+4=4354⋅4354 ≡ 593⋅593=351649 ≡ 542 mod 733

16: 43516=4358+8=4358⋅4358 ≡ 542⋅542=293764 ≡ 564 mod 733

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 254247 mod 487.

Lösung einblenden

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

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

247 = 128+64+32+16+4+2+1

1: 2541=254

2: 2542=2541+1=2541⋅2541 ≡ 254⋅254=64516 ≡ 232 mod 487

4: 2544=2542+2=2542⋅2542 ≡ 232⋅232=53824 ≡ 254 mod 487

8: 2548=2544+4=2544⋅2544 ≡ 254⋅254=64516 ≡ 232 mod 487

16: 25416=2548+8=2548⋅2548 ≡ 232⋅232=53824 ≡ 254 mod 487

32: 25432=25416+16=25416⋅25416 ≡ 254⋅254=64516 ≡ 232 mod 487

64: 25464=25432+32=25432⋅25432 ≡ 232⋅232=53824 ≡ 254 mod 487

128: 254128=25464+64=25464⋅25464 ≡ 254⋅254=64516 ≡ 232 mod 487

254247

= 254128+64+32+16+4+2+1

= 254128⋅25464⋅25432⋅25416⋅2544⋅2542⋅2541

232 ⋅ 254 ⋅ 232 ⋅ 254 ⋅ 254 ⋅ 232 ⋅ 254 mod 487
58928 ⋅ 232 ⋅ 254 ⋅ 254 ⋅ 232 ⋅ 254 mod 487 ≡ 1 ⋅ 232 ⋅ 254 ⋅ 254 ⋅ 232 ⋅ 254 mod 487
232 ⋅ 254 ⋅ 254 ⋅ 232 ⋅ 254 mod 487
58928 ⋅ 254 ⋅ 232 ⋅ 254 mod 487 ≡ 1 ⋅ 254 ⋅ 232 ⋅ 254 mod 487
254 ⋅ 232 ⋅ 254 mod 487
58928 ⋅ 254 mod 487 ≡ 1 ⋅ 254 mod 487
254 mod 487

Es gilt also: 254247 ≡ 254 mod 487

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 2⋅47 + 7
=>47 = 6⋅7 + 5
=>7 = 1⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(101,47)=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= 5-2⋅2
2= 7-1⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(7 -1⋅ 5)
= 1⋅5 -2⋅7 +2⋅ 5)
= -2⋅7 +3⋅ 5 (=1)
5= 47-6⋅7 eingesetzt in die Zeile drüber: 1 = -2⋅7 +3⋅(47 -6⋅ 7)
= -2⋅7 +3⋅47 -18⋅ 7)
= 3⋅47 -20⋅ 7 (=1)
7= 101-2⋅47 eingesetzt in die Zeile drüber: 1 = 3⋅47 -20⋅(101 -2⋅ 47)
= 3⋅47 -20⋅101 +40⋅ 47)
= -20⋅101 +43⋅ 47 (=1)

Es gilt also: ggt(101,47)=1 = -20⋅101 +43⋅47

oder wenn man -20⋅101 auf die linke Seite bringt:

1 +20⋅101 = +43⋅47

Es gilt also: 43⋅47 = 20⋅101 +1

Somit 43⋅47 = 1 mod 101

43 ist also das Inverse von 47 mod 101

Schlüsselpaar für RSA

Beispiel:

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