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: (1501 - 1498) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1501 - 1498) mod 3 ≡ (1501 mod 3 - 1498 mod 3) mod 3.

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

1498 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 1498 = 1500-2 = 3 ⋅ 500 -2 = 3 ⋅ 500 - 3 + 1.

Somit gilt:

(1501 - 1498) mod 3 ≡ (1 - 1) mod 3 ≡ 0 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (31 ⋅ 95) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(31 ⋅ 95) mod 11 ≡ (31 mod 11 ⋅ 95 mod 11) mod 11.

31 mod 11 ≡ 9 mod 11 kann man relativ leicht bestimmen, weil ja 31 = 22 + 9 = 2 ⋅ 11 + 9 ist.

95 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 95 = 88 + 7 = 8 ⋅ 11 + 7 ist.

Somit gilt:

(31 ⋅ 95) mod 11 ≡ (9 ⋅ 7) mod 11 ≡ 63 mod 11 ≡ 8 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 20164 mod 277.

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. 201 -> x
2. mod(x²,277) -> 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: 2011=201

2: 2012=2011+1=2011⋅2011 ≡ 201⋅201=40401 ≡ 236 mod 277

4: 2014=2012+2=2012⋅2012 ≡ 236⋅236=55696 ≡ 19 mod 277

8: 2018=2014+4=2014⋅2014 ≡ 19⋅19=361 ≡ 84 mod 277

16: 20116=2018+8=2018⋅2018 ≡ 84⋅84=7056 ≡ 131 mod 277

32: 20132=20116+16=20116⋅20116 ≡ 131⋅131=17161 ≡ 264 mod 277

64: 20164=20132+32=20132⋅20132 ≡ 264⋅264=69696 ≡ 169 mod 277

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 426102 mod 967.

Lösung einblenden

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

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

102 = 64+32+4+2

1: 4261=426

2: 4262=4261+1=4261⋅4261 ≡ 426⋅426=181476 ≡ 647 mod 967

4: 4264=4262+2=4262⋅4262 ≡ 647⋅647=418609 ≡ 865 mod 967

8: 4268=4264+4=4264⋅4264 ≡ 865⋅865=748225 ≡ 734 mod 967

16: 42616=4268+8=4268⋅4268 ≡ 734⋅734=538756 ≡ 137 mod 967

32: 42632=42616+16=42616⋅42616 ≡ 137⋅137=18769 ≡ 396 mod 967

64: 42664=42632+32=42632⋅42632 ≡ 396⋅396=156816 ≡ 162 mod 967

426102

= 42664+32+4+2

= 42664⋅42632⋅4264⋅4262

162 ⋅ 396 ⋅ 865 ⋅ 647 mod 967
64152 ⋅ 865 ⋅ 647 mod 967 ≡ 330 ⋅ 865 ⋅ 647 mod 967
285450 ⋅ 647 mod 967 ≡ 185 ⋅ 647 mod 967
119695 mod 967 ≡ 754 mod 967

Es gilt also: 426102 ≡ 754 mod 967

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 46 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 46

=>89 = 1⋅46 + 43
=>46 = 1⋅43 + 3
=>43 = 14⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(89,46)=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= 43-14⋅3
3= 46-1⋅43 eingesetzt in die Zeile drüber: 1 = 1⋅43 -14⋅(46 -1⋅ 43)
= 1⋅43 -14⋅46 +14⋅ 43)
= -14⋅46 +15⋅ 43 (=1)
43= 89-1⋅46 eingesetzt in die Zeile drüber: 1 = -14⋅46 +15⋅(89 -1⋅ 46)
= -14⋅46 +15⋅89 -15⋅ 46)
= 15⋅89 -29⋅ 46 (=1)

Es gilt also: ggt(89,46)=1 = 15⋅89 -29⋅46

oder wenn man 15⋅89 auf die linke Seite bringt:

1 -15⋅89 = -29⋅46

-29⋅46 = -15⋅89 + 1 |+89⋅46

-29⋅46 + 89⋅46 = -15⋅89 + 89⋅46 + 1

(-29 + 89) ⋅ 46 = (-15 + 46) ⋅ 89 + 1

60⋅46 = 31⋅89 + 1

Es gilt also: 60⋅46 = 31⋅89 +1

Somit 60⋅46 = 1 mod 89

60 ist also das Inverse von 46 mod 89

Schlüsselpaar für RSA

Beispiel:

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