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: (2498 - 505) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2498 - 505) mod 5 ≡ (2498 mod 5 - 505 mod 5) mod 5.

2498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 2498 = 2400+98 = 5 ⋅ 480 +98.

505 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 505 = 500+5 = 5 ⋅ 100 +5.

Somit gilt:

(2498 - 505) mod 5 ≡ (3 - 0) mod 5 ≡ 3 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (27 ⋅ 19) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(27 ⋅ 19) mod 10 ≡ (27 mod 10 ⋅ 19 mod 10) mod 10.

27 mod 10 ≡ 7 mod 10 kann man relativ leicht bestimmen, weil ja 27 = 20 + 7 = 2 ⋅ 10 + 7 ist.

19 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 19 = 10 + 9 = 1 ⋅ 10 + 9 ist.

Somit gilt:

(27 ⋅ 19) mod 10 ≡ (7 ⋅ 9) mod 10 ≡ 63 mod 10 ≡ 3 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 7748 mod 823.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 774 -> x
2. mod(x²,823) -> 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: 7741=774

2: 7742=7741+1=7741⋅7741 ≡ 774⋅774=599076 ≡ 755 mod 823

4: 7744=7742+2=7742⋅7742 ≡ 755⋅755=570025 ≡ 509 mod 823

8: 7748=7744+4=7744⋅7744 ≡ 509⋅509=259081 ≡ 659 mod 823

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 476171 mod 499.

Lösung einblenden

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

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

171 = 128+32+8+2+1

1: 4761=476

2: 4762=4761+1=4761⋅4761 ≡ 476⋅476=226576 ≡ 30 mod 499

4: 4764=4762+2=4762⋅4762 ≡ 30⋅30=900 ≡ 401 mod 499

8: 4768=4764+4=4764⋅4764 ≡ 401⋅401=160801 ≡ 123 mod 499

16: 47616=4768+8=4768⋅4768 ≡ 123⋅123=15129 ≡ 159 mod 499

32: 47632=47616+16=47616⋅47616 ≡ 159⋅159=25281 ≡ 331 mod 499

64: 47664=47632+32=47632⋅47632 ≡ 331⋅331=109561 ≡ 280 mod 499

128: 476128=47664+64=47664⋅47664 ≡ 280⋅280=78400 ≡ 57 mod 499

476171

= 476128+32+8+2+1

= 476128⋅47632⋅4768⋅4762⋅4761

57 ⋅ 331 ⋅ 123 ⋅ 30 ⋅ 476 mod 499
18867 ⋅ 123 ⋅ 30 ⋅ 476 mod 499 ≡ 404 ⋅ 123 ⋅ 30 ⋅ 476 mod 499
49692 ⋅ 30 ⋅ 476 mod 499 ≡ 291 ⋅ 30 ⋅ 476 mod 499
8730 ⋅ 476 mod 499 ≡ 247 ⋅ 476 mod 499
117572 mod 499 ≡ 307 mod 499

Es gilt also: 476171 ≡ 307 mod 499

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>71 = 1⋅62 + 9
=>62 = 6⋅9 + 8
=>9 = 1⋅8 + 1
=>8 = 8⋅1 + 0

also gilt: ggt(71,62)=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= 9-1⋅8
8= 62-6⋅9 eingesetzt in die Zeile drüber: 1 = 1⋅9 -1⋅(62 -6⋅ 9)
= 1⋅9 -1⋅62 +6⋅ 9)
= -1⋅62 +7⋅ 9 (=1)
9= 71-1⋅62 eingesetzt in die Zeile drüber: 1 = -1⋅62 +7⋅(71 -1⋅ 62)
= -1⋅62 +7⋅71 -7⋅ 62)
= 7⋅71 -8⋅ 62 (=1)

Es gilt also: ggt(71,62)=1 = 7⋅71 -8⋅62

oder wenn man 7⋅71 auf die linke Seite bringt:

1 -7⋅71 = -8⋅62

-8⋅62 = -7⋅71 + 1 |+71⋅62

-8⋅62 + 71⋅62 = -7⋅71 + 71⋅62 + 1

(-8 + 71) ⋅ 62 = (-7 + 62) ⋅ 71 + 1

63⋅62 = 55⋅71 + 1

Es gilt also: 63⋅62 = 55⋅71 +1

Somit 63⋅62 = 1 mod 71

63 ist also das Inverse von 62 mod 71

Schlüsselpaar für RSA

Beispiel:

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