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: (39992 + 23992) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(39992 + 23992) mod 8 ≡ (39992 mod 8 + 23992 mod 8) mod 8.

39992 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 39992 = 39000+992 = 8 ⋅ 4875 +992.

23992 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 23992 = 23000+992 = 8 ⋅ 2875 +992.

Somit gilt:

(39992 + 23992) mod 8 ≡ (0 + 0) mod 8 ≡ 0 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (16 ⋅ 55) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(16 ⋅ 55) mod 4 ≡ (16 mod 4 ⋅ 55 mod 4) mod 4.

16 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 16 = 16 + 0 = 4 ⋅ 4 + 0 ist.

55 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 55 = 52 + 3 = 13 ⋅ 4 + 3 ist.

Somit gilt:

(16 ⋅ 55) mod 4 ≡ (0 ⋅ 3) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 19664 mod 541.

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. 196 -> x
2. mod(x²,541) -> 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: 1961=196

2: 1962=1961+1=1961⋅1961 ≡ 196⋅196=38416 ≡ 5 mod 541

4: 1964=1962+2=1962⋅1962 ≡ 5⋅5=25 ≡ 25 mod 541

8: 1968=1964+4=1964⋅1964 ≡ 25⋅25=625 ≡ 84 mod 541

16: 19616=1968+8=1968⋅1968 ≡ 84⋅84=7056 ≡ 23 mod 541

32: 19632=19616+16=19616⋅19616 ≡ 23⋅23=529 ≡ 529 mod 541

64: 19664=19632+32=19632⋅19632 ≡ 529⋅529=279841 ≡ 144 mod 541

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 685217 mod 757.

Lösung einblenden

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

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

217 = 128+64+16+8+1

1: 6851=685

2: 6852=6851+1=6851⋅6851 ≡ 685⋅685=469225 ≡ 642 mod 757

4: 6854=6852+2=6852⋅6852 ≡ 642⋅642=412164 ≡ 356 mod 757

8: 6858=6854+4=6854⋅6854 ≡ 356⋅356=126736 ≡ 317 mod 757

16: 68516=6858+8=6858⋅6858 ≡ 317⋅317=100489 ≡ 565 mod 757

32: 68532=68516+16=68516⋅68516 ≡ 565⋅565=319225 ≡ 528 mod 757

64: 68564=68532+32=68532⋅68532 ≡ 528⋅528=278784 ≡ 208 mod 757

128: 685128=68564+64=68564⋅68564 ≡ 208⋅208=43264 ≡ 115 mod 757

685217

= 685128+64+16+8+1

= 685128⋅68564⋅68516⋅6858⋅6851

115 ⋅ 208 ⋅ 565 ⋅ 317 ⋅ 685 mod 757
23920 ⋅ 565 ⋅ 317 ⋅ 685 mod 757 ≡ 453 ⋅ 565 ⋅ 317 ⋅ 685 mod 757
255945 ⋅ 317 ⋅ 685 mod 757 ≡ 79 ⋅ 317 ⋅ 685 mod 757
25043 ⋅ 685 mod 757 ≡ 62 ⋅ 685 mod 757
42470 mod 757 ≡ 78 mod 757

Es gilt also: 685217 ≡ 78 mod 757

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 28 ⋅ x ≡ 1 mod 53 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 53 und 28

=>53 = 1⋅28 + 25
=>28 = 1⋅25 + 3
=>25 = 8⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(53,28)=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= 25-8⋅3
3= 28-1⋅25 eingesetzt in die Zeile drüber: 1 = 1⋅25 -8⋅(28 -1⋅ 25)
= 1⋅25 -8⋅28 +8⋅ 25)
= -8⋅28 +9⋅ 25 (=1)
25= 53-1⋅28 eingesetzt in die Zeile drüber: 1 = -8⋅28 +9⋅(53 -1⋅ 28)
= -8⋅28 +9⋅53 -9⋅ 28)
= 9⋅53 -17⋅ 28 (=1)

Es gilt also: ggt(53,28)=1 = 9⋅53 -17⋅28

oder wenn man 9⋅53 auf die linke Seite bringt:

1 -9⋅53 = -17⋅28

-17⋅28 = -9⋅53 + 1 |+53⋅28

-17⋅28 + 53⋅28 = -9⋅53 + 53⋅28 + 1

(-17 + 53) ⋅ 28 = (-9 + 28) ⋅ 53 + 1

36⋅28 = 19⋅53 + 1

Es gilt also: 36⋅28 = 19⋅53 +1

Somit 36⋅28 = 1 mod 53

36 ist also das Inverse von 28 mod 53

Schlüsselpaar für RSA

Beispiel:

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