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: (3505 - 64) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3505 - 64) mod 7 ≡ (3505 mod 7 - 64 mod 7) mod 7.

3505 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 3505 = 3500+5 = 7 ⋅ 500 +5.

64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 70-6 = 7 ⋅ 10 -6 = 7 ⋅ 10 - 7 + 1.

Somit gilt:

(3505 - 64) mod 7 ≡ (5 - 1) mod 7 ≡ 4 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (15 ⋅ 52) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 52) mod 10 ≡ (15 mod 10 ⋅ 52 mod 10) mod 10.

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

52 mod 10 ≡ 2 mod 10 kann man relativ leicht bestimmen, weil ja 52 = 50 + 2 = 5 ⋅ 10 + 2 ist.

Somit gilt:

(15 ⋅ 52) mod 10 ≡ (5 ⋅ 2) mod 10 ≡ 10 mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 18616 mod 293.

Lösung einblenden

Die 16 im Exponent ist ja ein reine 2er-Potenz (24).

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. 186 -> x
2. mod(x²,293) -> 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: 1861=186

2: 1862=1861+1=1861⋅1861 ≡ 186⋅186=34596 ≡ 22 mod 293

4: 1864=1862+2=1862⋅1862 ≡ 22⋅22=484 ≡ 191 mod 293

8: 1868=1864+4=1864⋅1864 ≡ 191⋅191=36481 ≡ 149 mod 293

16: 18616=1868+8=1868⋅1868 ≡ 149⋅149=22201 ≡ 226 mod 293

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 21763 mod 653.

Lösung einblenden

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

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

63 = 32+16+8+4+2+1

1: 2171=217

2: 2172=2171+1=2171⋅2171 ≡ 217⋅217=47089 ≡ 73 mod 653

4: 2174=2172+2=2172⋅2172 ≡ 73⋅73=5329 ≡ 105 mod 653

8: 2178=2174+4=2174⋅2174 ≡ 105⋅105=11025 ≡ 577 mod 653

16: 21716=2178+8=2178⋅2178 ≡ 577⋅577=332929 ≡ 552 mod 653

32: 21732=21716+16=21716⋅21716 ≡ 552⋅552=304704 ≡ 406 mod 653

21763

= 21732+16+8+4+2+1

= 21732⋅21716⋅2178⋅2174⋅2172⋅2171

406 ⋅ 552 ⋅ 577 ⋅ 105 ⋅ 73 ⋅ 217 mod 653
224112 ⋅ 577 ⋅ 105 ⋅ 73 ⋅ 217 mod 653 ≡ 133 ⋅ 577 ⋅ 105 ⋅ 73 ⋅ 217 mod 653
76741 ⋅ 105 ⋅ 73 ⋅ 217 mod 653 ≡ 340 ⋅ 105 ⋅ 73 ⋅ 217 mod 653
35700 ⋅ 73 ⋅ 217 mod 653 ≡ 438 ⋅ 73 ⋅ 217 mod 653
31974 ⋅ 217 mod 653 ≡ 630 ⋅ 217 mod 653
136710 mod 653 ≡ 233 mod 653

Es gilt also: 21763 ≡ 233 mod 653

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 = 71 und q = 89. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.