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: (24006 - 18003) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(24006 - 18003) mod 6 ≡ (24006 mod 6 - 18003 mod 6) mod 6.

24006 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 24006 = 24000+6 = 6 ⋅ 4000 +6.

18003 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 18003 = 18000+3 = 6 ⋅ 3000 +3.

Somit gilt:

(24006 - 18003) mod 6 ≡ (0 - 3) mod 6 ≡ -3 mod 6 ≡ 3 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (65 ⋅ 82) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(65 ⋅ 82) mod 9 ≡ (65 mod 9 ⋅ 82 mod 9) mod 9.

65 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 7 ⋅ 9 + 2 ist.

82 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 82 = 81 + 1 = 9 ⋅ 9 + 1 ist.

Somit gilt:

(65 ⋅ 82) mod 9 ≡ (2 ⋅ 1) mod 9 ≡ 2 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 63132 mod 719.

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. 631 -> x
2. mod(x²,719) -> 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: 6311=631

2: 6312=6311+1=6311⋅6311 ≡ 631⋅631=398161 ≡ 554 mod 719

4: 6314=6312+2=6312⋅6312 ≡ 554⋅554=306916 ≡ 622 mod 719

8: 6318=6314+4=6314⋅6314 ≡ 622⋅622=386884 ≡ 62 mod 719

16: 63116=6318+8=6318⋅6318 ≡ 62⋅62=3844 ≡ 249 mod 719

32: 63132=63116+16=63116⋅63116 ≡ 249⋅249=62001 ≡ 167 mod 719

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 139203 mod 397.

Lösung einblenden

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

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

203 = 128+64+8+2+1

1: 1391=139

2: 1392=1391+1=1391⋅1391 ≡ 139⋅139=19321 ≡ 265 mod 397

4: 1394=1392+2=1392⋅1392 ≡ 265⋅265=70225 ≡ 353 mod 397

8: 1398=1394+4=1394⋅1394 ≡ 353⋅353=124609 ≡ 348 mod 397

16: 13916=1398+8=1398⋅1398 ≡ 348⋅348=121104 ≡ 19 mod 397

32: 13932=13916+16=13916⋅13916 ≡ 19⋅19=361 ≡ 361 mod 397

64: 13964=13932+32=13932⋅13932 ≡ 361⋅361=130321 ≡ 105 mod 397

128: 139128=13964+64=13964⋅13964 ≡ 105⋅105=11025 ≡ 306 mod 397

139203

= 139128+64+8+2+1

= 139128⋅13964⋅1398⋅1392⋅1391

306 ⋅ 105 ⋅ 348 ⋅ 265 ⋅ 139 mod 397
32130 ⋅ 348 ⋅ 265 ⋅ 139 mod 397 ≡ 370 ⋅ 348 ⋅ 265 ⋅ 139 mod 397
128760 ⋅ 265 ⋅ 139 mod 397 ≡ 132 ⋅ 265 ⋅ 139 mod 397
34980 ⋅ 139 mod 397 ≡ 44 ⋅ 139 mod 397
6116 mod 397 ≡ 161 mod 397

Es gilt also: 139203 ≡ 161 mod 397

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 42 ⋅ x ≡ 1 mod 101 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 101 und 42

=>101 = 2⋅42 + 17
=>42 = 2⋅17 + 8
=>17 = 2⋅8 + 1
=>8 = 8⋅1 + 0

also gilt: ggt(101,42)=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= 17-2⋅8
8= 42-2⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -2⋅(42 -2⋅ 17)
= 1⋅17 -2⋅42 +4⋅ 17)
= -2⋅42 +5⋅ 17 (=1)
17= 101-2⋅42 eingesetzt in die Zeile drüber: 1 = -2⋅42 +5⋅(101 -2⋅ 42)
= -2⋅42 +5⋅101 -10⋅ 42)
= 5⋅101 -12⋅ 42 (=1)

Es gilt also: ggt(101,42)=1 = 5⋅101 -12⋅42

oder wenn man 5⋅101 auf die linke Seite bringt:

1 -5⋅101 = -12⋅42

-12⋅42 = -5⋅101 + 1 |+101⋅42

-12⋅42 + 101⋅42 = -5⋅101 + 101⋅42 + 1

(-12 + 101) ⋅ 42 = (-5 + 42) ⋅ 101 + 1

89⋅42 = 37⋅101 + 1

Es gilt also: 89⋅42 = 37⋅101 +1

Somit 89⋅42 = 1 mod 101

89 ist also das Inverse von 42 mod 101

Schlüsselpaar für RSA

Beispiel:

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