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: (8003 - 1199) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(8003 - 1199) mod 4 ≡ (8003 mod 4 - 1199 mod 4) mod 4.

8003 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 8003 = 8000+3 = 4 ⋅ 2000 +3.

1199 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 1199 = 1100+99 = 4 ⋅ 275 +99.

Somit gilt:

(8003 - 1199) mod 4 ≡ (3 - 3) mod 4 ≡ 0 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (48 ⋅ 62) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(48 ⋅ 62) mod 9 ≡ (48 mod 9 ⋅ 62 mod 9) mod 9.

48 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 48 = 45 + 3 = 5 ⋅ 9 + 3 ist.

62 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 62 = 54 + 8 = 6 ⋅ 9 + 8 ist.

Somit gilt:

(48 ⋅ 62) mod 9 ≡ (3 ⋅ 8) mod 9 ≡ 24 mod 9 ≡ 6 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 47164 mod 821.

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. 471 -> x
2. mod(x²,821) -> 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: 4711=471

2: 4712=4711+1=4711⋅4711 ≡ 471⋅471=221841 ≡ 171 mod 821

4: 4714=4712+2=4712⋅4712 ≡ 171⋅171=29241 ≡ 506 mod 821

8: 4718=4714+4=4714⋅4714 ≡ 506⋅506=256036 ≡ 705 mod 821

16: 47116=4718+8=4718⋅4718 ≡ 705⋅705=497025 ≡ 320 mod 821

32: 47132=47116+16=47116⋅47116 ≡ 320⋅320=102400 ≡ 596 mod 821

64: 47164=47132+32=47132⋅47132 ≡ 596⋅596=355216 ≡ 544 mod 821

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 292222 mod 449.

Lösung einblenden

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

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

222 = 128+64+16+8+4+2

1: 2921=292

2: 2922=2921+1=2921⋅2921 ≡ 292⋅292=85264 ≡ 403 mod 449

4: 2924=2922+2=2922⋅2922 ≡ 403⋅403=162409 ≡ 320 mod 449

8: 2928=2924+4=2924⋅2924 ≡ 320⋅320=102400 ≡ 28 mod 449

16: 29216=2928+8=2928⋅2928 ≡ 28⋅28=784 ≡ 335 mod 449

32: 29232=29216+16=29216⋅29216 ≡ 335⋅335=112225 ≡ 424 mod 449

64: 29264=29232+32=29232⋅29232 ≡ 424⋅424=179776 ≡ 176 mod 449

128: 292128=29264+64=29264⋅29264 ≡ 176⋅176=30976 ≡ 444 mod 449

292222

= 292128+64+16+8+4+2

= 292128⋅29264⋅29216⋅2928⋅2924⋅2922

444 ⋅ 176 ⋅ 335 ⋅ 28 ⋅ 320 ⋅ 403 mod 449
78144 ⋅ 335 ⋅ 28 ⋅ 320 ⋅ 403 mod 449 ≡ 18 ⋅ 335 ⋅ 28 ⋅ 320 ⋅ 403 mod 449
6030 ⋅ 28 ⋅ 320 ⋅ 403 mod 449 ≡ 193 ⋅ 28 ⋅ 320 ⋅ 403 mod 449
5404 ⋅ 320 ⋅ 403 mod 449 ≡ 16 ⋅ 320 ⋅ 403 mod 449
5120 ⋅ 403 mod 449 ≡ 181 ⋅ 403 mod 449
72943 mod 449 ≡ 205 mod 449

Es gilt also: 292222 ≡ 205 mod 449

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>89 = 1⋅77 + 12
=>77 = 6⋅12 + 5
=>12 = 2⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(89,77)=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= 12-2⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(12 -2⋅ 5)
= 1⋅5 -2⋅12 +4⋅ 5)
= -2⋅12 +5⋅ 5 (=1)
5= 77-6⋅12 eingesetzt in die Zeile drüber: 1 = -2⋅12 +5⋅(77 -6⋅ 12)
= -2⋅12 +5⋅77 -30⋅ 12)
= 5⋅77 -32⋅ 12 (=1)
12= 89-1⋅77 eingesetzt in die Zeile drüber: 1 = 5⋅77 -32⋅(89 -1⋅ 77)
= 5⋅77 -32⋅89 +32⋅ 77)
= -32⋅89 +37⋅ 77 (=1)

Es gilt also: ggt(89,77)=1 = -32⋅89 +37⋅77

oder wenn man -32⋅89 auf die linke Seite bringt:

1 +32⋅89 = +37⋅77

Es gilt also: 37⋅77 = 32⋅89 +1

Somit 37⋅77 = 1 mod 89

37 ist also das Inverse von 77 mod 89

Schlüsselpaar für RSA

Beispiel:

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