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: (603 + 1499) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(603 + 1499) mod 3 ≡ (603 mod 3 + 1499 mod 3) mod 3.

603 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 603 = 600+3 = 3 ⋅ 200 +3.

1499 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1499 = 1500-1 = 3 ⋅ 500 -1 = 3 ⋅ 500 - 3 + 2.

Somit gilt:

(603 + 1499) mod 3 ≡ (0 + 2) mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (64 ⋅ 64) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(64 ⋅ 64) mod 7 ≡ (64 mod 7 ⋅ 64 mod 7) mod 7.

64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 9 ⋅ 7 + 1 ist.

64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 9 ⋅ 7 + 1 ist.

Somit gilt:

(64 ⋅ 64) mod 7 ≡ (1 ⋅ 1) mod 7 ≡ 1 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 407128 mod 557.

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. 407 -> x
2. mod(x²,557) -> 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: 4071=407

2: 4072=4071+1=4071⋅4071 ≡ 407⋅407=165649 ≡ 220 mod 557

4: 4074=4072+2=4072⋅4072 ≡ 220⋅220=48400 ≡ 498 mod 557

8: 4078=4074+4=4074⋅4074 ≡ 498⋅498=248004 ≡ 139 mod 557

16: 40716=4078+8=4078⋅4078 ≡ 139⋅139=19321 ≡ 383 mod 557

32: 40732=40716+16=40716⋅40716 ≡ 383⋅383=146689 ≡ 198 mod 557

64: 40764=40732+32=40732⋅40732 ≡ 198⋅198=39204 ≡ 214 mod 557

128: 407128=40764+64=40764⋅40764 ≡ 214⋅214=45796 ≡ 122 mod 557

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 28061 mod 521.

Lösung einblenden

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

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

61 = 32+16+8+4+1

1: 2801=280

2: 2802=2801+1=2801⋅2801 ≡ 280⋅280=78400 ≡ 250 mod 521

4: 2804=2802+2=2802⋅2802 ≡ 250⋅250=62500 ≡ 501 mod 521

8: 2808=2804+4=2804⋅2804 ≡ 501⋅501=251001 ≡ 400 mod 521

16: 28016=2808+8=2808⋅2808 ≡ 400⋅400=160000 ≡ 53 mod 521

32: 28032=28016+16=28016⋅28016 ≡ 53⋅53=2809 ≡ 204 mod 521

28061

= 28032+16+8+4+1

= 28032⋅28016⋅2808⋅2804⋅2801

204 ⋅ 53 ⋅ 400 ⋅ 501 ⋅ 280 mod 521
10812 ⋅ 400 ⋅ 501 ⋅ 280 mod 521 ≡ 392 ⋅ 400 ⋅ 501 ⋅ 280 mod 521
156800 ⋅ 501 ⋅ 280 mod 521 ≡ 500 ⋅ 501 ⋅ 280 mod 521
250500 ⋅ 280 mod 521 ≡ 420 ⋅ 280 mod 521
117600 mod 521 ≡ 375 mod 521

Es gilt also: 28061 ≡ 375 mod 521

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 46 ⋅ x ≡ 1 mod 71 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 71 und 46

=>71 = 1⋅46 + 25
=>46 = 1⋅25 + 21
=>25 = 1⋅21 + 4
=>21 = 5⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(71,46)=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= 21-5⋅4
4= 25-1⋅21 eingesetzt in die Zeile drüber: 1 = 1⋅21 -5⋅(25 -1⋅ 21)
= 1⋅21 -5⋅25 +5⋅ 21)
= -5⋅25 +6⋅ 21 (=1)
21= 46-1⋅25 eingesetzt in die Zeile drüber: 1 = -5⋅25 +6⋅(46 -1⋅ 25)
= -5⋅25 +6⋅46 -6⋅ 25)
= 6⋅46 -11⋅ 25 (=1)
25= 71-1⋅46 eingesetzt in die Zeile drüber: 1 = 6⋅46 -11⋅(71 -1⋅ 46)
= 6⋅46 -11⋅71 +11⋅ 46)
= -11⋅71 +17⋅ 46 (=1)

Es gilt also: ggt(71,46)=1 = -11⋅71 +17⋅46

oder wenn man -11⋅71 auf die linke Seite bringt:

1 +11⋅71 = +17⋅46

Es gilt also: 17⋅46 = 11⋅71 +1

Somit 17⋅46 = 1 mod 71

17 ist also das Inverse von 46 mod 71

Schlüsselpaar für RSA

Beispiel:

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