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: (7999 + 15999) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(7999 + 15999) mod 4 ≡ (7999 mod 4 + 15999 mod 4) mod 4.

7999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 7999 = 7000+999 = 4 ⋅ 1750 +999.

15999 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 15999 = 15000+999 = 4 ⋅ 3750 +999.

Somit gilt:

(7999 + 15999) mod 4 ≡ (3 + 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (91 ⋅ 87) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(91 ⋅ 87) mod 4 ≡ (91 mod 4 ⋅ 87 mod 4) mod 4.

91 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 91 = 88 + 3 = 22 ⋅ 4 + 3 ist.

87 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 87 = 84 + 3 = 21 ⋅ 4 + 3 ist.

Somit gilt:

(91 ⋅ 87) mod 4 ≡ (3 ⋅ 3) mod 4 ≡ 9 mod 4 ≡ 1 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 321128 mod 577.

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. 321 -> x
2. mod(x²,577) -> 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: 3211=321

2: 3212=3211+1=3211⋅3211 ≡ 321⋅321=103041 ≡ 335 mod 577

4: 3214=3212+2=3212⋅3212 ≡ 335⋅335=112225 ≡ 287 mod 577

8: 3218=3214+4=3214⋅3214 ≡ 287⋅287=82369 ≡ 435 mod 577

16: 32116=3218+8=3218⋅3218 ≡ 435⋅435=189225 ≡ 546 mod 577

32: 32132=32116+16=32116⋅32116 ≡ 546⋅546=298116 ≡ 384 mod 577

64: 32164=32132+32=32132⋅32132 ≡ 384⋅384=147456 ≡ 321 mod 577

128: 321128=32164+64=32164⋅32164 ≡ 321⋅321=103041 ≡ 335 mod 577

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 192183 mod 373.

Lösung einblenden

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

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

183 = 128+32+16+4+2+1

1: 1921=192

2: 1922=1921+1=1921⋅1921 ≡ 192⋅192=36864 ≡ 310 mod 373

4: 1924=1922+2=1922⋅1922 ≡ 310⋅310=96100 ≡ 239 mod 373

8: 1928=1924+4=1924⋅1924 ≡ 239⋅239=57121 ≡ 52 mod 373

16: 19216=1928+8=1928⋅1928 ≡ 52⋅52=2704 ≡ 93 mod 373

32: 19232=19216+16=19216⋅19216 ≡ 93⋅93=8649 ≡ 70 mod 373

64: 19264=19232+32=19232⋅19232 ≡ 70⋅70=4900 ≡ 51 mod 373

128: 192128=19264+64=19264⋅19264 ≡ 51⋅51=2601 ≡ 363 mod 373

192183

= 192128+32+16+4+2+1

= 192128⋅19232⋅19216⋅1924⋅1922⋅1921

363 ⋅ 70 ⋅ 93 ⋅ 239 ⋅ 310 ⋅ 192 mod 373
25410 ⋅ 93 ⋅ 239 ⋅ 310 ⋅ 192 mod 373 ≡ 46 ⋅ 93 ⋅ 239 ⋅ 310 ⋅ 192 mod 373
4278 ⋅ 239 ⋅ 310 ⋅ 192 mod 373 ≡ 175 ⋅ 239 ⋅ 310 ⋅ 192 mod 373
41825 ⋅ 310 ⋅ 192 mod 373 ≡ 49 ⋅ 310 ⋅ 192 mod 373
15190 ⋅ 192 mod 373 ≡ 270 ⋅ 192 mod 373
51840 mod 373 ≡ 366 mod 373

Es gilt also: 192183 ≡ 366 mod 373

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>73 = 1⋅59 + 14
=>59 = 4⋅14 + 3
=>14 = 4⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(73,59)=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= 3-1⋅2
2= 14-4⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(14 -4⋅ 3)
= 1⋅3 -1⋅14 +4⋅ 3)
= -1⋅14 +5⋅ 3 (=1)
3= 59-4⋅14 eingesetzt in die Zeile drüber: 1 = -1⋅14 +5⋅(59 -4⋅ 14)
= -1⋅14 +5⋅59 -20⋅ 14)
= 5⋅59 -21⋅ 14 (=1)
14= 73-1⋅59 eingesetzt in die Zeile drüber: 1 = 5⋅59 -21⋅(73 -1⋅ 59)
= 5⋅59 -21⋅73 +21⋅ 59)
= -21⋅73 +26⋅ 59 (=1)

Es gilt also: ggt(73,59)=1 = -21⋅73 +26⋅59

oder wenn man -21⋅73 auf die linke Seite bringt:

1 +21⋅73 = +26⋅59

Es gilt also: 26⋅59 = 21⋅73 +1

Somit 26⋅59 = 1 mod 73

26 ist also das Inverse von 59 mod 73

Schlüsselpaar für RSA

Beispiel:

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