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: (24006 - 4003) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(24006 - 4003) mod 8 ≡ (24006 mod 8 - 4003 mod 8) mod 8.

24006 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 24006 = 24000+6 = 8 ⋅ 3000 +6.

4003 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 4003 = 4000+3 = 8 ⋅ 500 +3.

Somit gilt:

(24006 - 4003) mod 8 ≡ (6 - 3) mod 8 ≡ 3 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (90 ⋅ 75) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(90 ⋅ 75) mod 4 ≡ (90 mod 4 ⋅ 75 mod 4) mod 4.

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

75 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 75 = 72 + 3 = 18 ⋅ 4 + 3 ist.

Somit gilt:

(90 ⋅ 75) mod 4 ≡ (2 ⋅ 3) mod 4 ≡ 6 mod 4 ≡ 2 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 28732 mod 353.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 287 -> x
2. mod(x²,353) -> 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: 2871=287

2: 2872=2871+1=2871⋅2871 ≡ 287⋅287=82369 ≡ 120 mod 353

4: 2874=2872+2=2872⋅2872 ≡ 120⋅120=14400 ≡ 280 mod 353

8: 2878=2874+4=2874⋅2874 ≡ 280⋅280=78400 ≡ 34 mod 353

16: 28716=2878+8=2878⋅2878 ≡ 34⋅34=1156 ≡ 97 mod 353

32: 28732=28716+16=28716⋅28716 ≡ 97⋅97=9409 ≡ 231 mod 353

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 332254 mod 467.

Lösung einblenden

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

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

254 = 128+64+32+16+8+4+2

1: 3321=332

2: 3322=3321+1=3321⋅3321 ≡ 332⋅332=110224 ≡ 12 mod 467

4: 3324=3322+2=3322⋅3322 ≡ 12⋅12=144 ≡ 144 mod 467

8: 3328=3324+4=3324⋅3324 ≡ 144⋅144=20736 ≡ 188 mod 467

16: 33216=3328+8=3328⋅3328 ≡ 188⋅188=35344 ≡ 319 mod 467

32: 33232=33216+16=33216⋅33216 ≡ 319⋅319=101761 ≡ 422 mod 467

64: 33264=33232+32=33232⋅33232 ≡ 422⋅422=178084 ≡ 157 mod 467

128: 332128=33264+64=33264⋅33264 ≡ 157⋅157=24649 ≡ 365 mod 467

332254

= 332128+64+32+16+8+4+2

= 332128⋅33264⋅33232⋅33216⋅3328⋅3324⋅3322

365 ⋅ 157 ⋅ 422 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
57305 ⋅ 422 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467 ≡ 331 ⋅ 422 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
139682 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467 ≡ 49 ⋅ 319 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
15631 ⋅ 188 ⋅ 144 ⋅ 12 mod 467 ≡ 220 ⋅ 188 ⋅ 144 ⋅ 12 mod 467
41360 ⋅ 144 ⋅ 12 mod 467 ≡ 264 ⋅ 144 ⋅ 12 mod 467
38016 ⋅ 12 mod 467 ≡ 189 ⋅ 12 mod 467
2268 mod 467 ≡ 400 mod 467

Es gilt also: 332254 ≡ 400 mod 467

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>83 = 1⋅62 + 21
=>62 = 2⋅21 + 20
=>21 = 1⋅20 + 1
=>20 = 20⋅1 + 0

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

Es gilt also: ggt(83,62)=1 = 3⋅83 -4⋅62

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

1 -3⋅83 = -4⋅62

-4⋅62 = -3⋅83 + 1 |+83⋅62

-4⋅62 + 83⋅62 = -3⋅83 + 83⋅62 + 1

(-4 + 83) ⋅ 62 = (-3 + 62) ⋅ 83 + 1

79⋅62 = 59⋅83 + 1

Es gilt also: 79⋅62 = 59⋅83 +1

Somit 79⋅62 = 1 mod 83

79 ist also das Inverse von 62 mod 83

Schlüsselpaar für RSA

Beispiel:

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