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: (93 - 298) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(93 - 298) mod 3 ≡ (93 mod 3 - 298 mod 3) mod 3.

93 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 93 = 90+3 = 3 ⋅ 30 +3.

298 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 298 = 300-2 = 3 ⋅ 100 -2 = 3 ⋅ 100 - 3 + 1.

Somit gilt:

(93 - 298) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (35 ⋅ 98) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 98) mod 5 ≡ (35 mod 5 ⋅ 98 mod 5) mod 5.

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

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 95 + 3 = 19 ⋅ 5 + 3 ist.

Somit gilt:

(35 ⋅ 98) mod 5 ≡ (0 ⋅ 3) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 192128 mod 401.

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. 192 -> x
2. mod(x²,401) -> 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: 1921=192

2: 1922=1921+1=1921⋅1921 ≡ 192⋅192=36864 ≡ 373 mod 401

4: 1924=1922+2=1922⋅1922 ≡ 373⋅373=139129 ≡ 383 mod 401

8: 1928=1924+4=1924⋅1924 ≡ 383⋅383=146689 ≡ 324 mod 401

16: 19216=1928+8=1928⋅1928 ≡ 324⋅324=104976 ≡ 315 mod 401

32: 19232=19216+16=19216⋅19216 ≡ 315⋅315=99225 ≡ 178 mod 401

64: 19264=19232+32=19232⋅19232 ≡ 178⋅178=31684 ≡ 5 mod 401

128: 192128=19264+64=19264⋅19264 ≡ 5⋅5=25 ≡ 25 mod 401

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 667179 mod 733.

Lösung einblenden

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

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

179 = 128+32+16+2+1

1: 6671=667

2: 6672=6671+1=6671⋅6671 ≡ 667⋅667=444889 ≡ 691 mod 733

4: 6674=6672+2=6672⋅6672 ≡ 691⋅691=477481 ≡ 298 mod 733

8: 6678=6674+4=6674⋅6674 ≡ 298⋅298=88804 ≡ 111 mod 733

16: 66716=6678+8=6678⋅6678 ≡ 111⋅111=12321 ≡ 593 mod 733

32: 66732=66716+16=66716⋅66716 ≡ 593⋅593=351649 ≡ 542 mod 733

64: 66764=66732+32=66732⋅66732 ≡ 542⋅542=293764 ≡ 564 mod 733

128: 667128=66764+64=66764⋅66764 ≡ 564⋅564=318096 ≡ 707 mod 733

667179

= 667128+32+16+2+1

= 667128⋅66732⋅66716⋅6672⋅6671

707 ⋅ 542 ⋅ 593 ⋅ 691 ⋅ 667 mod 733
383194 ⋅ 593 ⋅ 691 ⋅ 667 mod 733 ≡ 568 ⋅ 593 ⋅ 691 ⋅ 667 mod 733
336824 ⋅ 691 ⋅ 667 mod 733 ≡ 377 ⋅ 691 ⋅ 667 mod 733
260507 ⋅ 667 mod 733 ≡ 292 ⋅ 667 mod 733
194764 mod 733 ≡ 519 mod 733

Es gilt also: 667179 ≡ 519 mod 733

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>79 = 2⋅35 + 9
=>35 = 3⋅9 + 8
=>9 = 1⋅8 + 1
=>8 = 8⋅1 + 0

also gilt: ggt(79,35)=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= 9-1⋅8
8= 35-3⋅9 eingesetzt in die Zeile drüber: 1 = 1⋅9 -1⋅(35 -3⋅ 9)
= 1⋅9 -1⋅35 +3⋅ 9)
= -1⋅35 +4⋅ 9 (=1)
9= 79-2⋅35 eingesetzt in die Zeile drüber: 1 = -1⋅35 +4⋅(79 -2⋅ 35)
= -1⋅35 +4⋅79 -8⋅ 35)
= 4⋅79 -9⋅ 35 (=1)

Es gilt also: ggt(79,35)=1 = 4⋅79 -9⋅35

oder wenn man 4⋅79 auf die linke Seite bringt:

1 -4⋅79 = -9⋅35

-9⋅35 = -4⋅79 + 1 |+79⋅35

-9⋅35 + 79⋅35 = -4⋅79 + 79⋅35 + 1

(-9 + 79) ⋅ 35 = (-4 + 35) ⋅ 79 + 1

70⋅35 = 31⋅79 + 1

Es gilt also: 70⋅35 = 31⋅79 +1

Somit 70⋅35 = 1 mod 79

70 ist also das Inverse von 35 mod 79

Schlüsselpaar für RSA

Beispiel:

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