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: (352 + 343) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(352 + 343) mod 7 ≡ (352 mod 7 + 343 mod 7) mod 7.

352 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 352 = 350+2 = 7 ⋅ 50 +2.

343 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 343 = 350-7 = 7 ⋅ 50 -7 = 7 ⋅ 50 - 7 + 0.

Somit gilt:

(352 + 343) mod 7 ≡ (2 + 0) mod 7 ≡ 2 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (77 ⋅ 20) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(77 ⋅ 20) mod 4 ≡ (77 mod 4 ⋅ 20 mod 4) mod 4.

77 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 77 = 76 + 1 = 19 ⋅ 4 + 1 ist.

20 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 20 = 20 + 0 = 5 ⋅ 4 + 0 ist.

Somit gilt:

(77 ⋅ 20) mod 4 ≡ (1 ⋅ 0) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 32816 mod 613.

Lösung einblenden

Die 16 im Exponent ist ja ein reine 2er-Potenz (24).

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. 328 -> x
2. mod(x²,613) -> 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: 3281=328

2: 3282=3281+1=3281⋅3281 ≡ 328⋅328=107584 ≡ 309 mod 613

4: 3284=3282+2=3282⋅3282 ≡ 309⋅309=95481 ≡ 466 mod 613

8: 3288=3284+4=3284⋅3284 ≡ 466⋅466=217156 ≡ 154 mod 613

16: 32816=3288+8=3288⋅3288 ≡ 154⋅154=23716 ≡ 422 mod 613

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 418123 mod 433.

Lösung einblenden

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

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

123 = 64+32+16+8+2+1

1: 4181=418

2: 4182=4181+1=4181⋅4181 ≡ 418⋅418=174724 ≡ 225 mod 433

4: 4184=4182+2=4182⋅4182 ≡ 225⋅225=50625 ≡ 397 mod 433

8: 4188=4184+4=4184⋅4184 ≡ 397⋅397=157609 ≡ 430 mod 433

16: 41816=4188+8=4188⋅4188 ≡ 430⋅430=184900 ≡ 9 mod 433

32: 41832=41816+16=41816⋅41816 ≡ 9⋅9=81 ≡ 81 mod 433

64: 41864=41832+32=41832⋅41832 ≡ 81⋅81=6561 ≡ 66 mod 433

418123

= 41864+32+16+8+2+1

= 41864⋅41832⋅41816⋅4188⋅4182⋅4181

66 ⋅ 81 ⋅ 9 ⋅ 430 ⋅ 225 ⋅ 418 mod 433
5346 ⋅ 9 ⋅ 430 ⋅ 225 ⋅ 418 mod 433 ≡ 150 ⋅ 9 ⋅ 430 ⋅ 225 ⋅ 418 mod 433
1350 ⋅ 430 ⋅ 225 ⋅ 418 mod 433 ≡ 51 ⋅ 430 ⋅ 225 ⋅ 418 mod 433
21930 ⋅ 225 ⋅ 418 mod 433 ≡ 280 ⋅ 225 ⋅ 418 mod 433
63000 ⋅ 418 mod 433 ≡ 215 ⋅ 418 mod 433
89870 mod 433 ≡ 239 mod 433

Es gilt also: 418123 ≡ 239 mod 433

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>61 = 3⋅18 + 7
=>18 = 2⋅7 + 4
=>7 = 1⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

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

Es gilt also: ggt(61,18)=1 = -5⋅61 +17⋅18

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

1 +5⋅61 = +17⋅18

Es gilt also: 17⋅18 = 5⋅61 +1

Somit 17⋅18 = 1 mod 61

17 ist also das Inverse von 18 mod 61

Schlüsselpaar für RSA

Beispiel:

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