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: (242 - 3208) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(242 - 3208) mod 8 ≡ (242 mod 8 - 3208 mod 8) mod 8.

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

3208 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 3208 = 3200+8 = 8 ⋅ 400 +8.

Somit gilt:

(242 - 3208) mod 8 ≡ (2 - 0) mod 8 ≡ 2 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (74 ⋅ 36) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 36) mod 11 ≡ (74 mod 11 ⋅ 36 mod 11) mod 11.

74 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 74 = 66 + 8 = 6 ⋅ 11 + 8 ist.

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

Somit gilt:

(74 ⋅ 36) mod 11 ≡ (8 ⋅ 3) mod 11 ≡ 24 mod 11 ≡ 2 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 73964 mod 911.

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. 739 -> x
2. mod(x²,911) -> 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: 7391=739

2: 7392=7391+1=7391⋅7391 ≡ 739⋅739=546121 ≡ 432 mod 911

4: 7394=7392+2=7392⋅7392 ≡ 432⋅432=186624 ≡ 780 mod 911

8: 7398=7394+4=7394⋅7394 ≡ 780⋅780=608400 ≡ 763 mod 911

16: 73916=7398+8=7398⋅7398 ≡ 763⋅763=582169 ≡ 40 mod 911

32: 73932=73916+16=73916⋅73916 ≡ 40⋅40=1600 ≡ 689 mod 911

64: 73964=73932+32=73932⋅73932 ≡ 689⋅689=474721 ≡ 90 mod 911

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 289117 mod 673.

Lösung einblenden

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

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

117 = 64+32+16+4+1

1: 2891=289

2: 2892=2891+1=2891⋅2891 ≡ 289⋅289=83521 ≡ 69 mod 673

4: 2894=2892+2=2892⋅2892 ≡ 69⋅69=4761 ≡ 50 mod 673

8: 2898=2894+4=2894⋅2894 ≡ 50⋅50=2500 ≡ 481 mod 673

16: 28916=2898+8=2898⋅2898 ≡ 481⋅481=231361 ≡ 522 mod 673

32: 28932=28916+16=28916⋅28916 ≡ 522⋅522=272484 ≡ 592 mod 673

64: 28964=28932+32=28932⋅28932 ≡ 592⋅592=350464 ≡ 504 mod 673

289117

= 28964+32+16+4+1

= 28964⋅28932⋅28916⋅2894⋅2891

504 ⋅ 592 ⋅ 522 ⋅ 50 ⋅ 289 mod 673
298368 ⋅ 522 ⋅ 50 ⋅ 289 mod 673 ≡ 229 ⋅ 522 ⋅ 50 ⋅ 289 mod 673
119538 ⋅ 50 ⋅ 289 mod 673 ≡ 417 ⋅ 50 ⋅ 289 mod 673
20850 ⋅ 289 mod 673 ≡ 660 ⋅ 289 mod 673
190740 mod 673 ≡ 281 mod 673

Es gilt also: 289117 ≡ 281 mod 673

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 56 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 56

=>73 = 1⋅56 + 17
=>56 = 3⋅17 + 5
=>17 = 3⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(73,56)=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= 5-2⋅2
2= 17-3⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(17 -3⋅ 5)
= 1⋅5 -2⋅17 +6⋅ 5)
= -2⋅17 +7⋅ 5 (=1)
5= 56-3⋅17 eingesetzt in die Zeile drüber: 1 = -2⋅17 +7⋅(56 -3⋅ 17)
= -2⋅17 +7⋅56 -21⋅ 17)
= 7⋅56 -23⋅ 17 (=1)
17= 73-1⋅56 eingesetzt in die Zeile drüber: 1 = 7⋅56 -23⋅(73 -1⋅ 56)
= 7⋅56 -23⋅73 +23⋅ 56)
= -23⋅73 +30⋅ 56 (=1)

Es gilt also: ggt(73,56)=1 = -23⋅73 +30⋅56

oder wenn man -23⋅73 auf die linke Seite bringt:

1 +23⋅73 = +30⋅56

Es gilt also: 30⋅56 = 23⋅73 +1

Somit 30⋅56 = 1 mod 73

30 ist also das Inverse von 56 mod 73

Schlüsselpaar für RSA

Beispiel:

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