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: (6003 + 150) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(6003 + 150) mod 3 ≡ (6003 mod 3 + 150 mod 3) mod 3.

6003 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 6003 = 6000+3 = 3 ⋅ 2000 +3.

150 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 150 = 150+0 = 3 ⋅ 50 +0.

Somit gilt:

(6003 + 150) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (96 ⋅ 82) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(96 ⋅ 82) mod 3 ≡ (96 mod 3 ⋅ 82 mod 3) mod 3.

96 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 96 = 96 + 0 = 32 ⋅ 3 + 0 ist.

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

Somit gilt:

(96 ⋅ 82) mod 3 ≡ (0 ⋅ 1) mod 3 ≡ 0 mod 3.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 78632 mod 929.

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. 786 -> x
2. mod(x²,929) -> 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: 7861=786

2: 7862=7861+1=7861⋅7861 ≡ 786⋅786=617796 ≡ 11 mod 929

4: 7864=7862+2=7862⋅7862 ≡ 11⋅11=121 ≡ 121 mod 929

8: 7868=7864+4=7864⋅7864 ≡ 121⋅121=14641 ≡ 706 mod 929

16: 78616=7868+8=7868⋅7868 ≡ 706⋅706=498436 ≡ 492 mod 929

32: 78632=78616+16=78616⋅78616 ≡ 492⋅492=242064 ≡ 524 mod 929

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 376189 mod 641.

Lösung einblenden

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

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

189 = 128+32+16+8+4+1

1: 3761=376

2: 3762=3761+1=3761⋅3761 ≡ 376⋅376=141376 ≡ 356 mod 641

4: 3764=3762+2=3762⋅3762 ≡ 356⋅356=126736 ≡ 459 mod 641

8: 3768=3764+4=3764⋅3764 ≡ 459⋅459=210681 ≡ 433 mod 641

16: 37616=3768+8=3768⋅3768 ≡ 433⋅433=187489 ≡ 317 mod 641

32: 37632=37616+16=37616⋅37616 ≡ 317⋅317=100489 ≡ 493 mod 641

64: 37664=37632+32=37632⋅37632 ≡ 493⋅493=243049 ≡ 110 mod 641

128: 376128=37664+64=37664⋅37664 ≡ 110⋅110=12100 ≡ 562 mod 641

376189

= 376128+32+16+8+4+1

= 376128⋅37632⋅37616⋅3768⋅3764⋅3761

562 ⋅ 493 ⋅ 317 ⋅ 433 ⋅ 459 ⋅ 376 mod 641
277066 ⋅ 317 ⋅ 433 ⋅ 459 ⋅ 376 mod 641 ≡ 154 ⋅ 317 ⋅ 433 ⋅ 459 ⋅ 376 mod 641
48818 ⋅ 433 ⋅ 459 ⋅ 376 mod 641 ≡ 102 ⋅ 433 ⋅ 459 ⋅ 376 mod 641
44166 ⋅ 459 ⋅ 376 mod 641 ≡ 578 ⋅ 459 ⋅ 376 mod 641
265302 ⋅ 376 mod 641 ≡ 569 ⋅ 376 mod 641
213944 mod 641 ≡ 491 mod 641

Es gilt also: 376189 ≡ 491 mod 641

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 2⋅36 + 29
=>36 = 1⋅29 + 7
=>29 = 4⋅7 + 1
=>7 = 7⋅1 + 0

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

Es gilt also: ggt(101,36)=1 = 5⋅101 -14⋅36

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

1 -5⋅101 = -14⋅36

-14⋅36 = -5⋅101 + 1 |+101⋅36

-14⋅36 + 101⋅36 = -5⋅101 + 101⋅36 + 1

(-14 + 101) ⋅ 36 = (-5 + 36) ⋅ 101 + 1

87⋅36 = 31⋅101 + 1

Es gilt also: 87⋅36 = 31⋅101 +1

Somit 87⋅36 = 1 mod 101

87 ist also das Inverse von 36 mod 101

Schlüsselpaar für RSA

Beispiel:

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