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: (19996 - 995) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(19996 - 995) mod 5 ≡ (19996 mod 5 - 995 mod 5) mod 5.

19996 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 19996 = 19000+996 = 5 ⋅ 3800 +996.

995 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 995 = 900+95 = 5 ⋅ 180 +95.

Somit gilt:

(19996 - 995) mod 5 ≡ (1 - 0) mod 5 ≡ 1 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (22 ⋅ 16) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(22 ⋅ 16) mod 8 ≡ (22 mod 8 ⋅ 16 mod 8) mod 8.

22 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 22 = 16 + 6 = 2 ⋅ 8 + 6 ist.

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

Somit gilt:

(22 ⋅ 16) mod 8 ≡ (6 ⋅ 0) mod 8 ≡ 0 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 11816 mod 229.

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. 118 -> x
2. mod(x²,229) -> 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: 1181=118

2: 1182=1181+1=1181⋅1181 ≡ 118⋅118=13924 ≡ 184 mod 229

4: 1184=1182+2=1182⋅1182 ≡ 184⋅184=33856 ≡ 193 mod 229

8: 1188=1184+4=1184⋅1184 ≡ 193⋅193=37249 ≡ 151 mod 229

16: 11816=1188+8=1188⋅1188 ≡ 151⋅151=22801 ≡ 130 mod 229

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 24471 mod 331.

Lösung einblenden

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

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

71 = 64+4+2+1

1: 2441=244

2: 2442=2441+1=2441⋅2441 ≡ 244⋅244=59536 ≡ 287 mod 331

4: 2444=2442+2=2442⋅2442 ≡ 287⋅287=82369 ≡ 281 mod 331

8: 2448=2444+4=2444⋅2444 ≡ 281⋅281=78961 ≡ 183 mod 331

16: 24416=2448+8=2448⋅2448 ≡ 183⋅183=33489 ≡ 58 mod 331

32: 24432=24416+16=24416⋅24416 ≡ 58⋅58=3364 ≡ 54 mod 331

64: 24464=24432+32=24432⋅24432 ≡ 54⋅54=2916 ≡ 268 mod 331

24471

= 24464+4+2+1

= 24464⋅2444⋅2442⋅2441

268 ⋅ 281 ⋅ 287 ⋅ 244 mod 331
75308 ⋅ 287 ⋅ 244 mod 331 ≡ 171 ⋅ 287 ⋅ 244 mod 331
49077 ⋅ 244 mod 331 ≡ 89 ⋅ 244 mod 331
21716 mod 331 ≡ 201 mod 331

Es gilt also: 24471 ≡ 201 mod 331

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 36 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 36

=>89 = 2⋅36 + 17
=>36 = 2⋅17 + 2
=>17 = 8⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(89,36)=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-8⋅2
2= 36-2⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -8⋅(36 -2⋅ 17)
= 1⋅17 -8⋅36 +16⋅ 17)
= -8⋅36 +17⋅ 17 (=1)
17= 89-2⋅36 eingesetzt in die Zeile drüber: 1 = -8⋅36 +17⋅(89 -2⋅ 36)
= -8⋅36 +17⋅89 -34⋅ 36)
= 17⋅89 -42⋅ 36 (=1)

Es gilt also: ggt(89,36)=1 = 17⋅89 -42⋅36

oder wenn man 17⋅89 auf die linke Seite bringt:

1 -17⋅89 = -42⋅36

-42⋅36 = -17⋅89 + 1 |+89⋅36

-42⋅36 + 89⋅36 = -17⋅89 + 89⋅36 + 1

(-42 + 89) ⋅ 36 = (-17 + 36) ⋅ 89 + 1

47⋅36 = 19⋅89 + 1

Es gilt also: 47⋅36 = 19⋅89 +1

Somit 47⋅36 = 1 mod 89

47 ist also das Inverse von 36 mod 89

Schlüsselpaar für RSA

Beispiel:

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