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: (696 - 2105) mod 7.
Um längere Rechnungen zu vermeiden, rechnen wir:
(696 - 2105) mod 7 ≡ (696 mod 7 - 2105 mod 7) mod 7.
696 mod 7 ≡ 3 mod 7 kann man relativ leicht bestimmen, weil ja 696
= 700
2105 mod 7 ≡ 5 mod 7 kann man relativ leicht bestimmen, weil ja 2105
= 2100
Somit gilt:
(696 - 2105) mod 7 ≡ (3 - 5) mod 7 ≡ -2 mod 7 ≡ 5 mod 7.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (82 ⋅ 21) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(82 ⋅ 21) mod 5 ≡ (82 mod 5 ⋅ 21 mod 5) mod 5.
82 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 82 = 80 + 2 = 16 ⋅ 5 + 2 ist.
21 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 21 = 20 + 1 = 4 ⋅ 5 + 1 ist.
Somit gilt:
(82 ⋅ 21) mod 5 ≡ (2 ⋅ 1) mod 5 ≡ 2 mod 5.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 47864 mod 587.
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. 478 -> x
2. mod(x²,587) -> 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: 4781=478
2: 4782=4781+1=4781⋅4781 ≡ 478⋅478=228484 ≡ 141 mod 587
4: 4784=4782+2=4782⋅4782 ≡ 141⋅141=19881 ≡ 510 mod 587
8: 4788=4784+4=4784⋅4784 ≡ 510⋅510=260100 ≡ 59 mod 587
16: 47816=4788+8=4788⋅4788 ≡ 59⋅59=3481 ≡ 546 mod 587
32: 47832=47816+16=47816⋅47816 ≡ 546⋅546=298116 ≡ 507 mod 587
64: 47864=47832+32=47832⋅47832 ≡ 507⋅507=257049 ≡ 530 mod 587
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 420100 mod 809.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 100 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 100 an und zerlegen 100 in eine Summer von 2er-Potenzen:
100 = 64+32+4
1: 4201=420
2: 4202=4201+1=4201⋅4201 ≡ 420⋅420=176400 ≡ 38 mod 809
4: 4204=4202+2=4202⋅4202 ≡ 38⋅38=1444 ≡ 635 mod 809
8: 4208=4204+4=4204⋅4204 ≡ 635⋅635=403225 ≡ 343 mod 809
16: 42016=4208+8=4208⋅4208 ≡ 343⋅343=117649 ≡ 344 mod 809
32: 42032=42016+16=42016⋅42016 ≡ 344⋅344=118336 ≡ 222 mod 809
64: 42064=42032+32=42032⋅42032 ≡ 222⋅222=49284 ≡ 744 mod 809
420100
= 42064+32+4
= 42064⋅42032⋅4204
≡ 744 ⋅ 222 ⋅ 635 mod 809
≡ 165168 ⋅ 635 mod 809 ≡ 132 ⋅ 635 mod 809
≡ 83820 mod 809 ≡ 493 mod 809
Es gilt also: 420100 ≡ 493 mod 809
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-71-Inverse zur Zahl 53.
Also bestimme x, so dass 53 ⋅ x ≡ 1 mod 71 gilt:
Berechnung des größten gemeinsamen Teilers von 71 und 53
| =>71 | = 1⋅53 + 18 |
| =>53 | = 2⋅18 + 17 |
| =>18 | = 1⋅17 + 1 |
| =>17 | = 17⋅1 + 0 |
also gilt: ggt(71,53)=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= 18-1⋅17 | |||
| 17= 53-2⋅18 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅18 -1⋅(53 -2⋅ 18)
= 1⋅18 -1⋅53 +2⋅ 18) = -1⋅53 +3⋅ 18 (=1) |
| 18= 71-1⋅53 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅53 +3⋅(71 -1⋅ 53)
= -1⋅53 +3⋅71 -3⋅ 53) = 3⋅71 -4⋅ 53 (=1) |
Es gilt also: ggt(71,53)=1 = 3⋅71 -4⋅53
oder wenn man 3⋅71 auf die linke Seite bringt:
1 -3⋅71 = -4⋅53
-4⋅53 = -3⋅71 + 1 |+71⋅53
-4⋅53 + 71⋅53 = -3⋅71 + 71⋅53 + 1
(-4 + 71) ⋅ 53 = (-3 + 53) ⋅ 71 + 1
67⋅53 = 50⋅71 + 1
Es gilt also: 67⋅53 = 50⋅71 +1
Somit 67⋅53 = 1 mod 71
67 ist also das Inverse von 53 mod 71
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 53 und q = 47. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.