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: (2402 + 12004) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2402 + 12004) mod 6 ≡ (2402 mod 6 + 12004 mod 6) mod 6.

2402 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 2402 = 2400+2 = 6 ⋅ 400 +2.

12004 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 12004 = 12000+4 = 6 ⋅ 2000 +4.

Somit gilt:

(2402 + 12004) mod 6 ≡ (2 + 4) mod 6 ≡ 6 mod 6 ≡ 0 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (71 ⋅ 36) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(71 ⋅ 36) mod 10 ≡ (71 mod 10 ⋅ 36 mod 10) mod 10.

71 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 71 = 70 + 1 = 7 ⋅ 10 + 1 ist.

36 mod 10 ≡ 6 mod 10 kann man relativ leicht bestimmen, weil ja 36 = 30 + 6 = 3 ⋅ 10 + 6 ist.

Somit gilt:

(71 ⋅ 36) mod 10 ≡ (1 ⋅ 6) mod 10 ≡ 6 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 34732 mod 409.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 347 -> x
2. mod(x²,409) -> 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: 3471=347

2: 3472=3471+1=3471⋅3471 ≡ 347⋅347=120409 ≡ 163 mod 409

4: 3474=3472+2=3472⋅3472 ≡ 163⋅163=26569 ≡ 393 mod 409

8: 3478=3474+4=3474⋅3474 ≡ 393⋅393=154449 ≡ 256 mod 409

16: 34716=3478+8=3478⋅3478 ≡ 256⋅256=65536 ≡ 96 mod 409

32: 34732=34716+16=34716⋅34716 ≡ 96⋅96=9216 ≡ 218 mod 409

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 217213 mod 431.

Lösung einblenden

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

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

213 = 128+64+16+4+1

1: 2171=217

2: 2172=2171+1=2171⋅2171 ≡ 217⋅217=47089 ≡ 110 mod 431

4: 2174=2172+2=2172⋅2172 ≡ 110⋅110=12100 ≡ 32 mod 431

8: 2178=2174+4=2174⋅2174 ≡ 32⋅32=1024 ≡ 162 mod 431

16: 21716=2178+8=2178⋅2178 ≡ 162⋅162=26244 ≡ 384 mod 431

32: 21732=21716+16=21716⋅21716 ≡ 384⋅384=147456 ≡ 54 mod 431

64: 21764=21732+32=21732⋅21732 ≡ 54⋅54=2916 ≡ 330 mod 431

128: 217128=21764+64=21764⋅21764 ≡ 330⋅330=108900 ≡ 288 mod 431

217213

= 217128+64+16+4+1

= 217128⋅21764⋅21716⋅2174⋅2171

288 ⋅ 330 ⋅ 384 ⋅ 32 ⋅ 217 mod 431
95040 ⋅ 384 ⋅ 32 ⋅ 217 mod 431 ≡ 220 ⋅ 384 ⋅ 32 ⋅ 217 mod 431
84480 ⋅ 32 ⋅ 217 mod 431 ≡ 4 ⋅ 32 ⋅ 217 mod 431
128 ⋅ 217 mod 431
27776 mod 431 ≡ 192 mod 431

Es gilt also: 217213 ≡ 192 mod 431

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 43 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 43

=>73 = 1⋅43 + 30
=>43 = 1⋅30 + 13
=>30 = 2⋅13 + 4
=>13 = 3⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(73,43)=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= 13-3⋅4
4= 30-2⋅13 eingesetzt in die Zeile drüber: 1 = 1⋅13 -3⋅(30 -2⋅ 13)
= 1⋅13 -3⋅30 +6⋅ 13)
= -3⋅30 +7⋅ 13 (=1)
13= 43-1⋅30 eingesetzt in die Zeile drüber: 1 = -3⋅30 +7⋅(43 -1⋅ 30)
= -3⋅30 +7⋅43 -7⋅ 30)
= 7⋅43 -10⋅ 30 (=1)
30= 73-1⋅43 eingesetzt in die Zeile drüber: 1 = 7⋅43 -10⋅(73 -1⋅ 43)
= 7⋅43 -10⋅73 +10⋅ 43)
= -10⋅73 +17⋅ 43 (=1)

Es gilt also: ggt(73,43)=1 = -10⋅73 +17⋅43

oder wenn man -10⋅73 auf die linke Seite bringt:

1 +10⋅73 = +17⋅43

Es gilt also: 17⋅43 = 10⋅73 +1

Somit 17⋅43 = 1 mod 73

17 ist also das Inverse von 43 mod 73

Schlüsselpaar für RSA

Beispiel:

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