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: (2399 + 30000) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2399 + 30000) mod 6 ≡ (2399 mod 6 + 30000 mod 6) mod 6.

2399 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 2399 = 2400-1 = 6 ⋅ 400 -1 = 6 ⋅ 400 - 6 + 5.

30000 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 30000 = 30000+0 = 6 ⋅ 5000 +0.

Somit gilt:

(2399 + 30000) mod 6 ≡ (5 + 0) mod 6 ≡ 5 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (26 ⋅ 35) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(26 ⋅ 35) mod 4 ≡ (26 mod 4 ⋅ 35 mod 4) mod 4.

26 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 26 = 24 + 2 = 6 ⋅ 4 + 2 ist.

35 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 35 = 32 + 3 = 8 ⋅ 4 + 3 ist.

Somit gilt:

(26 ⋅ 35) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 721128 mod 839.

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. 721 -> x
2. mod(x²,839) -> 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: 7211=721

2: 7212=7211+1=7211⋅7211 ≡ 721⋅721=519841 ≡ 500 mod 839

4: 7214=7212+2=7212⋅7212 ≡ 500⋅500=250000 ≡ 817 mod 839

8: 7218=7214+4=7214⋅7214 ≡ 817⋅817=667489 ≡ 484 mod 839

16: 72116=7218+8=7218⋅7218 ≡ 484⋅484=234256 ≡ 175 mod 839

32: 72132=72116+16=72116⋅72116 ≡ 175⋅175=30625 ≡ 421 mod 839

64: 72164=72132+32=72132⋅72132 ≡ 421⋅421=177241 ≡ 212 mod 839

128: 721128=72164+64=72164⋅72164 ≡ 212⋅212=44944 ≡ 477 mod 839

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 204124 mod 227.

Lösung einblenden

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

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

124 = 64+32+16+8+4

1: 2041=204

2: 2042=2041+1=2041⋅2041 ≡ 204⋅204=41616 ≡ 75 mod 227

4: 2044=2042+2=2042⋅2042 ≡ 75⋅75=5625 ≡ 177 mod 227

8: 2048=2044+4=2044⋅2044 ≡ 177⋅177=31329 ≡ 3 mod 227

16: 20416=2048+8=2048⋅2048 ≡ 3⋅3=9 ≡ 9 mod 227

32: 20432=20416+16=20416⋅20416 ≡ 9⋅9=81 ≡ 81 mod 227

64: 20464=20432+32=20432⋅20432 ≡ 81⋅81=6561 ≡ 205 mod 227

204124

= 20464+32+16+8+4

= 20464⋅20432⋅20416⋅2048⋅2044

205 ⋅ 81 ⋅ 9 ⋅ 3 ⋅ 177 mod 227
16605 ⋅ 9 ⋅ 3 ⋅ 177 mod 227 ≡ 34 ⋅ 9 ⋅ 3 ⋅ 177 mod 227
306 ⋅ 3 ⋅ 177 mod 227 ≡ 79 ⋅ 3 ⋅ 177 mod 227
237 ⋅ 177 mod 227 ≡ 10 ⋅ 177 mod 227
1770 mod 227 ≡ 181 mod 227

Es gilt also: 204124 ≡ 181 mod 227

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>89 = 1⋅48 + 41
=>48 = 1⋅41 + 7
=>41 = 5⋅7 + 6
=>7 = 1⋅6 + 1
=>6 = 6⋅1 + 0

also gilt: ggt(89,48)=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= 7-1⋅6
6= 41-5⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -1⋅(41 -5⋅ 7)
= 1⋅7 -1⋅41 +5⋅ 7)
= -1⋅41 +6⋅ 7 (=1)
7= 48-1⋅41 eingesetzt in die Zeile drüber: 1 = -1⋅41 +6⋅(48 -1⋅ 41)
= -1⋅41 +6⋅48 -6⋅ 41)
= 6⋅48 -7⋅ 41 (=1)
41= 89-1⋅48 eingesetzt in die Zeile drüber: 1 = 6⋅48 -7⋅(89 -1⋅ 48)
= 6⋅48 -7⋅89 +7⋅ 48)
= -7⋅89 +13⋅ 48 (=1)

Es gilt also: ggt(89,48)=1 = -7⋅89 +13⋅48

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

1 +7⋅89 = +13⋅48

Es gilt also: 13⋅48 = 7⋅89 +1

Somit 13⋅48 = 1 mod 89

13 ist also das Inverse von 48 mod 89

Schlüsselpaar für RSA

Beispiel:

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