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: (197 + 796) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(197 + 796) mod 4 ≡ (197 mod 4 + 796 mod 4) mod 4.

197 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 197 = 200-3 = 4 ⋅ 50 -3 = 4 ⋅ 50 - 4 + 1.

796 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 796 = 700+96 = 4 ⋅ 175 +96.

Somit gilt:

(197 + 796) mod 4 ≡ (1 + 0) mod 4 ≡ 1 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (81 ⋅ 83) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(81 ⋅ 83) mod 10 ≡ (81 mod 10 ⋅ 83 mod 10) mod 10.

81 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 8 ⋅ 10 + 1 ist.

83 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 83 = 80 + 3 = 8 ⋅ 10 + 3 ist.

Somit gilt:

(81 ⋅ 83) mod 10 ≡ (1 ⋅ 3) mod 10 ≡ 3 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 40764 mod 439.

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. 407 -> x
2. mod(x²,439) -> 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: 4071=407

2: 4072=4071+1=4071⋅4071 ≡ 407⋅407=165649 ≡ 146 mod 439

4: 4074=4072+2=4072⋅4072 ≡ 146⋅146=21316 ≡ 244 mod 439

8: 4078=4074+4=4074⋅4074 ≡ 244⋅244=59536 ≡ 271 mod 439

16: 40716=4078+8=4078⋅4078 ≡ 271⋅271=73441 ≡ 128 mod 439

32: 40732=40716+16=40716⋅40716 ≡ 128⋅128=16384 ≡ 141 mod 439

64: 40764=40732+32=40732⋅40732 ≡ 141⋅141=19881 ≡ 126 mod 439

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 422113 mod 911.

Lösung einblenden

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

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

113 = 64+32+16+1

1: 4221=422

2: 4222=4221+1=4221⋅4221 ≡ 422⋅422=178084 ≡ 439 mod 911

4: 4224=4222+2=4222⋅4222 ≡ 439⋅439=192721 ≡ 500 mod 911

8: 4228=4224+4=4224⋅4224 ≡ 500⋅500=250000 ≡ 386 mod 911

16: 42216=4228+8=4228⋅4228 ≡ 386⋅386=148996 ≡ 503 mod 911

32: 42232=42216+16=42216⋅42216 ≡ 503⋅503=253009 ≡ 662 mod 911

64: 42264=42232+32=42232⋅42232 ≡ 662⋅662=438244 ≡ 53 mod 911

422113

= 42264+32+16+1

= 42264⋅42232⋅42216⋅4221

53 ⋅ 662 ⋅ 503 ⋅ 422 mod 911
35086 ⋅ 503 ⋅ 422 mod 911 ≡ 468 ⋅ 503 ⋅ 422 mod 911
235404 ⋅ 422 mod 911 ≡ 366 ⋅ 422 mod 911
154452 mod 911 ≡ 493 mod 911

Es gilt also: 422113 ≡ 493 mod 911

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 24 ⋅ x ≡ 1 mod 79 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 79 und 24

=>79 = 3⋅24 + 7
=>24 = 3⋅7 + 3
=>7 = 2⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(79,24)=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= 24-3⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -2⋅(24 -3⋅ 7)
= 1⋅7 -2⋅24 +6⋅ 7)
= -2⋅24 +7⋅ 7 (=1)
7= 79-3⋅24 eingesetzt in die Zeile drüber: 1 = -2⋅24 +7⋅(79 -3⋅ 24)
= -2⋅24 +7⋅79 -21⋅ 24)
= 7⋅79 -23⋅ 24 (=1)

Es gilt also: ggt(79,24)=1 = 7⋅79 -23⋅24

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

1 -7⋅79 = -23⋅24

-23⋅24 = -7⋅79 + 1 |+79⋅24

-23⋅24 + 79⋅24 = -7⋅79 + 79⋅24 + 1

(-23 + 79) ⋅ 24 = (-7 + 24) ⋅ 79 + 1

56⋅24 = 17⋅79 + 1

Es gilt also: 56⋅24 = 17⋅79 +1

Somit 56⋅24 = 1 mod 79

56 ist also das Inverse von 24 mod 79

Schlüsselpaar für RSA

Beispiel:

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