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: (803 - 39992) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(803 - 39992) mod 8 ≡ (803 mod 8 - 39992 mod 8) mod 8.

803 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 803 = 800+3 = 8 ⋅ 100 +3.

39992 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 39992 = 39000+992 = 8 ⋅ 4875 +992.

Somit gilt:

(803 - 39992) mod 8 ≡ (3 - 0) mod 8 ≡ 3 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (18 ⋅ 21) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 21) mod 3 ≡ (18 mod 3 ⋅ 21 mod 3) mod 3.

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

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

Somit gilt:

(18 ⋅ 21) mod 3 ≡ (0 ⋅ 0) mod 3 ≡ 0 mod 3.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 39264 mod 599.

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. 392 -> x
2. mod(x²,599) -> 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: 3921=392

2: 3922=3921+1=3921⋅3921 ≡ 392⋅392=153664 ≡ 320 mod 599

4: 3924=3922+2=3922⋅3922 ≡ 320⋅320=102400 ≡ 570 mod 599

8: 3928=3924+4=3924⋅3924 ≡ 570⋅570=324900 ≡ 242 mod 599

16: 39216=3928+8=3928⋅3928 ≡ 242⋅242=58564 ≡ 461 mod 599

32: 39232=39216+16=39216⋅39216 ≡ 461⋅461=212521 ≡ 475 mod 599

64: 39264=39232+32=39232⋅39232 ≡ 475⋅475=225625 ≡ 401 mod 599

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 600107 mod 619.

Lösung einblenden

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

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

107 = 64+32+8+2+1

1: 6001=600

2: 6002=6001+1=6001⋅6001 ≡ 600⋅600=360000 ≡ 361 mod 619

4: 6004=6002+2=6002⋅6002 ≡ 361⋅361=130321 ≡ 331 mod 619

8: 6008=6004+4=6004⋅6004 ≡ 331⋅331=109561 ≡ 617 mod 619

16: 60016=6008+8=6008⋅6008 ≡ 617⋅617=380689 ≡ 4 mod 619

32: 60032=60016+16=60016⋅60016 ≡ 4⋅4=16 ≡ 16 mod 619

64: 60064=60032+32=60032⋅60032 ≡ 16⋅16=256 ≡ 256 mod 619

600107

= 60064+32+8+2+1

= 60064⋅60032⋅6008⋅6002⋅6001

256 ⋅ 16 ⋅ 617 ⋅ 361 ⋅ 600 mod 619
4096 ⋅ 617 ⋅ 361 ⋅ 600 mod 619 ≡ 382 ⋅ 617 ⋅ 361 ⋅ 600 mod 619
235694 ⋅ 361 ⋅ 600 mod 619 ≡ 474 ⋅ 361 ⋅ 600 mod 619
171114 ⋅ 600 mod 619 ≡ 270 ⋅ 600 mod 619
162000 mod 619 ≡ 441 mod 619

Es gilt also: 600107 ≡ 441 mod 619

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 33 ⋅ x ≡ 1 mod 97 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 97 und 33

=>97 = 2⋅33 + 31
=>33 = 1⋅31 + 2
=>31 = 15⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(97,33)=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= 31-15⋅2
2= 33-1⋅31 eingesetzt in die Zeile drüber: 1 = 1⋅31 -15⋅(33 -1⋅ 31)
= 1⋅31 -15⋅33 +15⋅ 31)
= -15⋅33 +16⋅ 31 (=1)
31= 97-2⋅33 eingesetzt in die Zeile drüber: 1 = -15⋅33 +16⋅(97 -2⋅ 33)
= -15⋅33 +16⋅97 -32⋅ 33)
= 16⋅97 -47⋅ 33 (=1)

Es gilt also: ggt(97,33)=1 = 16⋅97 -47⋅33

oder wenn man 16⋅97 auf die linke Seite bringt:

1 -16⋅97 = -47⋅33

-47⋅33 = -16⋅97 + 1 |+97⋅33

-47⋅33 + 97⋅33 = -16⋅97 + 97⋅33 + 1

(-47 + 97) ⋅ 33 = (-16 + 33) ⋅ 97 + 1

50⋅33 = 17⋅97 + 1

Es gilt also: 50⋅33 = 17⋅97 +1

Somit 50⋅33 = 1 mod 97

50 ist also das Inverse von 33 mod 97

Schlüsselpaar für RSA

Beispiel:

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