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: (903 - 1502) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(903 - 1502) mod 3 ≡ (903 mod 3 - 1502 mod 3) mod 3.

903 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 903 = 900+3 = 3 ⋅ 300 +3.

1502 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1502 = 1500+2 = 3 ⋅ 500 +2.

Somit gilt:

(903 - 1502) mod 3 ≡ (0 - 2) mod 3 ≡ -2 mod 3 ≡ 1 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (35 ⋅ 53) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(35 ⋅ 53) mod 11 ≡ (35 mod 11 ⋅ 53 mod 11) mod 11.

35 mod 11 ≡ 2 mod 11 kann man relativ leicht bestimmen, weil ja 35 = 33 + 2 = 3 ⋅ 11 + 2 ist.

53 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 53 = 44 + 9 = 4 ⋅ 11 + 9 ist.

Somit gilt:

(35 ⋅ 53) mod 11 ≡ (2 ⋅ 9) mod 11 ≡ 18 mod 11 ≡ 7 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 67464 mod 691.

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. 674 -> x
2. mod(x²,691) -> 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: 6741=674

2: 6742=6741+1=6741⋅6741 ≡ 674⋅674=454276 ≡ 289 mod 691

4: 6744=6742+2=6742⋅6742 ≡ 289⋅289=83521 ≡ 601 mod 691

8: 6748=6744+4=6744⋅6744 ≡ 601⋅601=361201 ≡ 499 mod 691

16: 67416=6748+8=6748⋅6748 ≡ 499⋅499=249001 ≡ 241 mod 691

32: 67432=67416+16=67416⋅67416 ≡ 241⋅241=58081 ≡ 37 mod 691

64: 67464=67432+32=67432⋅67432 ≡ 37⋅37=1369 ≡ 678 mod 691

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 427146 mod 643.

Lösung einblenden

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

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

146 = 128+16+2

1: 4271=427

2: 4272=4271+1=4271⋅4271 ≡ 427⋅427=182329 ≡ 360 mod 643

4: 4274=4272+2=4272⋅4272 ≡ 360⋅360=129600 ≡ 357 mod 643

8: 4278=4274+4=4274⋅4274 ≡ 357⋅357=127449 ≡ 135 mod 643

16: 42716=4278+8=4278⋅4278 ≡ 135⋅135=18225 ≡ 221 mod 643

32: 42732=42716+16=42716⋅42716 ≡ 221⋅221=48841 ≡ 616 mod 643

64: 42764=42732+32=42732⋅42732 ≡ 616⋅616=379456 ≡ 86 mod 643

128: 427128=42764+64=42764⋅42764 ≡ 86⋅86=7396 ≡ 323 mod 643

427146

= 427128+16+2

= 427128⋅42716⋅4272

323 ⋅ 221 ⋅ 360 mod 643
71383 ⋅ 360 mod 643 ≡ 10 ⋅ 360 mod 643
3600 mod 643 ≡ 385 mod 643

Es gilt also: 427146 ≡ 385 mod 643

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 25

=>67 = 2⋅25 + 17
=>25 = 1⋅17 + 8
=>17 = 2⋅8 + 1
=>8 = 8⋅1 + 0

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

Es gilt also: ggt(67,25)=1 = 3⋅67 -8⋅25

oder wenn man 3⋅67 auf die linke Seite bringt:

1 -3⋅67 = -8⋅25

-8⋅25 = -3⋅67 + 1 |+67⋅25

-8⋅25 + 67⋅25 = -3⋅67 + 67⋅25 + 1

(-8 + 67) ⋅ 25 = (-3 + 25) ⋅ 67 + 1

59⋅25 = 22⋅67 + 1

Es gilt also: 59⋅25 = 22⋅67 +1

Somit 59⋅25 = 1 mod 67

59 ist also das Inverse von 25 mod 67

Schlüsselpaar für RSA

Beispiel:

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