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: (269 + 2697) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(269 + 2697) mod 9 ≡ (269 mod 9 + 2697 mod 9) mod 9.

269 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 269 = 270-1 = 9 ⋅ 30 -1 = 9 ⋅ 30 - 9 + 8.

2697 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 2697 = 2700-3 = 9 ⋅ 300 -3 = 9 ⋅ 300 - 9 + 6.

Somit gilt:

(269 + 2697) mod 9 ≡ (8 + 6) mod 9 ≡ 14 mod 9 ≡ 5 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (70 ⋅ 61) mod 8.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 61) mod 8 ≡ (70 mod 8 ⋅ 61 mod 8) mod 8.

70 mod 8 ≡ 6 mod 8 kann man relativ leicht bestimmen, weil ja 70 = 64 + 6 = 8 ⋅ 8 + 6 ist.

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

Somit gilt:

(70 ⋅ 61) mod 8 ≡ (6 ⋅ 5) mod 8 ≡ 30 mod 8 ≡ 6 mod 8.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 8164 mod 227.

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. 81 -> x
2. mod(x²,227) -> 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: 811=81

2: 812=811+1=811⋅811 ≡ 81⋅81=6561 ≡ 205 mod 227

4: 814=812+2=812⋅812 ≡ 205⋅205=42025 ≡ 30 mod 227

8: 818=814+4=814⋅814 ≡ 30⋅30=900 ≡ 219 mod 227

16: 8116=818+8=818⋅818 ≡ 219⋅219=47961 ≡ 64 mod 227

32: 8132=8116+16=8116⋅8116 ≡ 64⋅64=4096 ≡ 10 mod 227

64: 8164=8132+32=8132⋅8132 ≡ 10⋅10=100 ≡ 100 mod 227

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 26771 mod 601.

Lösung einblenden

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

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

71 = 64+4+2+1

1: 2671=267

2: 2672=2671+1=2671⋅2671 ≡ 267⋅267=71289 ≡ 371 mod 601

4: 2674=2672+2=2672⋅2672 ≡ 371⋅371=137641 ≡ 12 mod 601

8: 2678=2674+4=2674⋅2674 ≡ 12⋅12=144 ≡ 144 mod 601

16: 26716=2678+8=2678⋅2678 ≡ 144⋅144=20736 ≡ 302 mod 601

32: 26732=26716+16=26716⋅26716 ≡ 302⋅302=91204 ≡ 453 mod 601

64: 26764=26732+32=26732⋅26732 ≡ 453⋅453=205209 ≡ 268 mod 601

26771

= 26764+4+2+1

= 26764⋅2674⋅2672⋅2671

268 ⋅ 12 ⋅ 371 ⋅ 267 mod 601
3216 ⋅ 371 ⋅ 267 mod 601 ≡ 211 ⋅ 371 ⋅ 267 mod 601
78281 ⋅ 267 mod 601 ≡ 151 ⋅ 267 mod 601
40317 mod 601 ≡ 50 mod 601

Es gilt also: 26771 ≡ 50 mod 601

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 52 ⋅ x ≡ 1 mod 61 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 61 und 52

=>61 = 1⋅52 + 9
=>52 = 5⋅9 + 7
=>9 = 1⋅7 + 2
=>7 = 3⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(61,52)=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= 7-3⋅2
2= 9-1⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -3⋅(9 -1⋅ 7)
= 1⋅7 -3⋅9 +3⋅ 7)
= -3⋅9 +4⋅ 7 (=1)
7= 52-5⋅9 eingesetzt in die Zeile drüber: 1 = -3⋅9 +4⋅(52 -5⋅ 9)
= -3⋅9 +4⋅52 -20⋅ 9)
= 4⋅52 -23⋅ 9 (=1)
9= 61-1⋅52 eingesetzt in die Zeile drüber: 1 = 4⋅52 -23⋅(61 -1⋅ 52)
= 4⋅52 -23⋅61 +23⋅ 52)
= -23⋅61 +27⋅ 52 (=1)

Es gilt also: ggt(61,52)=1 = -23⋅61 +27⋅52

oder wenn man -23⋅61 auf die linke Seite bringt:

1 +23⋅61 = +27⋅52

Es gilt also: 27⋅52 = 23⋅61 +1

Somit 27⋅52 = 1 mod 61

27 ist also das Inverse von 52 mod 61

Schlüsselpaar für RSA

Beispiel:

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