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: (34996 + 14005) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(34996 + 14005) mod 7 ≡ (34996 mod 7 + 14005 mod 7) mod 7.

34996 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 34996 = 35000-4 = 7 ⋅ 5000 -4 = 7 ⋅ 5000 - 7 + 3.

14005 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 14005 = 14000+5 = 7 ⋅ 2000 +5.

Somit gilt:

(34996 + 14005) mod 7 ≡ (3 + 5) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (43 ⋅ 60) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(43 ⋅ 60) mod 4 ≡ (43 mod 4 ⋅ 60 mod 4) mod 4.

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

60 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 60 = 60 + 0 = 15 ⋅ 4 + 0 ist.

Somit gilt:

(43 ⋅ 60) mod 4 ≡ (3 ⋅ 0) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 42732 mod 443.

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. 427 -> x
2. mod(x²,443) -> 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: 4271=427

2: 4272=4271+1=4271⋅4271 ≡ 427⋅427=182329 ≡ 256 mod 443

4: 4274=4272+2=4272⋅4272 ≡ 256⋅256=65536 ≡ 415 mod 443

8: 4278=4274+4=4274⋅4274 ≡ 415⋅415=172225 ≡ 341 mod 443

16: 42716=4278+8=4278⋅4278 ≡ 341⋅341=116281 ≡ 215 mod 443

32: 42732=42716+16=42716⋅42716 ≡ 215⋅215=46225 ≡ 153 mod 443

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 454103 mod 821.

Lösung einblenden

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

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

103 = 64+32+4+2+1

1: 4541=454

2: 4542=4541+1=4541⋅4541 ≡ 454⋅454=206116 ≡ 45 mod 821

4: 4544=4542+2=4542⋅4542 ≡ 45⋅45=2025 ≡ 383 mod 821

8: 4548=4544+4=4544⋅4544 ≡ 383⋅383=146689 ≡ 551 mod 821

16: 45416=4548+8=4548⋅4548 ≡ 551⋅551=303601 ≡ 652 mod 821

32: 45432=45416+16=45416⋅45416 ≡ 652⋅652=425104 ≡ 647 mod 821

64: 45464=45432+32=45432⋅45432 ≡ 647⋅647=418609 ≡ 720 mod 821

454103

= 45464+32+4+2+1

= 45464⋅45432⋅4544⋅4542⋅4541

720 ⋅ 647 ⋅ 383 ⋅ 45 ⋅ 454 mod 821
465840 ⋅ 383 ⋅ 45 ⋅ 454 mod 821 ≡ 333 ⋅ 383 ⋅ 45 ⋅ 454 mod 821
127539 ⋅ 45 ⋅ 454 mod 821 ≡ 284 ⋅ 45 ⋅ 454 mod 821
12780 ⋅ 454 mod 821 ≡ 465 ⋅ 454 mod 821
211110 mod 821 ≡ 113 mod 821

Es gilt also: 454103 ≡ 113 mod 821

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

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

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

Es gilt also: ggt(83,33)=1 = 2⋅83 -5⋅33

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

1 -2⋅83 = -5⋅33

-5⋅33 = -2⋅83 + 1 |+83⋅33

-5⋅33 + 83⋅33 = -2⋅83 + 83⋅33 + 1

(-5 + 83) ⋅ 33 = (-2 + 33) ⋅ 83 + 1

78⋅33 = 31⋅83 + 1

Es gilt also: 78⋅33 = 31⋅83 +1

Somit 78⋅33 = 1 mod 83

78 ist also das Inverse von 33 mod 83

Schlüsselpaar für RSA

Beispiel:

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