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: (1402 - 3504) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1402 - 3504) mod 7 ≡ (1402 mod 7 - 3504 mod 7) mod 7.

1402 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 1402 = 1400+2 = 7 ⋅ 200 +2.

3504 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 3504 = 3500+4 = 7 ⋅ 500 +4.

Somit gilt:

(1402 - 3504) mod 7 ≡ (2 - 4) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (18 ⋅ 34) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 34) mod 10 ≡ (18 mod 10 ⋅ 34 mod 10) mod 10.

18 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 18 = 10 + 8 = 1 ⋅ 10 + 8 ist.

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

Somit gilt:

(18 ⋅ 34) mod 10 ≡ (8 ⋅ 4) mod 10 ≡ 32 mod 10 ≡ 2 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 322128 mod 367.

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. 322 -> x
2. mod(x²,367) -> 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: 3221=322

2: 3222=3221+1=3221⋅3221 ≡ 322⋅322=103684 ≡ 190 mod 367

4: 3224=3222+2=3222⋅3222 ≡ 190⋅190=36100 ≡ 134 mod 367

8: 3228=3224+4=3224⋅3224 ≡ 134⋅134=17956 ≡ 340 mod 367

16: 32216=3228+8=3228⋅3228 ≡ 340⋅340=115600 ≡ 362 mod 367

32: 32232=32216+16=32216⋅32216 ≡ 362⋅362=131044 ≡ 25 mod 367

64: 32264=32232+32=32232⋅32232 ≡ 25⋅25=625 ≡ 258 mod 367

128: 322128=32264+64=32264⋅32264 ≡ 258⋅258=66564 ≡ 137 mod 367

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 242159 mod 743.

Lösung einblenden

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

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

159 = 128+16+8+4+2+1

1: 2421=242

2: 2422=2421+1=2421⋅2421 ≡ 242⋅242=58564 ≡ 610 mod 743

4: 2424=2422+2=2422⋅2422 ≡ 610⋅610=372100 ≡ 600 mod 743

8: 2428=2424+4=2424⋅2424 ≡ 600⋅600=360000 ≡ 388 mod 743

16: 24216=2428+8=2428⋅2428 ≡ 388⋅388=150544 ≡ 458 mod 743

32: 24232=24216+16=24216⋅24216 ≡ 458⋅458=209764 ≡ 238 mod 743

64: 24264=24232+32=24232⋅24232 ≡ 238⋅238=56644 ≡ 176 mod 743

128: 242128=24264+64=24264⋅24264 ≡ 176⋅176=30976 ≡ 513 mod 743

242159

= 242128+16+8+4+2+1

= 242128⋅24216⋅2428⋅2424⋅2422⋅2421

513 ⋅ 458 ⋅ 388 ⋅ 600 ⋅ 610 ⋅ 242 mod 743
234954 ⋅ 388 ⋅ 600 ⋅ 610 ⋅ 242 mod 743 ≡ 166 ⋅ 388 ⋅ 600 ⋅ 610 ⋅ 242 mod 743
64408 ⋅ 600 ⋅ 610 ⋅ 242 mod 743 ≡ 510 ⋅ 600 ⋅ 610 ⋅ 242 mod 743
306000 ⋅ 610 ⋅ 242 mod 743 ≡ 627 ⋅ 610 ⋅ 242 mod 743
382470 ⋅ 242 mod 743 ≡ 568 ⋅ 242 mod 743
137456 mod 743 ≡ 1 mod 743

Es gilt also: 242159 ≡ 1 mod 743

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 19 ⋅ x ≡ 1 mod 61 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 61 und 19

=>61 = 3⋅19 + 4
=>19 = 4⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(61,19)=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= 4-1⋅3
3= 19-4⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(19 -4⋅ 4)
= 1⋅4 -1⋅19 +4⋅ 4)
= -1⋅19 +5⋅ 4 (=1)
4= 61-3⋅19 eingesetzt in die Zeile drüber: 1 = -1⋅19 +5⋅(61 -3⋅ 19)
= -1⋅19 +5⋅61 -15⋅ 19)
= 5⋅61 -16⋅ 19 (=1)

Es gilt also: ggt(61,19)=1 = 5⋅61 -16⋅19

oder wenn man 5⋅61 auf die linke Seite bringt:

1 -5⋅61 = -16⋅19

-16⋅19 = -5⋅61 + 1 |+61⋅19

-16⋅19 + 61⋅19 = -5⋅61 + 61⋅19 + 1

(-16 + 61) ⋅ 19 = (-5 + 19) ⋅ 61 + 1

45⋅19 = 14⋅61 + 1

Es gilt also: 45⋅19 = 14⋅61 +1

Somit 45⋅19 = 1 mod 61

45 ist also das Inverse von 19 mod 61

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.