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: (27000 - 279) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(27000 - 279) mod 9 ≡ (27000 mod 9 - 279 mod 9) mod 9.

27000 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 27000 = 27000+0 = 9 ⋅ 3000 +0.

279 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 279 = 270+9 = 9 ⋅ 30 +9.

Somit gilt:

(27000 - 279) mod 9 ≡ (0 - 0) mod 9 ≡ 0 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (50 ⋅ 91) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(50 ⋅ 91) mod 4 ≡ (50 mod 4 ⋅ 91 mod 4) mod 4.

50 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 50 = 48 + 2 = 12 ⋅ 4 + 2 ist.

91 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 91 = 88 + 3 = 22 ⋅ 4 + 3 ist.

Somit gilt:

(50 ⋅ 91) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 4208 mod 641.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 420 -> x
2. mod(x²,641) -> 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: 4201=420

2: 4202=4201+1=4201⋅4201 ≡ 420⋅420=176400 ≡ 125 mod 641

4: 4204=4202+2=4202⋅4202 ≡ 125⋅125=15625 ≡ 241 mod 641

8: 4208=4204+4=4204⋅4204 ≡ 241⋅241=58081 ≡ 391 mod 641

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 692171 mod 967.

Lösung einblenden

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

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

171 = 128+32+8+2+1

1: 6921=692

2: 6922=6921+1=6921⋅6921 ≡ 692⋅692=478864 ≡ 199 mod 967

4: 6924=6922+2=6922⋅6922 ≡ 199⋅199=39601 ≡ 921 mod 967

8: 6928=6924+4=6924⋅6924 ≡ 921⋅921=848241 ≡ 182 mod 967

16: 69216=6928+8=6928⋅6928 ≡ 182⋅182=33124 ≡ 246 mod 967

32: 69232=69216+16=69216⋅69216 ≡ 246⋅246=60516 ≡ 562 mod 967

64: 69264=69232+32=69232⋅69232 ≡ 562⋅562=315844 ≡ 602 mod 967

128: 692128=69264+64=69264⋅69264 ≡ 602⋅602=362404 ≡ 746 mod 967

692171

= 692128+32+8+2+1

= 692128⋅69232⋅6928⋅6922⋅6921

746 ⋅ 562 ⋅ 182 ⋅ 199 ⋅ 692 mod 967
419252 ⋅ 182 ⋅ 199 ⋅ 692 mod 967 ≡ 541 ⋅ 182 ⋅ 199 ⋅ 692 mod 967
98462 ⋅ 199 ⋅ 692 mod 967 ≡ 795 ⋅ 199 ⋅ 692 mod 967
158205 ⋅ 692 mod 967 ≡ 584 ⋅ 692 mod 967
404128 mod 967 ≡ 889 mod 967

Es gilt also: 692171 ≡ 889 mod 967

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 66 ⋅ x ≡ 1 mod 97 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 97 und 66

=>97 = 1⋅66 + 31
=>66 = 2⋅31 + 4
=>31 = 7⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(97,66)=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= 31-7⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(31 -7⋅ 4)
= 1⋅4 -1⋅31 +7⋅ 4)
= -1⋅31 +8⋅ 4 (=1)
4= 66-2⋅31 eingesetzt in die Zeile drüber: 1 = -1⋅31 +8⋅(66 -2⋅ 31)
= -1⋅31 +8⋅66 -16⋅ 31)
= 8⋅66 -17⋅ 31 (=1)
31= 97-1⋅66 eingesetzt in die Zeile drüber: 1 = 8⋅66 -17⋅(97 -1⋅ 66)
= 8⋅66 -17⋅97 +17⋅ 66)
= -17⋅97 +25⋅ 66 (=1)

Es gilt also: ggt(97,66)=1 = -17⋅97 +25⋅66

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

1 +17⋅97 = +25⋅66

Es gilt also: 25⋅66 = 17⋅97 +1

Somit 25⋅66 = 1 mod 97

25 ist also das Inverse von 66 mod 97

Schlüsselpaar für RSA

Beispiel:

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