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: (146 - 2005) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(146 - 2005) mod 5 ≡ (146 mod 5 - 2005 mod 5) mod 5.

146 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 146 = 140+6 = 5 ⋅ 28 +6.

2005 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 2005 = 2000+5 = 5 ⋅ 400 +5.

Somit gilt:

(146 - 2005) mod 5 ≡ (1 - 0) mod 5 ≡ 1 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (56 ⋅ 30) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(56 ⋅ 30) mod 10 ≡ (56 mod 10 ⋅ 30 mod 10) mod 10.

56 mod 10 ≡ 6 mod 10 kann man relativ leicht bestimmen, weil ja 56 = 50 + 6 = 5 ⋅ 10 + 6 ist.

30 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 30 = 30 + 0 = 3 ⋅ 10 + 0 ist.

Somit gilt:

(56 ⋅ 30) mod 10 ≡ (6 ⋅ 0) mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 36464 mod 389.

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. 364 -> x
2. mod(x²,389) -> 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: 3641=364

2: 3642=3641+1=3641⋅3641 ≡ 364⋅364=132496 ≡ 236 mod 389

4: 3644=3642+2=3642⋅3642 ≡ 236⋅236=55696 ≡ 69 mod 389

8: 3648=3644+4=3644⋅3644 ≡ 69⋅69=4761 ≡ 93 mod 389

16: 36416=3648+8=3648⋅3648 ≡ 93⋅93=8649 ≡ 91 mod 389

32: 36432=36416+16=36416⋅36416 ≡ 91⋅91=8281 ≡ 112 mod 389

64: 36464=36432+32=36432⋅36432 ≡ 112⋅112=12544 ≡ 96 mod 389

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 30071 mod 571.

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: 3001=300

2: 3002=3001+1=3001⋅3001 ≡ 300⋅300=90000 ≡ 353 mod 571

4: 3004=3002+2=3002⋅3002 ≡ 353⋅353=124609 ≡ 131 mod 571

8: 3008=3004+4=3004⋅3004 ≡ 131⋅131=17161 ≡ 31 mod 571

16: 30016=3008+8=3008⋅3008 ≡ 31⋅31=961 ≡ 390 mod 571

32: 30032=30016+16=30016⋅30016 ≡ 390⋅390=152100 ≡ 214 mod 571

64: 30064=30032+32=30032⋅30032 ≡ 214⋅214=45796 ≡ 116 mod 571

30071

= 30064+4+2+1

= 30064⋅3004⋅3002⋅3001

≡ 116 ⋅ 131 ⋅ 353 ⋅ 300 mod 571
≡ 15196 ⋅ 353 ⋅ 300 mod 571 ≡ 350 ⋅ 353 ⋅ 300 mod 571
≡ 123550 ⋅ 300 mod 571 ≡ 214 ⋅ 300 mod 571
≡ 64200 mod 571 ≡ 248 mod 571

Es gilt also: 30071 ≡ 248 mod 571

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 29 ⋅ x ≡ 1 mod 83 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 83 und 29

=>83 = 2⋅29 + 25
=>29 = 1⋅25 + 4
=>25 = 6⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(83,29)=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= 25-6⋅4
4= 29-1⋅25 eingesetzt in die Zeile drüber: 1 = 1⋅25 -6⋅(29 -1⋅ 25)
= 1⋅25 -6⋅29 +6⋅ 25)
= -6⋅29 +7⋅ 25 (=1)
25= 83-2⋅29 eingesetzt in die Zeile drüber: 1 = -6⋅29 +7⋅(83 -2⋅ 29)
= -6⋅29 +7⋅83 -14⋅ 29)
= 7⋅83 -20⋅ 29 (=1)

Es gilt also: ggt(83,29)=1 = 7⋅83 -20⋅29

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

1 -7⋅83 = -20⋅29

-20⋅29 = -7⋅83 + 1 |+83⋅29

-20⋅29 + 83⋅29 = -7⋅83 + 83⋅29 + 1

(-20 + 83) ⋅ 29 = (-7 + 29) ⋅ 83 + 1

63⋅29 = 22⋅83 + 1

Es gilt also: 63⋅29 = 22⋅83 +1

Somit 63⋅29 = 1 mod 83

63 ist also das Inverse von 29 mod 83

Schlüsselpaar für RSA

Beispiel:

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