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: (92 + 368) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(92 + 368) mod 9 ≡ (92 mod 9 + 368 mod 9) mod 9.

92 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 92 = 90+2 = 9 ⋅ 10 +2.

368 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 368 = 360+8 = 9 ⋅ 40 +8.

Somit gilt:

(92 + 368) mod 9 ≡ (2 + 8) mod 9 ≡ 10 mod 9 ≡ 1 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (65 ⋅ 29) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(65 ⋅ 29) mod 7 ≡ (65 mod 7 ⋅ 29 mod 7) mod 7.

65 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 9 ⋅ 7 + 2 ist.

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

Somit gilt:

(65 ⋅ 29) mod 7 ≡ (2 ⋅ 1) mod 7 ≡ 2 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 55864 mod 787.

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. 558 -> x
2. mod(x²,787) -> 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: 5581=558

2: 5582=5581+1=5581⋅5581 ≡ 558⋅558=311364 ≡ 499 mod 787

4: 5584=5582+2=5582⋅5582 ≡ 499⋅499=249001 ≡ 309 mod 787

8: 5588=5584+4=5584⋅5584 ≡ 309⋅309=95481 ≡ 254 mod 787

16: 55816=5588+8=5588⋅5588 ≡ 254⋅254=64516 ≡ 769 mod 787

32: 55832=55816+16=55816⋅55816 ≡ 769⋅769=591361 ≡ 324 mod 787

64: 55864=55832+32=55832⋅55832 ≡ 324⋅324=104976 ≡ 305 mod 787

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 29578 mod 599.

Lösung einblenden

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

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

78 = 64+8+4+2

1: 2951=295

2: 2952=2951+1=2951⋅2951 ≡ 295⋅295=87025 ≡ 170 mod 599

4: 2954=2952+2=2952⋅2952 ≡ 170⋅170=28900 ≡ 148 mod 599

8: 2958=2954+4=2954⋅2954 ≡ 148⋅148=21904 ≡ 340 mod 599

16: 29516=2958+8=2958⋅2958 ≡ 340⋅340=115600 ≡ 592 mod 599

32: 29532=29516+16=29516⋅29516 ≡ 592⋅592=350464 ≡ 49 mod 599

64: 29564=29532+32=29532⋅29532 ≡ 49⋅49=2401 ≡ 5 mod 599

29578

= 29564+8+4+2

= 29564⋅2958⋅2954⋅2952

5 ⋅ 340 ⋅ 148 ⋅ 170 mod 599
1700 ⋅ 148 ⋅ 170 mod 599 ≡ 502 ⋅ 148 ⋅ 170 mod 599
74296 ⋅ 170 mod 599 ≡ 20 ⋅ 170 mod 599
3400 mod 599 ≡ 405 mod 599

Es gilt also: 29578 ≡ 405 mod 599

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 60 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 60

=>89 = 1⋅60 + 29
=>60 = 2⋅29 + 2
=>29 = 14⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(89,60)=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-14⋅2
2= 60-2⋅29 eingesetzt in die Zeile drüber: 1 = 1⋅29 -14⋅(60 -2⋅ 29)
= 1⋅29 -14⋅60 +28⋅ 29)
= -14⋅60 +29⋅ 29 (=1)
29= 89-1⋅60 eingesetzt in die Zeile drüber: 1 = -14⋅60 +29⋅(89 -1⋅ 60)
= -14⋅60 +29⋅89 -29⋅ 60)
= 29⋅89 -43⋅ 60 (=1)

Es gilt also: ggt(89,60)=1 = 29⋅89 -43⋅60

oder wenn man 29⋅89 auf die linke Seite bringt:

1 -29⋅89 = -43⋅60

-43⋅60 = -29⋅89 + 1 |+89⋅60

-43⋅60 + 89⋅60 = -29⋅89 + 89⋅60 + 1

(-43 + 89) ⋅ 60 = (-29 + 60) ⋅ 89 + 1

46⋅60 = 31⋅89 + 1

Es gilt also: 46⋅60 = 31⋅89 +1

Somit 46⋅60 = 1 mod 89

46 ist also das Inverse von 60 mod 89

Schlüsselpaar für RSA

Beispiel:

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