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: (12002 + 121) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(12002 + 121) mod 3 ≡ (12002 mod 3 + 121 mod 3) mod 3.

12002 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 12002 = 12000+2 = 3 ⋅ 4000 +2.

121 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 121 = 120+1 = 3 ⋅ 40 +1.

Somit gilt:

(12002 + 121) mod 3 ≡ (2 + 1) mod 3 ≡ 3 mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (70 ⋅ 20) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 20) mod 4 ≡ (70 mod 4 ⋅ 20 mod 4) mod 4.

70 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 70 = 68 + 2 = 17 ⋅ 4 + 2 ist.

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

Somit gilt:

(70 ⋅ 20) mod 4 ≡ (2 ⋅ 0) mod 4 ≡ 0 mod 4.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 40664 mod 769.

Lösung einblenden

Die 64 im Exponent ist ja ein reine 2er-Potenz (26).

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. 406 -> x
2. mod(x²,769) -> 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: 4061=406

2: 4062=4061+1=4061⋅4061 ≡ 406⋅406=164836 ≡ 270 mod 769

4: 4064=4062+2=4062⋅4062 ≡ 270⋅270=72900 ≡ 614 mod 769

8: 4068=4064+4=4064⋅4064 ≡ 614⋅614=376996 ≡ 186 mod 769

16: 40616=4068+8=4068⋅4068 ≡ 186⋅186=34596 ≡ 760 mod 769

32: 40632=40616+16=40616⋅40616 ≡ 760⋅760=577600 ≡ 81 mod 769

64: 40664=40632+32=40632⋅40632 ≡ 81⋅81=6561 ≡ 409 mod 769

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 668154 mod 821.

Lösung einblenden

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

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

154 = 128+16+8+2

1: 6681=668

2: 6682=6681+1=6681⋅6681 ≡ 668⋅668=446224 ≡ 421 mod 821

4: 6684=6682+2=6682⋅6682 ≡ 421⋅421=177241 ≡ 726 mod 821

8: 6688=6684+4=6684⋅6684 ≡ 726⋅726=527076 ≡ 815 mod 821

16: 66816=6688+8=6688⋅6688 ≡ 815⋅815=664225 ≡ 36 mod 821

32: 66832=66816+16=66816⋅66816 ≡ 36⋅36=1296 ≡ 475 mod 821

64: 66864=66832+32=66832⋅66832 ≡ 475⋅475=225625 ≡ 671 mod 821

128: 668128=66864+64=66864⋅66864 ≡ 671⋅671=450241 ≡ 333 mod 821

668154

= 668128+16+8+2

= 668128⋅66816⋅6688⋅6682

333 ⋅ 36 ⋅ 815 ⋅ 421 mod 821
11988 ⋅ 815 ⋅ 421 mod 821 ≡ 494 ⋅ 815 ⋅ 421 mod 821
402610 ⋅ 421 mod 821 ≡ 320 ⋅ 421 mod 821
134720 mod 821 ≡ 76 mod 821

Es gilt also: 668154 ≡ 76 mod 821

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 72 ⋅ x ≡ 1 mod 101 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 101 und 72

=>101 = 1⋅72 + 29
=>72 = 2⋅29 + 14
=>29 = 2⋅14 + 1
=>14 = 14⋅1 + 0

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

Es gilt also: ggt(101,72)=1 = 5⋅101 -7⋅72

oder wenn man 5⋅101 auf die linke Seite bringt:

1 -5⋅101 = -7⋅72

-7⋅72 = -5⋅101 + 1 |+101⋅72

-7⋅72 + 101⋅72 = -5⋅101 + 101⋅72 + 1

(-7 + 101) ⋅ 72 = (-5 + 72) ⋅ 101 + 1

94⋅72 = 67⋅101 + 1

Es gilt also: 94⋅72 = 67⋅101 +1

Somit 94⋅72 = 1 mod 101

94 ist also das Inverse von 72 mod 101

Schlüsselpaar für RSA

Beispiel:

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