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: (3000 + 1503) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3000 + 1503) mod 3 ≡ (3000 mod 3 + 1503 mod 3) mod 3.

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

1503 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 1503 = 1500+3 = 3 ⋅ 500 +3.

Somit gilt:

(3000 + 1503) mod 3 ≡ (0 + 0) mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (99 ⋅ 23) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(99 ⋅ 23) mod 7 ≡ (99 mod 7 ⋅ 23 mod 7) mod 7.

99 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 99 = 98 + 1 = 14 ⋅ 7 + 1 ist.

23 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 23 = 21 + 2 = 3 ⋅ 7 + 2 ist.

Somit gilt:

(99 ⋅ 23) mod 7 ≡ (1 ⋅ 2) mod 7 ≡ 2 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 32732 mod 331.

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. 327 -> x
2. mod(x²,331) -> 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: 3271=327

2: 3272=3271+1=3271⋅3271 ≡ 327⋅327=106929 ≡ 16 mod 331

4: 3274=3272+2=3272⋅3272 ≡ 16⋅16=256 ≡ 256 mod 331

8: 3278=3274+4=3274⋅3274 ≡ 256⋅256=65536 ≡ 329 mod 331

16: 32716=3278+8=3278⋅3278 ≡ 329⋅329=108241 ≡ 4 mod 331

32: 32732=32716+16=32716⋅32716 ≡ 4⋅4=16 ≡ 16 mod 331

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 779242 mod 883.

Lösung einblenden

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

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

242 = 128+64+32+16+2

1: 7791=779

2: 7792=7791+1=7791⋅7791 ≡ 779⋅779=606841 ≡ 220 mod 883

4: 7794=7792+2=7792⋅7792 ≡ 220⋅220=48400 ≡ 718 mod 883

8: 7798=7794+4=7794⋅7794 ≡ 718⋅718=515524 ≡ 735 mod 883

16: 77916=7798+8=7798⋅7798 ≡ 735⋅735=540225 ≡ 712 mod 883

32: 77932=77916+16=77916⋅77916 ≡ 712⋅712=506944 ≡ 102 mod 883

64: 77964=77932+32=77932⋅77932 ≡ 102⋅102=10404 ≡ 691 mod 883

128: 779128=77964+64=77964⋅77964 ≡ 691⋅691=477481 ≡ 661 mod 883

779242

= 779128+64+32+16+2

= 779128⋅77964⋅77932⋅77916⋅7792

661 ⋅ 691 ⋅ 102 ⋅ 712 ⋅ 220 mod 883
456751 ⋅ 102 ⋅ 712 ⋅ 220 mod 883 ≡ 240 ⋅ 102 ⋅ 712 ⋅ 220 mod 883
24480 ⋅ 712 ⋅ 220 mod 883 ≡ 639 ⋅ 712 ⋅ 220 mod 883
454968 ⋅ 220 mod 883 ≡ 223 ⋅ 220 mod 883
49060 mod 883 ≡ 495 mod 883

Es gilt also: 779242 ≡ 495 mod 883

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 54 ⋅ x ≡ 1 mod 71 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 71 und 54

=>71 = 1⋅54 + 17
=>54 = 3⋅17 + 3
=>17 = 5⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(71,54)=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= 3-1⋅2
2= 17-5⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(17 -5⋅ 3)
= 1⋅3 -1⋅17 +5⋅ 3)
= -1⋅17 +6⋅ 3 (=1)
3= 54-3⋅17 eingesetzt in die Zeile drüber: 1 = -1⋅17 +6⋅(54 -3⋅ 17)
= -1⋅17 +6⋅54 -18⋅ 17)
= 6⋅54 -19⋅ 17 (=1)
17= 71-1⋅54 eingesetzt in die Zeile drüber: 1 = 6⋅54 -19⋅(71 -1⋅ 54)
= 6⋅54 -19⋅71 +19⋅ 54)
= -19⋅71 +25⋅ 54 (=1)

Es gilt also: ggt(71,54)=1 = -19⋅71 +25⋅54

oder wenn man -19⋅71 auf die linke Seite bringt:

1 +19⋅71 = +25⋅54

Es gilt also: 25⋅54 = 19⋅71 +1

Somit 25⋅54 = 1 mod 71

25 ist also das Inverse von 54 mod 71

Schlüsselpaar für RSA

Beispiel:

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