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: (404 + 156) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(404 + 156) mod 4 ≡ (404 mod 4 + 156 mod 4) mod 4.

404 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 404 = 400+4 = 4 ⋅ 100 +4.

156 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 156 = 160-4 = 4 ⋅ 40 -4 = 4 ⋅ 40 - 4 + 0.

Somit gilt:

(404 + 156) mod 4 ≡ (0 + 0) mod 4 ≡ 0 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (30 ⋅ 27) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(30 ⋅ 27) mod 9 ≡ (30 mod 9 ⋅ 27 mod 9) mod 9.

30 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 30 = 27 + 3 = 3 ⋅ 9 + 3 ist.

27 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 27 = 27 + 0 = 3 ⋅ 9 + 0 ist.

Somit gilt:

(30 ⋅ 27) mod 9 ≡ (3 ⋅ 0) mod 9 ≡ 0 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 199128 mod 463.

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. 199 -> x
2. mod(x²,463) -> 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: 1991=199

2: 1992=1991+1=1991⋅1991 ≡ 199⋅199=39601 ≡ 246 mod 463

4: 1994=1992+2=1992⋅1992 ≡ 246⋅246=60516 ≡ 326 mod 463

8: 1998=1994+4=1994⋅1994 ≡ 326⋅326=106276 ≡ 249 mod 463

16: 19916=1998+8=1998⋅1998 ≡ 249⋅249=62001 ≡ 422 mod 463

32: 19932=19916+16=19916⋅19916 ≡ 422⋅422=178084 ≡ 292 mod 463

64: 19964=19932+32=19932⋅19932 ≡ 292⋅292=85264 ≡ 72 mod 463

128: 199128=19964+64=19964⋅19964 ≡ 72⋅72=5184 ≡ 91 mod 463

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 578199 mod 593.

Lösung einblenden

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

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

199 = 128+64+4+2+1

1: 5781=578

2: 5782=5781+1=5781⋅5781 ≡ 578⋅578=334084 ≡ 225 mod 593

4: 5784=5782+2=5782⋅5782 ≡ 225⋅225=50625 ≡ 220 mod 593

8: 5788=5784+4=5784⋅5784 ≡ 220⋅220=48400 ≡ 367 mod 593

16: 57816=5788+8=5788⋅5788 ≡ 367⋅367=134689 ≡ 78 mod 593

32: 57832=57816+16=57816⋅57816 ≡ 78⋅78=6084 ≡ 154 mod 593

64: 57864=57832+32=57832⋅57832 ≡ 154⋅154=23716 ≡ 589 mod 593

128: 578128=57864+64=57864⋅57864 ≡ 589⋅589=346921 ≡ 16 mod 593

578199

= 578128+64+4+2+1

= 578128⋅57864⋅5784⋅5782⋅5781

16 ⋅ 589 ⋅ 220 ⋅ 225 ⋅ 578 mod 593
9424 ⋅ 220 ⋅ 225 ⋅ 578 mod 593 ≡ 529 ⋅ 220 ⋅ 225 ⋅ 578 mod 593
116380 ⋅ 225 ⋅ 578 mod 593 ≡ 152 ⋅ 225 ⋅ 578 mod 593
34200 ⋅ 578 mod 593 ≡ 399 ⋅ 578 mod 593
230622 mod 593 ≡ 538 mod 593

Es gilt also: 578199 ≡ 538 mod 593

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 53 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 53

=>89 = 1⋅53 + 36
=>53 = 1⋅36 + 17
=>36 = 2⋅17 + 2
=>17 = 8⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(89,53)=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= 17-8⋅2
2= 36-2⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -8⋅(36 -2⋅ 17)
= 1⋅17 -8⋅36 +16⋅ 17)
= -8⋅36 +17⋅ 17 (=1)
17= 53-1⋅36 eingesetzt in die Zeile drüber: 1 = -8⋅36 +17⋅(53 -1⋅ 36)
= -8⋅36 +17⋅53 -17⋅ 36)
= 17⋅53 -25⋅ 36 (=1)
36= 89-1⋅53 eingesetzt in die Zeile drüber: 1 = 17⋅53 -25⋅(89 -1⋅ 53)
= 17⋅53 -25⋅89 +25⋅ 53)
= -25⋅89 +42⋅ 53 (=1)

Es gilt also: ggt(89,53)=1 = -25⋅89 +42⋅53

oder wenn man -25⋅89 auf die linke Seite bringt:

1 +25⋅89 = +42⋅53

Es gilt also: 42⋅53 = 25⋅89 +1

Somit 42⋅53 = 1 mod 89

42 ist also das Inverse von 53 mod 89

Schlüsselpaar für RSA

Beispiel:

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