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: (24004 + 24006) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(24004 + 24006) mod 8 ≡ (24004 mod 8 + 24006 mod 8) mod 8.

24004 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 24004 = 24000+4 = 8 ⋅ 3000 +4.

24006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 24006 = 24000+6 = 8 ⋅ 3000 +6.

Somit gilt:

(24004 + 24006) mod 8 ≡ (4 + 6) mod 8 ≡ 10 mod 8 ≡ 2 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (15 ⋅ 54) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(15 ⋅ 54) mod 5 ≡ (15 mod 5 ⋅ 54 mod 5) mod 5.

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

54 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 54 = 50 + 4 = 10 ⋅ 5 + 4 ist.

Somit gilt:

(15 ⋅ 54) mod 5 ≡ (0 ⋅ 4) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 358128 mod 577.

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. 358 -> x
2. mod(x²,577) -> 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: 3581=358

2: 3582=3581+1=3581⋅3581 ≡ 358⋅358=128164 ≡ 70 mod 577

4: 3584=3582+2=3582⋅3582 ≡ 70⋅70=4900 ≡ 284 mod 577

8: 3588=3584+4=3584⋅3584 ≡ 284⋅284=80656 ≡ 453 mod 577

16: 35816=3588+8=3588⋅3588 ≡ 453⋅453=205209 ≡ 374 mod 577

32: 35832=35816+16=35816⋅35816 ≡ 374⋅374=139876 ≡ 242 mod 577

64: 35864=35832+32=35832⋅35832 ≡ 242⋅242=58564 ≡ 287 mod 577

128: 358128=35864+64=35864⋅35864 ≡ 287⋅287=82369 ≡ 435 mod 577

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 679212 mod 691.

Lösung einblenden

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

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

212 = 128+64+16+4

1: 6791=679

2: 6792=6791+1=6791⋅6791 ≡ 679⋅679=461041 ≡ 144 mod 691

4: 6794=6792+2=6792⋅6792 ≡ 144⋅144=20736 ≡ 6 mod 691

8: 6798=6794+4=6794⋅6794 ≡ 6⋅6=36 ≡ 36 mod 691

16: 67916=6798+8=6798⋅6798 ≡ 36⋅36=1296 ≡ 605 mod 691

32: 67932=67916+16=67916⋅67916 ≡ 605⋅605=366025 ≡ 486 mod 691

64: 67964=67932+32=67932⋅67932 ≡ 486⋅486=236196 ≡ 565 mod 691

128: 679128=67964+64=67964⋅67964 ≡ 565⋅565=319225 ≡ 674 mod 691

679212

= 679128+64+16+4

= 679128⋅67964⋅67916⋅6794

674 ⋅ 565 ⋅ 605 ⋅ 6 mod 691
380810 ⋅ 605 ⋅ 6 mod 691 ≡ 69 ⋅ 605 ⋅ 6 mod 691
41745 ⋅ 6 mod 691 ≡ 285 ⋅ 6 mod 691
1710 mod 691 ≡ 328 mod 691

Es gilt also: 679212 ≡ 328 mod 691

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 55 ⋅ x ≡ 1 mod 83 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 83 und 55

=>83 = 1⋅55 + 28
=>55 = 1⋅28 + 27
=>28 = 1⋅27 + 1
=>27 = 27⋅1 + 0

also gilt: ggt(83,55)=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= 28-1⋅27
27= 55-1⋅28 eingesetzt in die Zeile drüber: 1 = 1⋅28 -1⋅(55 -1⋅ 28)
= 1⋅28 -1⋅55 +1⋅ 28)
= -1⋅55 +2⋅ 28 (=1)
28= 83-1⋅55 eingesetzt in die Zeile drüber: 1 = -1⋅55 +2⋅(83 -1⋅ 55)
= -1⋅55 +2⋅83 -2⋅ 55)
= 2⋅83 -3⋅ 55 (=1)

Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55

oder wenn man 2⋅83 auf die linke Seite bringt:

1 -2⋅83 = -3⋅55

-3⋅55 = -2⋅83 + 1 |+83⋅55

-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1

(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1

80⋅55 = 53⋅83 + 1

Es gilt also: 80⋅55 = 53⋅83 +1

Somit 80⋅55 = 1 mod 83

80 ist also das Inverse von 55 mod 83

Schlüsselpaar für RSA

Beispiel:

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