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: (8000 + 318) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(8000 + 318) mod 8 ≡ (8000 mod 8 + 318 mod 8) mod 8.

8000 mod 8 ≡ 0 mod 8 kann man relativ leicht bestimmen, weil ja 8000 = 8000+0 = 8 ⋅ 1000 +0.

318 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 318 = 320-2 = 8 ⋅ 40 -2 = 8 ⋅ 40 - 8 + 6.

Somit gilt:

(8000 + 318) mod 8 ≡ (0 + 6) mod 8 ≡ 6 mod 8.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (17 ⋅ 48) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(17 ⋅ 48) mod 4 ≡ (17 mod 4 ⋅ 48 mod 4) mod 4.

17 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 17 = 16 + 1 = 4 ⋅ 4 + 1 ist.

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

Somit gilt:

(17 ⋅ 48) mod 4 ≡ (1 ⋅ 0) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 53716 mod 997.

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. 537 -> x
2. mod(x²,997) -> 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: 5371=537

2: 5372=5371+1=5371⋅5371 ≡ 537⋅537=288369 ≡ 236 mod 997

4: 5374=5372+2=5372⋅5372 ≡ 236⋅236=55696 ≡ 861 mod 997

8: 5378=5374+4=5374⋅5374 ≡ 861⋅861=741321 ≡ 550 mod 997

16: 53716=5378+8=5378⋅5378 ≡ 550⋅550=302500 ≡ 409 mod 997

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 148254 mod 263.

Lösung einblenden

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

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

254 = 128+64+32+16+8+4+2

1: 1481=148

2: 1482=1481+1=1481⋅1481 ≡ 148⋅148=21904 ≡ 75 mod 263

4: 1484=1482+2=1482⋅1482 ≡ 75⋅75=5625 ≡ 102 mod 263

8: 1488=1484+4=1484⋅1484 ≡ 102⋅102=10404 ≡ 147 mod 263

16: 14816=1488+8=1488⋅1488 ≡ 147⋅147=21609 ≡ 43 mod 263

32: 14832=14816+16=14816⋅14816 ≡ 43⋅43=1849 ≡ 8 mod 263

64: 14864=14832+32=14832⋅14832 ≡ 8⋅8=64 ≡ 64 mod 263

128: 148128=14864+64=14864⋅14864 ≡ 64⋅64=4096 ≡ 151 mod 263

148254

= 148128+64+32+16+8+4+2

= 148128⋅14864⋅14832⋅14816⋅1488⋅1484⋅1482

151 ⋅ 64 ⋅ 8 ⋅ 43 ⋅ 147 ⋅ 102 ⋅ 75 mod 263
9664 ⋅ 8 ⋅ 43 ⋅ 147 ⋅ 102 ⋅ 75 mod 263 ≡ 196 ⋅ 8 ⋅ 43 ⋅ 147 ⋅ 102 ⋅ 75 mod 263
1568 ⋅ 43 ⋅ 147 ⋅ 102 ⋅ 75 mod 263 ≡ 253 ⋅ 43 ⋅ 147 ⋅ 102 ⋅ 75 mod 263
10879 ⋅ 147 ⋅ 102 ⋅ 75 mod 263 ≡ 96 ⋅ 147 ⋅ 102 ⋅ 75 mod 263
14112 ⋅ 102 ⋅ 75 mod 263 ≡ 173 ⋅ 102 ⋅ 75 mod 263
17646 ⋅ 75 mod 263 ≡ 25 ⋅ 75 mod 263
1875 mod 263 ≡ 34 mod 263

Es gilt also: 148254 ≡ 34 mod 263

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 32 ⋅ x ≡ 1 mod 59 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 59 und 32

=>59 = 1⋅32 + 27
=>32 = 1⋅27 + 5
=>27 = 5⋅5 + 2
=>5 = 2⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(59,32)=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= 5-2⋅2
2= 27-5⋅5 eingesetzt in die Zeile drüber: 1 = 1⋅5 -2⋅(27 -5⋅ 5)
= 1⋅5 -2⋅27 +10⋅ 5)
= -2⋅27 +11⋅ 5 (=1)
5= 32-1⋅27 eingesetzt in die Zeile drüber: 1 = -2⋅27 +11⋅(32 -1⋅ 27)
= -2⋅27 +11⋅32 -11⋅ 27)
= 11⋅32 -13⋅ 27 (=1)
27= 59-1⋅32 eingesetzt in die Zeile drüber: 1 = 11⋅32 -13⋅(59 -1⋅ 32)
= 11⋅32 -13⋅59 +13⋅ 32)
= -13⋅59 +24⋅ 32 (=1)

Es gilt also: ggt(59,32)=1 = -13⋅59 +24⋅32

oder wenn man -13⋅59 auf die linke Seite bringt:

1 +13⋅59 = +24⋅32

Es gilt also: 24⋅32 = 13⋅59 +1

Somit 24⋅32 = 1 mod 59

24 ist also das Inverse von 32 mod 59

Schlüsselpaar für RSA

Beispiel:

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