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: (1600 + 16000) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1600 + 16000) mod 8 ≡ (1600 mod 8 + 16000 mod 8) mod 8.

1600 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 1600 = 1600+0 = 8 ⋅ 200 +0.

16000 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 16000 = 16000+0 = 8 ⋅ 2000 +0.

Somit gilt:

(1600 + 16000) mod 8 ≡ (0 + 0) mod 8 ≡ 0 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (44 ⋅ 70) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(44 ⋅ 70) mod 10 ≡ (44 mod 10 ⋅ 70 mod 10) mod 10.

44 mod 10 ≡ 4 mod 10 kann man relativ leicht bestimmen, weil ja 44 = 40 + 4 = 4 ⋅ 10 + 4 ist.

70 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 70 = 70 + 0 = 7 ⋅ 10 + 0 ist.

Somit gilt:

(44 ⋅ 70) mod 10 ≡ (4 ⋅ 0) mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 994128 mod 1009.

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. 994 -> x
2. mod(x²,1009) -> 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: 9941=994

2: 9942=9941+1=9941⋅9941 ≡ 994⋅994=988036 ≡ 225 mod 1009

4: 9944=9942+2=9942⋅9942 ≡ 225⋅225=50625 ≡ 175 mod 1009

8: 9948=9944+4=9944⋅9944 ≡ 175⋅175=30625 ≡ 355 mod 1009

16: 99416=9948+8=9948⋅9948 ≡ 355⋅355=126025 ≡ 909 mod 1009

32: 99432=99416+16=99416⋅99416 ≡ 909⋅909=826281 ≡ 919 mod 1009

64: 99464=99432+32=99432⋅99432 ≡ 919⋅919=844561 ≡ 28 mod 1009

128: 994128=99464+64=99464⋅99464 ≡ 28⋅28=784 ≡ 784 mod 1009

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 429233 mod 823.

Lösung einblenden

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

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

233 = 128+64+32+8+1

1: 4291=429

2: 4292=4291+1=4291⋅4291 ≡ 429⋅429=184041 ≡ 512 mod 823

4: 4294=4292+2=4292⋅4292 ≡ 512⋅512=262144 ≡ 430 mod 823

8: 4298=4294+4=4294⋅4294 ≡ 430⋅430=184900 ≡ 548 mod 823

16: 42916=4298+8=4298⋅4298 ≡ 548⋅548=300304 ≡ 732 mod 823

32: 42932=42916+16=42916⋅42916 ≡ 732⋅732=535824 ≡ 51 mod 823

64: 42964=42932+32=42932⋅42932 ≡ 51⋅51=2601 ≡ 132 mod 823

128: 429128=42964+64=42964⋅42964 ≡ 132⋅132=17424 ≡ 141 mod 823

429233

= 429128+64+32+8+1

= 429128⋅42964⋅42932⋅4298⋅4291

141 ⋅ 132 ⋅ 51 ⋅ 548 ⋅ 429 mod 823
18612 ⋅ 51 ⋅ 548 ⋅ 429 mod 823 ≡ 506 ⋅ 51 ⋅ 548 ⋅ 429 mod 823
25806 ⋅ 548 ⋅ 429 mod 823 ≡ 293 ⋅ 548 ⋅ 429 mod 823
160564 ⋅ 429 mod 823 ≡ 79 ⋅ 429 mod 823
33891 mod 823 ≡ 148 mod 823

Es gilt also: 429233 ≡ 148 mod 823

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 76 ⋅ x ≡ 1 mod 83 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 83 und 76

=>83 = 1⋅76 + 7
=>76 = 10⋅7 + 6
=>7 = 1⋅6 + 1
=>6 = 6⋅1 + 0

also gilt: ggt(83,76)=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= 7-1⋅6
6= 76-10⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -1⋅(76 -10⋅ 7)
= 1⋅7 -1⋅76 +10⋅ 7)
= -1⋅76 +11⋅ 7 (=1)
7= 83-1⋅76 eingesetzt in die Zeile drüber: 1 = -1⋅76 +11⋅(83 -1⋅ 76)
= -1⋅76 +11⋅83 -11⋅ 76)
= 11⋅83 -12⋅ 76 (=1)

Es gilt also: ggt(83,76)=1 = 11⋅83 -12⋅76

oder wenn man 11⋅83 auf die linke Seite bringt:

1 -11⋅83 = -12⋅76

-12⋅76 = -11⋅83 + 1 |+83⋅76

-12⋅76 + 83⋅76 = -11⋅83 + 83⋅76 + 1

(-12 + 83) ⋅ 76 = (-11 + 76) ⋅ 83 + 1

71⋅76 = 65⋅83 + 1

Es gilt also: 71⋅76 = 65⋅83 +1

Somit 71⋅76 = 1 mod 83

71 ist also das Inverse von 76 mod 83

Schlüsselpaar für RSA

Beispiel:

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