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: (802 + 203) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(802 + 203) mod 4 ≡ (802 mod 4 + 203 mod 4) mod 4.

802 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 802 = 800+2 = 4 ⋅ 200 +2.

203 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 203 = 200+3 = 4 ⋅ 50 +3.

Somit gilt:

(802 + 203) mod 4 ≡ (2 + 3) mod 4 ≡ 5 mod 4 ≡ 1 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (85 ⋅ 97) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(85 ⋅ 97) mod 7 ≡ (85 mod 7 ⋅ 97 mod 7) mod 7.

85 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 85 = 84 + 1 = 12 ⋅ 7 + 1 ist.

97 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 97 = 91 + 6 = 13 ⋅ 7 + 6 ist.

Somit gilt:

(85 ⋅ 97) mod 7 ≡ (1 ⋅ 6) mod 7 ≡ 6 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 42464 mod 953.

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. 424 -> x
2. mod(x²,953) -> 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: 4241=424

2: 4242=4241+1=4241⋅4241 ≡ 424⋅424=179776 ≡ 612 mod 953

4: 4244=4242+2=4242⋅4242 ≡ 612⋅612=374544 ≡ 15 mod 953

8: 4248=4244+4=4244⋅4244 ≡ 15⋅15=225 ≡ 225 mod 953

16: 42416=4248+8=4248⋅4248 ≡ 225⋅225=50625 ≡ 116 mod 953

32: 42432=42416+16=42416⋅42416 ≡ 116⋅116=13456 ≡ 114 mod 953

64: 42464=42432+32=42432⋅42432 ≡ 114⋅114=12996 ≡ 607 mod 953

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 22281 mod 593.

Lösung einblenden

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

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

81 = 64+16+1

1: 2221=222

2: 2222=2221+1=2221⋅2221 ≡ 222⋅222=49284 ≡ 65 mod 593

4: 2224=2222+2=2222⋅2222 ≡ 65⋅65=4225 ≡ 74 mod 593

8: 2228=2224+4=2224⋅2224 ≡ 74⋅74=5476 ≡ 139 mod 593

16: 22216=2228+8=2228⋅2228 ≡ 139⋅139=19321 ≡ 345 mod 593

32: 22232=22216+16=22216⋅22216 ≡ 345⋅345=119025 ≡ 425 mod 593

64: 22264=22232+32=22232⋅22232 ≡ 425⋅425=180625 ≡ 353 mod 593

22281

= 22264+16+1

= 22264⋅22216⋅2221

353 ⋅ 345 ⋅ 222 mod 593
121785 ⋅ 222 mod 593 ≡ 220 ⋅ 222 mod 593
48840 mod 593 ≡ 214 mod 593

Es gilt also: 22281 ≡ 214 mod 593

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 25

=>67 = 2⋅25 + 17
=>25 = 1⋅17 + 8
=>17 = 2⋅8 + 1
=>8 = 8⋅1 + 0

also gilt: ggt(67,25)=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= 17-2⋅8
8= 25-1⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -2⋅(25 -1⋅ 17)
= 1⋅17 -2⋅25 +2⋅ 17)
= -2⋅25 +3⋅ 17 (=1)
17= 67-2⋅25 eingesetzt in die Zeile drüber: 1 = -2⋅25 +3⋅(67 -2⋅ 25)
= -2⋅25 +3⋅67 -6⋅ 25)
= 3⋅67 -8⋅ 25 (=1)

Es gilt also: ggt(67,25)=1 = 3⋅67 -8⋅25

oder wenn man 3⋅67 auf die linke Seite bringt:

1 -3⋅67 = -8⋅25

-8⋅25 = -3⋅67 + 1 |+67⋅25

-8⋅25 + 67⋅25 = -3⋅67 + 67⋅25 + 1

(-8 + 67) ⋅ 25 = (-3 + 25) ⋅ 67 + 1

59⋅25 = 22⋅67 + 1

Es gilt also: 59⋅25 = 22⋅67 +1

Somit 59⋅25 = 1 mod 67

59 ist also das Inverse von 25 mod 67

Schlüsselpaar für RSA

Beispiel:

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