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

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(84 - 404) mod 4 ≡ (84 mod 4 - 404 mod 4) mod 4.

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

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

Somit gilt:

(84 - 404) mod 4 ≡ (0 - 0) mod 4 ≡ 0 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (58 ⋅ 21) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(58 ⋅ 21) mod 11 ≡ (58 mod 11 ⋅ 21 mod 11) mod 11.

58 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 58 = 55 + 3 = 5 ⋅ 11 + 3 ist.

21 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 21 = 11 + 10 = 1 ⋅ 11 + 10 ist.

Somit gilt:

(58 ⋅ 21) mod 11 ≡ (3 ⋅ 10) mod 11 ≡ 30 mod 11 ≡ 8 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 565128 mod 977.

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. 565 -> x
2. mod(x²,977) -> 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: 5651=565

2: 5652=5651+1=5651⋅5651 ≡ 565⋅565=319225 ≡ 723 mod 977

4: 5654=5652+2=5652⋅5652 ≡ 723⋅723=522729 ≡ 34 mod 977

8: 5658=5654+4=5654⋅5654 ≡ 34⋅34=1156 ≡ 179 mod 977

16: 56516=5658+8=5658⋅5658 ≡ 179⋅179=32041 ≡ 777 mod 977

32: 56532=56516+16=56516⋅56516 ≡ 777⋅777=603729 ≡ 920 mod 977

64: 56564=56532+32=56532⋅56532 ≡ 920⋅920=846400 ≡ 318 mod 977

128: 565128=56564+64=56564⋅56564 ≡ 318⋅318=101124 ≡ 493 mod 977

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 547200 mod 809.

Lösung einblenden

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

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

200 = 128+64+8

1: 5471=547

2: 5472=5471+1=5471⋅5471 ≡ 547⋅547=299209 ≡ 688 mod 809

4: 5474=5472+2=5472⋅5472 ≡ 688⋅688=473344 ≡ 79 mod 809

8: 5478=5474+4=5474⋅5474 ≡ 79⋅79=6241 ≡ 578 mod 809

16: 54716=5478+8=5478⋅5478 ≡ 578⋅578=334084 ≡ 776 mod 809

32: 54732=54716+16=54716⋅54716 ≡ 776⋅776=602176 ≡ 280 mod 809

64: 54764=54732+32=54732⋅54732 ≡ 280⋅280=78400 ≡ 736 mod 809

128: 547128=54764+64=54764⋅54764 ≡ 736⋅736=541696 ≡ 475 mod 809

547200

= 547128+64+8

= 547128⋅54764⋅5478

475 ⋅ 736 ⋅ 578 mod 809
349600 ⋅ 578 mod 809 ≡ 112 ⋅ 578 mod 809
64736 mod 809 ≡ 16 mod 809

Es gilt also: 547200 ≡ 16 mod 809

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 22 ⋅ x ≡ 1 mod 61 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 61 und 22

=>61 = 2⋅22 + 17
=>22 = 1⋅17 + 5
=>17 = 3⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(61,22)=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= 5-2⋅2
2= 17-3⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(17 -3⋅ 5)
= 1⋅5 -2⋅17 +6⋅ 5)
= -2⋅17 +7⋅ 5 (=1)
5= 22-1⋅17 eingesetzt in die Zeile drüber: 1 = -2⋅17 +7⋅(22 -1⋅ 17)
= -2⋅17 +7⋅22 -7⋅ 17)
= 7⋅22 -9⋅ 17 (=1)
17= 61-2⋅22 eingesetzt in die Zeile drüber: 1 = 7⋅22 -9⋅(61 -2⋅ 22)
= 7⋅22 -9⋅61 +18⋅ 22)
= -9⋅61 +25⋅ 22 (=1)

Es gilt also: ggt(61,22)=1 = -9⋅61 +25⋅22

oder wenn man -9⋅61 auf die linke Seite bringt:

1 +9⋅61 = +25⋅22

Es gilt also: 25⋅22 = 9⋅61 +1

Somit 25⋅22 = 1 mod 61

25 ist also das Inverse von 22 mod 61

Schlüsselpaar für RSA

Beispiel:

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