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: (3000 - 1201) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3000 - 1201) mod 3 ≡ (3000 mod 3 - 1201 mod 3) mod 3.

3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000 = 3000+0 = 3 ⋅ 1000 +0.

1201 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1201 = 1200+1 = 3 ⋅ 400 +1.

Somit gilt:

(3000 - 1201) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (21 ⋅ 69) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(21 ⋅ 69) mod 11 ≡ (21 mod 11 ⋅ 69 mod 11) mod 11.

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

69 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 69 = 66 + 3 = 6 ⋅ 11 + 3 ist.

Somit gilt:

(21 ⋅ 69) mod 11 ≡ (10 ⋅ 3) mod 11 ≡ 30 mod 11 ≡ 8 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 780128 mod 907.

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. 780 -> x
2. mod(x²,907) -> 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: 7801=780

2: 7802=7801+1=7801⋅7801 ≡ 780⋅780=608400 ≡ 710 mod 907

4: 7804=7802+2=7802⋅7802 ≡ 710⋅710=504100 ≡ 715 mod 907

8: 7808=7804+4=7804⋅7804 ≡ 715⋅715=511225 ≡ 584 mod 907

16: 78016=7808+8=7808⋅7808 ≡ 584⋅584=341056 ≡ 24 mod 907

32: 78032=78016+16=78016⋅78016 ≡ 24⋅24=576 ≡ 576 mod 907

64: 78064=78032+32=78032⋅78032 ≡ 576⋅576=331776 ≡ 721 mod 907

128: 780128=78064+64=78064⋅78064 ≡ 721⋅721=519841 ≡ 130 mod 907

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 302207 mod 929.

Lösung einblenden

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

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

207 = 128+64+8+4+2+1

1: 3021=302

2: 3022=3021+1=3021⋅3021 ≡ 302⋅302=91204 ≡ 162 mod 929

4: 3024=3022+2=3022⋅3022 ≡ 162⋅162=26244 ≡ 232 mod 929

8: 3028=3024+4=3024⋅3024 ≡ 232⋅232=53824 ≡ 871 mod 929

16: 30216=3028+8=3028⋅3028 ≡ 871⋅871=758641 ≡ 577 mod 929

32: 30232=30216+16=30216⋅30216 ≡ 577⋅577=332929 ≡ 347 mod 929

64: 30264=30232+32=30232⋅30232 ≡ 347⋅347=120409 ≡ 568 mod 929

128: 302128=30264+64=30264⋅30264 ≡ 568⋅568=322624 ≡ 261 mod 929

302207

= 302128+64+8+4+2+1

= 302128⋅30264⋅3028⋅3024⋅3022⋅3021

261 ⋅ 568 ⋅ 871 ⋅ 232 ⋅ 162 ⋅ 302 mod 929
148248 ⋅ 871 ⋅ 232 ⋅ 162 ⋅ 302 mod 929 ≡ 537 ⋅ 871 ⋅ 232 ⋅ 162 ⋅ 302 mod 929
467727 ⋅ 232 ⋅ 162 ⋅ 302 mod 929 ≡ 440 ⋅ 232 ⋅ 162 ⋅ 302 mod 929
102080 ⋅ 162 ⋅ 302 mod 929 ≡ 819 ⋅ 162 ⋅ 302 mod 929
132678 ⋅ 302 mod 929 ≡ 760 ⋅ 302 mod 929
229520 mod 929 ≡ 57 mod 929

Es gilt also: 302207 ≡ 57 mod 929

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 1⋅67 + 34
=>67 = 1⋅34 + 33
=>34 = 1⋅33 + 1
=>33 = 33⋅1 + 0

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

Es gilt also: ggt(101,67)=1 = 2⋅101 -3⋅67

oder wenn man 2⋅101 auf die linke Seite bringt:

1 -2⋅101 = -3⋅67

-3⋅67 = -2⋅101 + 1 |+101⋅67

-3⋅67 + 101⋅67 = -2⋅101 + 101⋅67 + 1

(-3 + 101) ⋅ 67 = (-2 + 67) ⋅ 101 + 1

98⋅67 = 65⋅101 + 1

Es gilt also: 98⋅67 = 65⋅101 +1

Somit 98⋅67 = 1 mod 101

98 ist also das Inverse von 67 mod 101

Schlüsselpaar für RSA

Beispiel:

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