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: (10001 - 496) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(10001 - 496) mod 5 ≡ (10001 mod 5 - 496 mod 5) mod 5.

10001 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 10001 = 10000+1 = 5 ⋅ 2000 +1.

496 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 496 = 400+96 = 5 ⋅ 80 +96.

Somit gilt:

(10001 - 496) mod 5 ≡ (1 - 1) mod 5 ≡ 0 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (81 ⋅ 22) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 22) mod 11 ≡ (81 mod 11 ⋅ 22 mod 11) mod 11.

81 mod 11 ≡ 4 mod 11 kann man relativ leicht bestimmen, weil ja 81 = 77 + 4 = 7 ⋅ 11 + 4 ist.

22 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 22 = 22 + 0 = 2 ⋅ 11 + 0 ist.

Somit gilt:

(81 ⋅ 22) mod 11 ≡ (4 ⋅ 0) mod 11 ≡ 0 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 33116 mod 859.

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. 331 -> x
2. mod(x²,859) -> 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: 3311=331

2: 3312=3311+1=3311⋅3311 ≡ 331⋅331=109561 ≡ 468 mod 859

4: 3314=3312+2=3312⋅3312 ≡ 468⋅468=219024 ≡ 838 mod 859

8: 3318=3314+4=3314⋅3314 ≡ 838⋅838=702244 ≡ 441 mod 859

16: 33116=3318+8=3318⋅3318 ≡ 441⋅441=194481 ≡ 347 mod 859

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 498217 mod 691.

Lösung einblenden

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

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

217 = 128+64+16+8+1

1: 4981=498

2: 4982=4981+1=4981⋅4981 ≡ 498⋅498=248004 ≡ 626 mod 691

4: 4984=4982+2=4982⋅4982 ≡ 626⋅626=391876 ≡ 79 mod 691

8: 4988=4984+4=4984⋅4984 ≡ 79⋅79=6241 ≡ 22 mod 691

16: 49816=4988+8=4988⋅4988 ≡ 22⋅22=484 ≡ 484 mod 691

32: 49832=49816+16=49816⋅49816 ≡ 484⋅484=234256 ≡ 7 mod 691

64: 49864=49832+32=49832⋅49832 ≡ 7⋅7=49 ≡ 49 mod 691

128: 498128=49864+64=49864⋅49864 ≡ 49⋅49=2401 ≡ 328 mod 691

498217

= 498128+64+16+8+1

= 498128⋅49864⋅49816⋅4988⋅4981

328 ⋅ 49 ⋅ 484 ⋅ 22 ⋅ 498 mod 691
16072 ⋅ 484 ⋅ 22 ⋅ 498 mod 691 ≡ 179 ⋅ 484 ⋅ 22 ⋅ 498 mod 691
86636 ⋅ 22 ⋅ 498 mod 691 ≡ 261 ⋅ 22 ⋅ 498 mod 691
5742 ⋅ 498 mod 691 ≡ 214 ⋅ 498 mod 691
106572 mod 691 ≡ 158 mod 691

Es gilt also: 498217 ≡ 158 mod 691

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>83 = 1⋅50 + 33
=>50 = 1⋅33 + 17
=>33 = 1⋅17 + 16
=>17 = 1⋅16 + 1
=>16 = 16⋅1 + 0

also gilt: ggt(83,50)=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= 17-1⋅16
16= 33-1⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -1⋅(33 -1⋅ 17)
= 1⋅17 -1⋅33 +1⋅ 17)
= -1⋅33 +2⋅ 17 (=1)
17= 50-1⋅33 eingesetzt in die Zeile drüber: 1 = -1⋅33 +2⋅(50 -1⋅ 33)
= -1⋅33 +2⋅50 -2⋅ 33)
= 2⋅50 -3⋅ 33 (=1)
33= 83-1⋅50 eingesetzt in die Zeile drüber: 1 = 2⋅50 -3⋅(83 -1⋅ 50)
= 2⋅50 -3⋅83 +3⋅ 50)
= -3⋅83 +5⋅ 50 (=1)

Es gilt also: ggt(83,50)=1 = -3⋅83 +5⋅50

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

1 +3⋅83 = +5⋅50

Es gilt also: 5⋅50 = 3⋅83 +1

Somit 5⋅50 = 1 mod 83

5 ist also das Inverse von 50 mod 83

Schlüsselpaar für RSA

Beispiel:

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