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: (116 + 7998) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(116 + 7998) mod 4 ≡ (116 mod 4 + 7998 mod 4) mod 4.

116 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 116 = 120-4 = 4 ⋅ 30 -4 = 4 ⋅ 30 - 4 + 0.

7998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 7998 = 7000+998 = 4 ⋅ 1750 +998.

Somit gilt:

(116 + 7998) mod 4 ≡ (0 + 2) mod 4 ≡ 2 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (35 ⋅ 80) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 80) mod 7 ≡ (35 mod 7 ⋅ 80 mod 7) mod 7.

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

80 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 80 = 77 + 3 = 11 ⋅ 7 + 3 ist.

Somit gilt:

(35 ⋅ 80) mod 7 ≡ (0 ⋅ 3) mod 7 ≡ 0 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 47716 mod 661.

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. 477 -> x
2. mod(x²,661) -> 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: 4771=477

2: 4772=4771+1=4771⋅4771 ≡ 477⋅477=227529 ≡ 145 mod 661

4: 4774=4772+2=4772⋅4772 ≡ 145⋅145=21025 ≡ 534 mod 661

8: 4778=4774+4=4774⋅4774 ≡ 534⋅534=285156 ≡ 265 mod 661

16: 47716=4778+8=4778⋅4778 ≡ 265⋅265=70225 ≡ 159 mod 661

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 623250 mod 631.

Lösung einblenden

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

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

250 = 128+64+32+16+8+2

1: 6231=623

2: 6232=6231+1=6231⋅6231 ≡ 623⋅623=388129 ≡ 64 mod 631

4: 6234=6232+2=6232⋅6232 ≡ 64⋅64=4096 ≡ 310 mod 631

8: 6238=6234+4=6234⋅6234 ≡ 310⋅310=96100 ≡ 188 mod 631

16: 62316=6238+8=6238⋅6238 ≡ 188⋅188=35344 ≡ 8 mod 631

32: 62332=62316+16=62316⋅62316 ≡ 8⋅8=64 ≡ 64 mod 631

64: 62364=62332+32=62332⋅62332 ≡ 64⋅64=4096 ≡ 310 mod 631

128: 623128=62364+64=62364⋅62364 ≡ 310⋅310=96100 ≡ 188 mod 631

623250

= 623128+64+32+16+8+2

= 623128⋅62364⋅62332⋅62316⋅6238⋅6232

188 ⋅ 310 ⋅ 64 ⋅ 8 ⋅ 188 ⋅ 64 mod 631
58280 ⋅ 64 ⋅ 8 ⋅ 188 ⋅ 64 mod 631 ≡ 228 ⋅ 64 ⋅ 8 ⋅ 188 ⋅ 64 mod 631
14592 ⋅ 8 ⋅ 188 ⋅ 64 mod 631 ≡ 79 ⋅ 8 ⋅ 188 ⋅ 64 mod 631
632 ⋅ 188 ⋅ 64 mod 631 ≡ 1 ⋅ 188 ⋅ 64 mod 631
188 ⋅ 64 mod 631
12032 mod 631 ≡ 43 mod 631

Es gilt also: 623250 ≡ 43 mod 631

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 56 ⋅ x ≡ 1 mod 79 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 79 und 56

=>79 = 1⋅56 + 23
=>56 = 2⋅23 + 10
=>23 = 2⋅10 + 3
=>10 = 3⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(79,56)=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= 10-3⋅3
3= 23-2⋅10 eingesetzt in die Zeile drüber: 1 = 1⋅10 -3⋅(23 -2⋅ 10)
= 1⋅10 -3⋅23 +6⋅ 10)
= -3⋅23 +7⋅ 10 (=1)
10= 56-2⋅23 eingesetzt in die Zeile drüber: 1 = -3⋅23 +7⋅(56 -2⋅ 23)
= -3⋅23 +7⋅56 -14⋅ 23)
= 7⋅56 -17⋅ 23 (=1)
23= 79-1⋅56 eingesetzt in die Zeile drüber: 1 = 7⋅56 -17⋅(79 -1⋅ 56)
= 7⋅56 -17⋅79 +17⋅ 56)
= -17⋅79 +24⋅ 56 (=1)

Es gilt also: ggt(79,56)=1 = -17⋅79 +24⋅56

oder wenn man -17⋅79 auf die linke Seite bringt:

1 +17⋅79 = +24⋅56

Es gilt also: 24⋅56 = 17⋅79 +1

Somit 24⋅56 = 1 mod 79

24 ist also das Inverse von 56 mod 79

Schlüsselpaar für RSA

Beispiel:

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