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: (1497 - 30) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1497 - 30) mod 3 ≡ (1497 mod 3 - 30 mod 3) mod 3.

1497 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1497 = 1500-3 = 3 ⋅ 500 -3 = 3 ⋅ 500 - 3 + 0.

30 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 30 = 30+0 = 3 ⋅ 10 +0.

Somit gilt:

(1497 - 30) mod 3 ≡ (0 - 0) mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (99 ⋅ 20) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 20) mod 11 ≡ (99 mod 11 ⋅ 20 mod 11) mod 11.

99 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 99 = 99 + 0 = 9 ⋅ 11 + 0 ist.

20 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 20 = 11 + 9 = 1 ⋅ 11 + 9 ist.

Somit gilt:

(99 ⋅ 20) mod 11 ≡ (0 ⋅ 9) mod 11 ≡ 0 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 542128 mod 877.

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. 542 -> x
2. mod(x²,877) -> 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: 5421=542

2: 5422=5421+1=5421⋅5421 ≡ 542⋅542=293764 ≡ 846 mod 877

4: 5424=5422+2=5422⋅5422 ≡ 846⋅846=715716 ≡ 84 mod 877

8: 5428=5424+4=5424⋅5424 ≡ 84⋅84=7056 ≡ 40 mod 877

16: 54216=5428+8=5428⋅5428 ≡ 40⋅40=1600 ≡ 723 mod 877

32: 54232=54216+16=54216⋅54216 ≡ 723⋅723=522729 ≡ 37 mod 877

64: 54264=54232+32=54232⋅54232 ≡ 37⋅37=1369 ≡ 492 mod 877

128: 542128=54264+64=54264⋅54264 ≡ 492⋅492=242064 ≡ 12 mod 877

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 474154 mod 601.

Lösung einblenden

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

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

154 = 128+16+8+2

1: 4741=474

2: 4742=4741+1=4741⋅4741 ≡ 474⋅474=224676 ≡ 503 mod 601

4: 4744=4742+2=4742⋅4742 ≡ 503⋅503=253009 ≡ 589 mod 601

8: 4748=4744+4=4744⋅4744 ≡ 589⋅589=346921 ≡ 144 mod 601

16: 47416=4748+8=4748⋅4748 ≡ 144⋅144=20736 ≡ 302 mod 601

32: 47432=47416+16=47416⋅47416 ≡ 302⋅302=91204 ≡ 453 mod 601

64: 47464=47432+32=47432⋅47432 ≡ 453⋅453=205209 ≡ 268 mod 601

128: 474128=47464+64=47464⋅47464 ≡ 268⋅268=71824 ≡ 305 mod 601

474154

= 474128+16+8+2

= 474128⋅47416⋅4748⋅4742

305 ⋅ 302 ⋅ 144 ⋅ 503 mod 601
92110 ⋅ 144 ⋅ 503 mod 601 ≡ 157 ⋅ 144 ⋅ 503 mod 601
22608 ⋅ 503 mod 601 ≡ 371 ⋅ 503 mod 601
186613 mod 601 ≡ 303 mod 601

Es gilt also: 474154 ≡ 303 mod 601

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 31 ⋅ x ≡ 1 mod 59 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 59 und 31

=>59 = 1⋅31 + 28
=>31 = 1⋅28 + 3
=>28 = 9⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(59,31)=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-9⋅3
3= 31-1⋅28 eingesetzt in die Zeile drüber: 1 = 1⋅28 -9⋅(31 -1⋅ 28)
= 1⋅28 -9⋅31 +9⋅ 28)
= -9⋅31 +10⋅ 28 (=1)
28= 59-1⋅31 eingesetzt in die Zeile drüber: 1 = -9⋅31 +10⋅(59 -1⋅ 31)
= -9⋅31 +10⋅59 -10⋅ 31)
= 10⋅59 -19⋅ 31 (=1)

Es gilt also: ggt(59,31)=1 = 10⋅59 -19⋅31

oder wenn man 10⋅59 auf die linke Seite bringt:

1 -10⋅59 = -19⋅31

-19⋅31 = -10⋅59 + 1 |+59⋅31

-19⋅31 + 59⋅31 = -10⋅59 + 59⋅31 + 1

(-19 + 59) ⋅ 31 = (-10 + 31) ⋅ 59 + 1

40⋅31 = 21⋅59 + 1

Es gilt also: 40⋅31 = 21⋅59 +1

Somit 40⋅31 = 1 mod 59

40 ist also das Inverse von 31 mod 59

Schlüsselpaar für RSA

Beispiel:

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