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

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(203 - 40) mod 4 ≡ (203 mod 4 - 40 mod 4) mod 4.

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

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

Somit gilt:

(203 - 40) mod 4 ≡ (3 - 0) mod 4 ≡ 3 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (74 ⋅ 100) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(74 ⋅ 100) mod 8 ≡ (74 mod 8 ⋅ 100 mod 8) mod 8.

74 mod 8 ≡ 2 mod 8 kann man relativ leicht bestimmen, weil ja 74 = 72 + 2 = 9 ⋅ 8 + 2 ist.

100 mod 8 ≡ 4 mod 8 kann man relativ leicht bestimmen, weil ja 100 = 96 + 4 = 12 ⋅ 8 + 4 ist.

Somit gilt:

(74 ⋅ 100) mod 8 ≡ (2 ⋅ 4) mod 8 ≡ 8 mod 8 ≡ 0 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 29116 mod 293.

Lösung einblenden

Die 16 im Exponent ist ja ein reine 2er-Potenz (24).

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. 291 -> x
2. mod(x²,293) -> 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: 2911=291

2: 2912=2911+1=2911⋅2911 ≡ 291⋅291=84681 ≡ 4 mod 293

4: 2914=2912+2=2912⋅2912 ≡ 4⋅4=16 ≡ 16 mod 293

8: 2918=2914+4=2914⋅2914 ≡ 16⋅16=256 ≡ 256 mod 293

16: 29116=2918+8=2918⋅2918 ≡ 256⋅256=65536 ≡ 197 mod 293

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 726222 mod 881.

Lösung einblenden

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

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

222 = 128+64+16+8+4+2

1: 7261=726

2: 7262=7261+1=7261⋅7261 ≡ 726⋅726=527076 ≡ 238 mod 881

4: 7264=7262+2=7262⋅7262 ≡ 238⋅238=56644 ≡ 260 mod 881

8: 7268=7264+4=7264⋅7264 ≡ 260⋅260=67600 ≡ 644 mod 881

16: 72616=7268+8=7268⋅7268 ≡ 644⋅644=414736 ≡ 666 mod 881

32: 72632=72616+16=72616⋅72616 ≡ 666⋅666=443556 ≡ 413 mod 881

64: 72664=72632+32=72632⋅72632 ≡ 413⋅413=170569 ≡ 536 mod 881

128: 726128=72664+64=72664⋅72664 ≡ 536⋅536=287296 ≡ 90 mod 881

726222

= 726128+64+16+8+4+2

= 726128⋅72664⋅72616⋅7268⋅7264⋅7262

90 ⋅ 536 ⋅ 666 ⋅ 644 ⋅ 260 ⋅ 238 mod 881
48240 ⋅ 666 ⋅ 644 ⋅ 260 ⋅ 238 mod 881 ≡ 666 ⋅ 666 ⋅ 644 ⋅ 260 ⋅ 238 mod 881
443556 ⋅ 644 ⋅ 260 ⋅ 238 mod 881 ≡ 413 ⋅ 644 ⋅ 260 ⋅ 238 mod 881
265972 ⋅ 260 ⋅ 238 mod 881 ≡ 791 ⋅ 260 ⋅ 238 mod 881
205660 ⋅ 238 mod 881 ≡ 387 ⋅ 238 mod 881
92106 mod 881 ≡ 482 mod 881

Es gilt also: 726222 ≡ 482 mod 881

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>83 = 1⋅55 + 28
=>55 = 1⋅28 + 27
=>28 = 1⋅27 + 1
=>27 = 27⋅1 + 0

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

Es gilt also: ggt(83,55)=1 = 2⋅83 -3⋅55

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

1 -2⋅83 = -3⋅55

-3⋅55 = -2⋅83 + 1 |+83⋅55

-3⋅55 + 83⋅55 = -2⋅83 + 83⋅55 + 1

(-3 + 83) ⋅ 55 = (-2 + 55) ⋅ 83 + 1

80⋅55 = 53⋅83 + 1

Es gilt also: 80⋅55 = 53⋅83 +1

Somit 80⋅55 = 1 mod 83

80 ist also das Inverse von 55 mod 83

Schlüsselpaar für RSA

Beispiel:

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