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: (8998 - 5998) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(8998 - 5998) mod 3 ≡ (8998 mod 3 - 5998 mod 3) mod 3.

8998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 8998 = 9000-2 = 3 ⋅ 3000 -2 = 3 ⋅ 3000 - 3 + 1.

5998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 5998 = 6000-2 = 3 ⋅ 2000 -2 = 3 ⋅ 2000 - 3 + 1.

Somit gilt:

(8998 - 5998) mod 3 ≡ (1 - 1) mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (18 ⋅ 75) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(18 ⋅ 75) mod 11 ≡ (18 mod 11 ⋅ 75 mod 11) mod 11.

18 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 18 = 11 + 7 = 1 ⋅ 11 + 7 ist.

75 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 75 = 66 + 9 = 6 ⋅ 11 + 9 ist.

Somit gilt:

(18 ⋅ 75) mod 11 ≡ (7 ⋅ 9) mod 11 ≡ 63 mod 11 ≡ 8 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 35432 mod 457.

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. 354 -> x
2. mod(x²,457) -> 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: 3541=354

2: 3542=3541+1=3541⋅3541 ≡ 354⋅354=125316 ≡ 98 mod 457

4: 3544=3542+2=3542⋅3542 ≡ 98⋅98=9604 ≡ 7 mod 457

8: 3548=3544+4=3544⋅3544 ≡ 7⋅7=49 ≡ 49 mod 457

16: 35416=3548+8=3548⋅3548 ≡ 49⋅49=2401 ≡ 116 mod 457

32: 35432=35416+16=35416⋅35416 ≡ 116⋅116=13456 ≡ 203 mod 457

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 383151 mod 587.

Lösung einblenden

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

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

151 = 128+16+4+2+1

1: 3831=383

2: 3832=3831+1=3831⋅3831 ≡ 383⋅383=146689 ≡ 526 mod 587

4: 3834=3832+2=3832⋅3832 ≡ 526⋅526=276676 ≡ 199 mod 587

8: 3838=3834+4=3834⋅3834 ≡ 199⋅199=39601 ≡ 272 mod 587

16: 38316=3838+8=3838⋅3838 ≡ 272⋅272=73984 ≡ 22 mod 587

32: 38332=38316+16=38316⋅38316 ≡ 22⋅22=484 ≡ 484 mod 587

64: 38364=38332+32=38332⋅38332 ≡ 484⋅484=234256 ≡ 43 mod 587

128: 383128=38364+64=38364⋅38364 ≡ 43⋅43=1849 ≡ 88 mod 587

383151

= 383128+16+4+2+1

= 383128⋅38316⋅3834⋅3832⋅3831

88 ⋅ 22 ⋅ 199 ⋅ 526 ⋅ 383 mod 587
1936 ⋅ 199 ⋅ 526 ⋅ 383 mod 587 ≡ 175 ⋅ 199 ⋅ 526 ⋅ 383 mod 587
34825 ⋅ 526 ⋅ 383 mod 587 ≡ 192 ⋅ 526 ⋅ 383 mod 587
100992 ⋅ 383 mod 587 ≡ 28 ⋅ 383 mod 587
10724 mod 587 ≡ 158 mod 587

Es gilt also: 383151 ≡ 158 mod 587

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 44 ⋅ x ≡ 1 mod 67 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 67 und 44

=>67 = 1⋅44 + 23
=>44 = 1⋅23 + 21
=>23 = 1⋅21 + 2
=>21 = 10⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(67,44)=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-10⋅2
2= 23-1⋅21 eingesetzt in die Zeile drüber: 1 = 1⋅21 -10⋅(23 -1⋅ 21)
= 1⋅21 -10⋅23 +10⋅ 21)
= -10⋅23 +11⋅ 21 (=1)
21= 44-1⋅23 eingesetzt in die Zeile drüber: 1 = -10⋅23 +11⋅(44 -1⋅ 23)
= -10⋅23 +11⋅44 -11⋅ 23)
= 11⋅44 -21⋅ 23 (=1)
23= 67-1⋅44 eingesetzt in die Zeile drüber: 1 = 11⋅44 -21⋅(67 -1⋅ 44)
= 11⋅44 -21⋅67 +21⋅ 44)
= -21⋅67 +32⋅ 44 (=1)

Es gilt also: ggt(67,44)=1 = -21⋅67 +32⋅44

oder wenn man -21⋅67 auf die linke Seite bringt:

1 +21⋅67 = +32⋅44

Es gilt also: 32⋅44 = 21⋅67 +1

Somit 32⋅44 = 1 mod 67

32 ist also das Inverse von 44 mod 67

Schlüsselpaar für RSA

Beispiel:

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