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: (1500 - 20004) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1500 - 20004) mod 5 ≡ (1500 mod 5 - 20004 mod 5) mod 5.

1500 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 1500 = 1500+0 = 5 ⋅ 300 +0.

20004 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 20004 = 20000+4 = 5 ⋅ 4000 +4.

Somit gilt:

(1500 - 20004) mod 5 ≡ (0 - 4) mod 5 ≡ -4 mod 5 ≡ 1 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (55 ⋅ 56) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(55 ⋅ 56) mod 10 ≡ (55 mod 10 ⋅ 56 mod 10) mod 10.

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

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

Somit gilt:

(55 ⋅ 56) mod 10 ≡ (5 ⋅ 6) mod 10 ≡ 30 mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 42564 mod 827.

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. 425 -> x
2. mod(x²,827) -> 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: 4251=425

2: 4252=4251+1=4251⋅4251 ≡ 425⋅425=180625 ≡ 339 mod 827

4: 4254=4252+2=4252⋅4252 ≡ 339⋅339=114921 ≡ 795 mod 827

8: 4258=4254+4=4254⋅4254 ≡ 795⋅795=632025 ≡ 197 mod 827

16: 42516=4258+8=4258⋅4258 ≡ 197⋅197=38809 ≡ 767 mod 827

32: 42532=42516+16=42516⋅42516 ≡ 767⋅767=588289 ≡ 292 mod 827

64: 42564=42532+32=42532⋅42532 ≡ 292⋅292=85264 ≡ 83 mod 827

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 504106 mod 827.

Lösung einblenden

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

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

106 = 64+32+8+2

1: 5041=504

2: 5042=5041+1=5041⋅5041 ≡ 504⋅504=254016 ≡ 127 mod 827

4: 5044=5042+2=5042⋅5042 ≡ 127⋅127=16129 ≡ 416 mod 827

8: 5048=5044+4=5044⋅5044 ≡ 416⋅416=173056 ≡ 213 mod 827

16: 50416=5048+8=5048⋅5048 ≡ 213⋅213=45369 ≡ 711 mod 827

32: 50432=50416+16=50416⋅50416 ≡ 711⋅711=505521 ≡ 224 mod 827

64: 50464=50432+32=50432⋅50432 ≡ 224⋅224=50176 ≡ 556 mod 827

504106

= 50464+32+8+2

= 50464⋅50432⋅5048⋅5042

556 ⋅ 224 ⋅ 213 ⋅ 127 mod 827
124544 ⋅ 213 ⋅ 127 mod 827 ≡ 494 ⋅ 213 ⋅ 127 mod 827
105222 ⋅ 127 mod 827 ≡ 193 ⋅ 127 mod 827
24511 mod 827 ≡ 528 mod 827

Es gilt also: 504106 ≡ 528 mod 827

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

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

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

Es gilt also: ggt(73,30)=1 = 7⋅73 -17⋅30

oder wenn man 7⋅73 auf die linke Seite bringt:

1 -7⋅73 = -17⋅30

-17⋅30 = -7⋅73 + 1 |+73⋅30

-17⋅30 + 73⋅30 = -7⋅73 + 73⋅30 + 1

(-17 + 73) ⋅ 30 = (-7 + 30) ⋅ 73 + 1

56⋅30 = 23⋅73 + 1

Es gilt also: 56⋅30 = 23⋅73 +1

Somit 56⋅30 = 1 mod 73

56 ist also das Inverse von 30 mod 73

Schlüsselpaar für RSA

Beispiel:

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