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: (4998 + 2500) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(4998 + 2500) mod 5 ≡ (4998 mod 5 + 2500 mod 5) mod 5.

4998 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 4998 = 4000+998 = 5 ⋅ 800 +998.

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

Somit gilt:

(4998 + 2500) mod 5 ≡ (3 + 0) mod 5 ≡ 3 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (24 ⋅ 28) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(24 ⋅ 28) mod 4 ≡ (24 mod 4 ⋅ 28 mod 4) mod 4.

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

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

Somit gilt:

(24 ⋅ 28) mod 4 ≡ (0 ⋅ 0) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 458128 mod 593.

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. 458 -> x
2. mod(x²,593) -> 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: 4581=458

2: 4582=4581+1=4581⋅4581 ≡ 458⋅458=209764 ≡ 435 mod 593

4: 4584=4582+2=4582⋅4582 ≡ 435⋅435=189225 ≡ 58 mod 593

8: 4588=4584+4=4584⋅4584 ≡ 58⋅58=3364 ≡ 399 mod 593

16: 45816=4588+8=4588⋅4588 ≡ 399⋅399=159201 ≡ 277 mod 593

32: 45832=45816+16=45816⋅45816 ≡ 277⋅277=76729 ≡ 232 mod 593

64: 45864=45832+32=45832⋅45832 ≡ 232⋅232=53824 ≡ 454 mod 593

128: 458128=45864+64=45864⋅45864 ≡ 454⋅454=206116 ≡ 345 mod 593

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 666122 mod 839.

Lösung einblenden

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

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

122 = 64+32+16+8+2

1: 6661=666

2: 6662=6661+1=6661⋅6661 ≡ 666⋅666=443556 ≡ 564 mod 839

4: 6664=6662+2=6662⋅6662 ≡ 564⋅564=318096 ≡ 115 mod 839

8: 6668=6664+4=6664⋅6664 ≡ 115⋅115=13225 ≡ 640 mod 839

16: 66616=6668+8=6668⋅6668 ≡ 640⋅640=409600 ≡ 168 mod 839

32: 66632=66616+16=66616⋅66616 ≡ 168⋅168=28224 ≡ 537 mod 839

64: 66664=66632+32=66632⋅66632 ≡ 537⋅537=288369 ≡ 592 mod 839

666122

= 66664+32+16+8+2

= 66664⋅66632⋅66616⋅6668⋅6662

592 ⋅ 537 ⋅ 168 ⋅ 640 ⋅ 564 mod 839
317904 ⋅ 168 ⋅ 640 ⋅ 564 mod 839 ≡ 762 ⋅ 168 ⋅ 640 ⋅ 564 mod 839
128016 ⋅ 640 ⋅ 564 mod 839 ≡ 488 ⋅ 640 ⋅ 564 mod 839
312320 ⋅ 564 mod 839 ≡ 212 ⋅ 564 mod 839
119568 mod 839 ≡ 430 mod 839

Es gilt also: 666122 ≡ 430 mod 839

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 37 ⋅ x ≡ 1 mod 71 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 71 und 37

=>71 = 1⋅37 + 34
=>37 = 1⋅34 + 3
=>34 = 11⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(71,37)=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= 34-11⋅3
3= 37-1⋅34 eingesetzt in die Zeile drüber: 1 = 1⋅34 -11⋅(37 -1⋅ 34)
= 1⋅34 -11⋅37 +11⋅ 34)
= -11⋅37 +12⋅ 34 (=1)
34= 71-1⋅37 eingesetzt in die Zeile drüber: 1 = -11⋅37 +12⋅(71 -1⋅ 37)
= -11⋅37 +12⋅71 -12⋅ 37)
= 12⋅71 -23⋅ 37 (=1)

Es gilt also: ggt(71,37)=1 = 12⋅71 -23⋅37

oder wenn man 12⋅71 auf die linke Seite bringt:

1 -12⋅71 = -23⋅37

-23⋅37 = -12⋅71 + 1 |+71⋅37

-23⋅37 + 71⋅37 = -12⋅71 + 71⋅37 + 1

(-23 + 71) ⋅ 37 = (-12 + 37) ⋅ 71 + 1

48⋅37 = 25⋅71 + 1

Es gilt also: 48⋅37 = 25⋅71 +1

Somit 48⋅37 = 1 mod 71

48 ist also das Inverse von 37 mod 71

Schlüsselpaar für RSA

Beispiel:

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