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: (282 - 1397) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(282 - 1397) mod 7 ≡ (282 mod 7 - 1397 mod 7) mod 7.

282 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 282 = 280+2 = 7 ⋅ 40 +2.

1397 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 1397 = 1400-3 = 7 ⋅ 200 -3 = 7 ⋅ 200 - 7 + 4.

Somit gilt:

(282 - 1397) mod 7 ≡ (2 - 4) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (49 ⋅ 47) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(49 ⋅ 47) mod 8 ≡ (49 mod 8 ⋅ 47 mod 8) mod 8.

49 mod 8 ≡ 1 mod 8 kann man relativ leicht bestimmen, weil ja 49 = 48 + 1 = 6 ⋅ 8 + 1 ist.

47 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 47 = 40 + 7 = 5 ⋅ 8 + 7 ist.

Somit gilt:

(49 ⋅ 47) mod 8 ≡ (1 ⋅ 7) mod 8 ≡ 7 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 2468 mod 337.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 246 -> x
2. mod(x²,337) -> 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: 2461=246

2: 2462=2461+1=2461⋅2461 ≡ 246⋅246=60516 ≡ 193 mod 337

4: 2464=2462+2=2462⋅2462 ≡ 193⋅193=37249 ≡ 179 mod 337

8: 2468=2464+4=2464⋅2464 ≡ 179⋅179=32041 ≡ 26 mod 337

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 348238 mod 619.

Lösung einblenden

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

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

238 = 128+64+32+8+4+2

1: 3481=348

2: 3482=3481+1=3481⋅3481 ≡ 348⋅348=121104 ≡ 399 mod 619

4: 3484=3482+2=3482⋅3482 ≡ 399⋅399=159201 ≡ 118 mod 619

8: 3488=3484+4=3484⋅3484 ≡ 118⋅118=13924 ≡ 306 mod 619

16: 34816=3488+8=3488⋅3488 ≡ 306⋅306=93636 ≡ 167 mod 619

32: 34832=34816+16=34816⋅34816 ≡ 167⋅167=27889 ≡ 34 mod 619

64: 34864=34832+32=34832⋅34832 ≡ 34⋅34=1156 ≡ 537 mod 619

128: 348128=34864+64=34864⋅34864 ≡ 537⋅537=288369 ≡ 534 mod 619

348238

= 348128+64+32+8+4+2

= 348128⋅34864⋅34832⋅3488⋅3484⋅3482

534 ⋅ 537 ⋅ 34 ⋅ 306 ⋅ 118 ⋅ 399 mod 619
286758 ⋅ 34 ⋅ 306 ⋅ 118 ⋅ 399 mod 619 ≡ 161 ⋅ 34 ⋅ 306 ⋅ 118 ⋅ 399 mod 619
5474 ⋅ 306 ⋅ 118 ⋅ 399 mod 619 ≡ 522 ⋅ 306 ⋅ 118 ⋅ 399 mod 619
159732 ⋅ 118 ⋅ 399 mod 619 ≡ 30 ⋅ 118 ⋅ 399 mod 619
3540 ⋅ 399 mod 619 ≡ 445 ⋅ 399 mod 619
177555 mod 619 ≡ 521 mod 619

Es gilt also: 348238 ≡ 521 mod 619

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 28 ⋅ x ≡ 1 mod 53 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 53 und 28

=>53 = 1⋅28 + 25
=>28 = 1⋅25 + 3
=>25 = 8⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(53,28)=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= 25-8⋅3
3= 28-1⋅25 eingesetzt in die Zeile drüber: 1 = 1⋅25 -8⋅(28 -1⋅ 25)
= 1⋅25 -8⋅28 +8⋅ 25)
= -8⋅28 +9⋅ 25 (=1)
25= 53-1⋅28 eingesetzt in die Zeile drüber: 1 = -8⋅28 +9⋅(53 -1⋅ 28)
= -8⋅28 +9⋅53 -9⋅ 28)
= 9⋅53 -17⋅ 28 (=1)

Es gilt also: ggt(53,28)=1 = 9⋅53 -17⋅28

oder wenn man 9⋅53 auf die linke Seite bringt:

1 -9⋅53 = -17⋅28

-17⋅28 = -9⋅53 + 1 |+53⋅28

-17⋅28 + 53⋅28 = -9⋅53 + 53⋅28 + 1

(-17 + 53) ⋅ 28 = (-9 + 28) ⋅ 53 + 1

36⋅28 = 19⋅53 + 1

Es gilt also: 36⋅28 = 19⋅53 +1

Somit 36⋅28 = 1 mod 53

36 ist also das Inverse von 28 mod 53

Schlüsselpaar für RSA

Beispiel:

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