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: (701 + 2102) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(701 + 2102) mod 7 ≡ (701 mod 7 + 2102 mod 7) mod 7.

701 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 701 = 700+1 = 7 ⋅ 100 +1.

2102 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 2102 = 2100+2 = 7 ⋅ 300 +2.

Somit gilt:

(701 + 2102) mod 7 ≡ (1 + 2) mod 7 ≡ 3 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (64 ⋅ 88) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(64 ⋅ 88) mod 7 ≡ (64 mod 7 ⋅ 88 mod 7) mod 7.

64 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 64 = 63 + 1 = 9 ⋅ 7 + 1 ist.

88 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 88 = 84 + 4 = 12 ⋅ 7 + 4 ist.

Somit gilt:

(64 ⋅ 88) mod 7 ≡ (1 ⋅ 4) mod 7 ≡ 4 mod 7.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 41664 mod 617.

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. 416 -> x
2. mod(x²,617) -> 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: 4161=416

2: 4162=4161+1=4161⋅4161 ≡ 416⋅416=173056 ≡ 296 mod 617

4: 4164=4162+2=4162⋅4162 ≡ 296⋅296=87616 ≡ 2 mod 617

8: 4168=4164+4=4164⋅4164 ≡ 2⋅2=4 ≡ 4 mod 617

16: 41616=4168+8=4168⋅4168 ≡ 4⋅4=16 ≡ 16 mod 617

32: 41632=41616+16=41616⋅41616 ≡ 16⋅16=256 ≡ 256 mod 617

64: 41664=41632+32=41632⋅41632 ≡ 256⋅256=65536 ≡ 134 mod 617

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 369170 mod 839.

Lösung einblenden

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

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

170 = 128+32+8+2

1: 3691=369

2: 3692=3691+1=3691⋅3691 ≡ 369⋅369=136161 ≡ 243 mod 839

4: 3694=3692+2=3692⋅3692 ≡ 243⋅243=59049 ≡ 319 mod 839

8: 3698=3694+4=3694⋅3694 ≡ 319⋅319=101761 ≡ 242 mod 839

16: 36916=3698+8=3698⋅3698 ≡ 242⋅242=58564 ≡ 673 mod 839

32: 36932=36916+16=36916⋅36916 ≡ 673⋅673=452929 ≡ 708 mod 839

64: 36964=36932+32=36932⋅36932 ≡ 708⋅708=501264 ≡ 381 mod 839

128: 369128=36964+64=36964⋅36964 ≡ 381⋅381=145161 ≡ 14 mod 839

369170

= 369128+32+8+2

= 369128⋅36932⋅3698⋅3692

14 ⋅ 708 ⋅ 242 ⋅ 243 mod 839
9912 ⋅ 242 ⋅ 243 mod 839 ≡ 683 ⋅ 242 ⋅ 243 mod 839
165286 ⋅ 243 mod 839 ≡ 3 ⋅ 243 mod 839
729 mod 839

Es gilt also: 369170 ≡ 729 mod 839

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>101 = 1⋅59 + 42
=>59 = 1⋅42 + 17
=>42 = 2⋅17 + 8
=>17 = 2⋅8 + 1
=>8 = 8⋅1 + 0

also gilt: ggt(101,59)=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= 17-2⋅8
8= 42-2⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -2⋅(42 -2⋅ 17)
= 1⋅17 -2⋅42 +4⋅ 17)
= -2⋅42 +5⋅ 17 (=1)
17= 59-1⋅42 eingesetzt in die Zeile drüber: 1 = -2⋅42 +5⋅(59 -1⋅ 42)
= -2⋅42 +5⋅59 -5⋅ 42)
= 5⋅59 -7⋅ 42 (=1)
42= 101-1⋅59 eingesetzt in die Zeile drüber: 1 = 5⋅59 -7⋅(101 -1⋅ 59)
= 5⋅59 -7⋅101 +7⋅ 59)
= -7⋅101 +12⋅ 59 (=1)

Es gilt also: ggt(101,59)=1 = -7⋅101 +12⋅59

oder wenn man -7⋅101 auf die linke Seite bringt:

1 +7⋅101 = +12⋅59

Es gilt also: 12⋅59 = 7⋅101 +1

Somit 12⋅59 = 1 mod 101

12 ist also das Inverse von 59 mod 101

Schlüsselpaar für RSA

Beispiel:

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