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: (696 - 2105) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(696 - 2105) mod 7 ≡ (696 mod 7 - 2105 mod 7) mod 7.

696 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 696 = 700-4 = 7 ⋅ 100 -4 = 7 ⋅ 100 - 7 + 3.

2105 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 2105 = 2100+5 = 7 ⋅ 300 +5.

Somit gilt:

(696 - 2105) mod 7 ≡ (3 - 5) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (82 ⋅ 21) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(82 ⋅ 21) mod 5 ≡ (82 mod 5 ⋅ 21 mod 5) mod 5.

82 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 82 = 80 + 2 = 16 ⋅ 5 + 2 ist.

21 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 21 = 20 + 1 = 4 ⋅ 5 + 1 ist.

Somit gilt:

(82 ⋅ 21) mod 5 ≡ (2 ⋅ 1) mod 5 ≡ 2 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 47864 mod 587.

Lösung einblenden

Die 64 im Exponent ist ja ein reine 2er-Potenz (26).

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. 478 -> x
2. mod(x²,587) -> 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: 4781=478

2: 4782=4781+1=4781⋅4781 ≡ 478⋅478=228484 ≡ 141 mod 587

4: 4784=4782+2=4782⋅4782 ≡ 141⋅141=19881 ≡ 510 mod 587

8: 4788=4784+4=4784⋅4784 ≡ 510⋅510=260100 ≡ 59 mod 587

16: 47816=4788+8=4788⋅4788 ≡ 59⋅59=3481 ≡ 546 mod 587

32: 47832=47816+16=47816⋅47816 ≡ 546⋅546=298116 ≡ 507 mod 587

64: 47864=47832+32=47832⋅47832 ≡ 507⋅507=257049 ≡ 530 mod 587

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 420100 mod 809.

Lösung einblenden

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

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

100 = 64+32+4

1: 4201=420

2: 4202=4201+1=4201⋅4201 ≡ 420⋅420=176400 ≡ 38 mod 809

4: 4204=4202+2=4202⋅4202 ≡ 38⋅38=1444 ≡ 635 mod 809

8: 4208=4204+4=4204⋅4204 ≡ 635⋅635=403225 ≡ 343 mod 809

16: 42016=4208+8=4208⋅4208 ≡ 343⋅343=117649 ≡ 344 mod 809

32: 42032=42016+16=42016⋅42016 ≡ 344⋅344=118336 ≡ 222 mod 809

64: 42064=42032+32=42032⋅42032 ≡ 222⋅222=49284 ≡ 744 mod 809

420100

= 42064+32+4

= 42064⋅42032⋅4204

744 ⋅ 222 ⋅ 635 mod 809
165168 ⋅ 635 mod 809 ≡ 132 ⋅ 635 mod 809
83820 mod 809 ≡ 493 mod 809

Es gilt also: 420100 ≡ 493 mod 809

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>71 = 1⋅53 + 18
=>53 = 2⋅18 + 17
=>18 = 1⋅17 + 1
=>17 = 17⋅1 + 0

also gilt: ggt(71,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= 18-1⋅17
17= 53-2⋅18 eingesetzt in die Zeile drüber: 1 = 1⋅18 -1⋅(53 -2⋅ 18)
= 1⋅18 -1⋅53 +2⋅ 18)
= -1⋅53 +3⋅ 18 (=1)
18= 71-1⋅53 eingesetzt in die Zeile drüber: 1 = -1⋅53 +3⋅(71 -1⋅ 53)
= -1⋅53 +3⋅71 -3⋅ 53)
= 3⋅71 -4⋅ 53 (=1)

Es gilt also: ggt(71,53)=1 = 3⋅71 -4⋅53

oder wenn man 3⋅71 auf die linke Seite bringt:

1 -3⋅71 = -4⋅53

-4⋅53 = -3⋅71 + 1 |+71⋅53

-4⋅53 + 71⋅53 = -3⋅71 + 71⋅53 + 1

(-4 + 71) ⋅ 53 = (-3 + 53) ⋅ 71 + 1

67⋅53 = 50⋅71 + 1

Es gilt also: 67⋅53 = 50⋅71 +1

Somit 67⋅53 = 1 mod 71

67 ist also das Inverse von 53 mod 71

Schlüsselpaar für RSA

Beispiel:

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