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: (1196 - 2399) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1196 - 2399) mod 6 ≡ (1196 mod 6 - 2399 mod 6) mod 6.

1196 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 1196 = 1200-4 = 6 ⋅ 200 -4 = 6 ⋅ 200 - 6 + 2.

2399 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 2399 = 2400-1 = 6 ⋅ 400 -1 = 6 ⋅ 400 - 6 + 5.

Somit gilt:

(1196 - 2399) mod 6 ≡ (2 - 5) mod 6 ≡ -3 mod 6 ≡ 3 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (70 ⋅ 26) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(70 ⋅ 26) mod 6 ≡ (70 mod 6 ⋅ 26 mod 6) mod 6.

70 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 70 = 66 + 4 = 11 ⋅ 6 + 4 ist.

26 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 26 = 24 + 2 = 4 ⋅ 6 + 2 ist.

Somit gilt:

(70 ⋅ 26) mod 6 ≡ (4 ⋅ 2) mod 6 ≡ 8 mod 6 ≡ 2 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 342128 mod 599.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 342 -> x
2. mod(x²,599) -> 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: 3421=342

2: 3422=3421+1=3421⋅3421 ≡ 342⋅342=116964 ≡ 159 mod 599

4: 3424=3422+2=3422⋅3422 ≡ 159⋅159=25281 ≡ 123 mod 599

8: 3428=3424+4=3424⋅3424 ≡ 123⋅123=15129 ≡ 154 mod 599

16: 34216=3428+8=3428⋅3428 ≡ 154⋅154=23716 ≡ 355 mod 599

32: 34232=34216+16=34216⋅34216 ≡ 355⋅355=126025 ≡ 235 mod 599

64: 34264=34232+32=34232⋅34232 ≡ 235⋅235=55225 ≡ 117 mod 599

128: 342128=34264+64=34264⋅34264 ≡ 117⋅117=13689 ≡ 511 mod 599

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 757127 mod 991.

Lösung einblenden

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

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

127 = 64+32+16+8+4+2+1

1: 7571=757

2: 7572=7571+1=7571⋅7571 ≡ 757⋅757=573049 ≡ 251 mod 991

4: 7574=7572+2=7572⋅7572 ≡ 251⋅251=63001 ≡ 568 mod 991

8: 7578=7574+4=7574⋅7574 ≡ 568⋅568=322624 ≡ 549 mod 991

16: 75716=7578+8=7578⋅7578 ≡ 549⋅549=301401 ≡ 137 mod 991

32: 75732=75716+16=75716⋅75716 ≡ 137⋅137=18769 ≡ 931 mod 991

64: 75764=75732+32=75732⋅75732 ≡ 931⋅931=866761 ≡ 627 mod 991

757127

= 75764+32+16+8+4+2+1

= 75764⋅75732⋅75716⋅7578⋅7574⋅7572⋅7571

627 ⋅ 931 ⋅ 137 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
583737 ⋅ 137 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991 ≡ 38 ⋅ 137 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
5206 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991 ≡ 251 ⋅ 549 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
137799 ⋅ 568 ⋅ 251 ⋅ 757 mod 991 ≡ 50 ⋅ 568 ⋅ 251 ⋅ 757 mod 991
28400 ⋅ 251 ⋅ 757 mod 991 ≡ 652 ⋅ 251 ⋅ 757 mod 991
163652 ⋅ 757 mod 991 ≡ 137 ⋅ 757 mod 991
103709 mod 991 ≡ 645 mod 991

Es gilt also: 757127 ≡ 645 mod 991

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 87 ⋅ x ≡ 1 mod 97 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 97 und 87

=>97 = 1⋅87 + 10
=>87 = 8⋅10 + 7
=>10 = 1⋅7 + 3
=>7 = 2⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(97,87)=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-2⋅3
3= 10-1⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -2⋅(10 -1⋅ 7)
= 1⋅7 -2⋅10 +2⋅ 7)
= -2⋅10 +3⋅ 7 (=1)
7= 87-8⋅10 eingesetzt in die Zeile drüber: 1 = -2⋅10 +3⋅(87 -8⋅ 10)
= -2⋅10 +3⋅87 -24⋅ 10)
= 3⋅87 -26⋅ 10 (=1)
10= 97-1⋅87 eingesetzt in die Zeile drüber: 1 = 3⋅87 -26⋅(97 -1⋅ 87)
= 3⋅87 -26⋅97 +26⋅ 87)
= -26⋅97 +29⋅ 87 (=1)

Es gilt also: ggt(97,87)=1 = -26⋅97 +29⋅87

oder wenn man -26⋅97 auf die linke Seite bringt:

1 +26⋅97 = +29⋅87

Es gilt also: 29⋅87 = 26⋅97 +1

Somit 29⋅87 = 1 mod 97

29 ist also das Inverse von 87 mod 97

Schlüsselpaar für RSA

Beispiel:

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