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: (238 + 8007) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(238 + 8007) mod 8 ≡ (238 mod 8 + 8007 mod 8) mod 8.

238 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 238 = 240-2 = 8 ⋅ 30 -2 = 8 ⋅ 30 - 8 + 6.

8007 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 8007 = 8000+7 = 8 ⋅ 1000 +7.

Somit gilt:

(238 + 8007) mod 8 ≡ (6 + 7) mod 8 ≡ 13 mod 8 ≡ 5 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (31 ⋅ 69) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 69) mod 10 ≡ (31 mod 10 ⋅ 69 mod 10) mod 10.

31 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 31 = 30 + 1 = 3 ⋅ 10 + 1 ist.

69 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 69 = 60 + 9 = 6 ⋅ 10 + 9 ist.

Somit gilt:

(31 ⋅ 69) mod 10 ≡ (1 ⋅ 9) mod 10 ≡ 9 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 258128 mod 283.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 258 -> x
2. mod(x²,283) -> 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: 2581=258

2: 2582=2581+1=2581⋅2581 ≡ 258⋅258=66564 ≡ 59 mod 283

4: 2584=2582+2=2582⋅2582 ≡ 59⋅59=3481 ≡ 85 mod 283

8: 2588=2584+4=2584⋅2584 ≡ 85⋅85=7225 ≡ 150 mod 283

16: 25816=2588+8=2588⋅2588 ≡ 150⋅150=22500 ≡ 143 mod 283

32: 25832=25816+16=25816⋅25816 ≡ 143⋅143=20449 ≡ 73 mod 283

64: 25864=25832+32=25832⋅25832 ≡ 73⋅73=5329 ≡ 235 mod 283

128: 258128=25864+64=25864⋅25864 ≡ 235⋅235=55225 ≡ 40 mod 283

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 65889 mod 937.

Lösung einblenden

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

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

89 = 64+16+8+1

1: 6581=658

2: 6582=6581+1=6581⋅6581 ≡ 658⋅658=432964 ≡ 70 mod 937

4: 6584=6582+2=6582⋅6582 ≡ 70⋅70=4900 ≡ 215 mod 937

8: 6588=6584+4=6584⋅6584 ≡ 215⋅215=46225 ≡ 312 mod 937

16: 65816=6588+8=6588⋅6588 ≡ 312⋅312=97344 ≡ 833 mod 937

32: 65832=65816+16=65816⋅65816 ≡ 833⋅833=693889 ≡ 509 mod 937

64: 65864=65832+32=65832⋅65832 ≡ 509⋅509=259081 ≡ 469 mod 937

65889

= 65864+16+8+1

= 65864⋅65816⋅6588⋅6581

469 ⋅ 833 ⋅ 312 ⋅ 658 mod 937
390677 ⋅ 312 ⋅ 658 mod 937 ≡ 885 ⋅ 312 ⋅ 658 mod 937
276120 ⋅ 658 mod 937 ≡ 642 ⋅ 658 mod 937
422436 mod 937 ≡ 786 mod 937

Es gilt also: 65889 ≡ 786 mod 937

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>67 = 2⋅23 + 21
=>23 = 1⋅21 + 2
=>21 = 10⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(67,23)=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= 21-10⋅2
2= 23-1⋅21 eingesetzt in die Zeile drüber: 1 = 1⋅21 -10⋅(23 -1⋅ 21)
= 1⋅21 -10⋅23 +10⋅ 21)
= -10⋅23 +11⋅ 21 (=1)
21= 67-2⋅23 eingesetzt in die Zeile drüber: 1 = -10⋅23 +11⋅(67 -2⋅ 23)
= -10⋅23 +11⋅67 -22⋅ 23)
= 11⋅67 -32⋅ 23 (=1)

Es gilt also: ggt(67,23)=1 = 11⋅67 -32⋅23

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

1 -11⋅67 = -32⋅23

-32⋅23 = -11⋅67 + 1 |+67⋅23

-32⋅23 + 67⋅23 = -11⋅67 + 67⋅23 + 1

(-32 + 67) ⋅ 23 = (-11 + 23) ⋅ 67 + 1

35⋅23 = 12⋅67 + 1

Es gilt also: 35⋅23 = 12⋅67 +1

Somit 35⋅23 = 1 mod 67

35 ist also das Inverse von 23 mod 67

Schlüsselpaar für RSA

Beispiel:

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