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: (1200 + 76) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1200 + 76) mod 4 ≡ (1200 mod 4 + 76 mod 4) mod 4.

1200 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 1200 = 1200+0 = 4 ⋅ 300 +0.

76 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 76 = 80-4 = 4 ⋅ 20 -4 = 4 ⋅ 20 - 4 + 0.

Somit gilt:

(1200 + 76) mod 4 ≡ (0 + 0) mod 4 ≡ 0 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (70 ⋅ 31) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 31) mod 11 ≡ (70 mod 11 ⋅ 31 mod 11) mod 11.

70 mod 11 ≡ 4 mod 11 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 6 ⋅ 11 + 4 ist.

31 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 31 = 22 + 9 = 2 ⋅ 11 + 9 ist.

Somit gilt:

(70 ⋅ 31) mod 11 ≡ (4 ⋅ 9) mod 11 ≡ 36 mod 11 ≡ 3 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 3958 mod 673.

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. 395 -> x
2. mod(x²,673) -> 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: 3951=395

2: 3952=3951+1=3951⋅3951 ≡ 395⋅395=156025 ≡ 562 mod 673

4: 3954=3952+2=3952⋅3952 ≡ 562⋅562=315844 ≡ 207 mod 673

8: 3958=3954+4=3954⋅3954 ≡ 207⋅207=42849 ≡ 450 mod 673

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 40183 mod 751.

Lösung einblenden

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

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

83 = 64+16+2+1

1: 4011=401

2: 4012=4011+1=4011⋅4011 ≡ 401⋅401=160801 ≡ 87 mod 751

4: 4014=4012+2=4012⋅4012 ≡ 87⋅87=7569 ≡ 59 mod 751

8: 4018=4014+4=4014⋅4014 ≡ 59⋅59=3481 ≡ 477 mod 751

16: 40116=4018+8=4018⋅4018 ≡ 477⋅477=227529 ≡ 727 mod 751

32: 40132=40116+16=40116⋅40116 ≡ 727⋅727=528529 ≡ 576 mod 751

64: 40164=40132+32=40132⋅40132 ≡ 576⋅576=331776 ≡ 585 mod 751

40183

= 40164+16+2+1

= 40164⋅40116⋅4012⋅4011

585 ⋅ 727 ⋅ 87 ⋅ 401 mod 751
425295 ⋅ 87 ⋅ 401 mod 751 ≡ 229 ⋅ 87 ⋅ 401 mod 751
19923 ⋅ 401 mod 751 ≡ 397 ⋅ 401 mod 751
159197 mod 751 ≡ 736 mod 751

Es gilt also: 40183 ≡ 736 mod 751

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>79 = 2⋅27 + 25
=>27 = 1⋅25 + 2
=>25 = 12⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(79,27)=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= 25-12⋅2
2= 27-1⋅25 eingesetzt in die Zeile drüber: 1 = 1⋅25 -12⋅(27 -1⋅ 25)
= 1⋅25 -12⋅27 +12⋅ 25)
= -12⋅27 +13⋅ 25 (=1)
25= 79-2⋅27 eingesetzt in die Zeile drüber: 1 = -12⋅27 +13⋅(79 -2⋅ 27)
= -12⋅27 +13⋅79 -26⋅ 27)
= 13⋅79 -38⋅ 27 (=1)

Es gilt also: ggt(79,27)=1 = 13⋅79 -38⋅27

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

1 -13⋅79 = -38⋅27

-38⋅27 = -13⋅79 + 1 |+79⋅27

-38⋅27 + 79⋅27 = -13⋅79 + 79⋅27 + 1

(-38 + 79) ⋅ 27 = (-13 + 27) ⋅ 79 + 1

41⋅27 = 14⋅79 + 1

Es gilt also: 41⋅27 = 14⋅79 +1

Somit 41⋅27 = 1 mod 79

41 ist also das Inverse von 27 mod 79

Schlüsselpaar für RSA

Beispiel:

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