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: (14998 - 3000) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(14998 - 3000) mod 3 ≡ (14998 mod 3 - 3000 mod 3) mod 3.
14998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 14998
= 15000
3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000
= 3000
Somit gilt:
(14998 - 3000) mod 3 ≡ (1 - 0) mod 3 ≡ 1 mod 3.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (28 ⋅ 80) mod 3.
Um längere Rechnungen zu vermeiden, rechnen wir:
(28 ⋅ 80) mod 3 ≡ (28 mod 3 ⋅ 80 mod 3) mod 3.
28 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 28 = 27 + 1 = 9 ⋅ 3 + 1 ist.
80 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 80 = 78 + 2 = 26 ⋅ 3 + 2 ist.
Somit gilt:
(28 ⋅ 80) mod 3 ≡ (1 ⋅ 2) mod 3 ≡ 2 mod 3.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 43264 mod 863.
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. 432 -> x
2. mod(x²,863) -> 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: 4321=432
2: 4322=4321+1=4321⋅4321 ≡ 432⋅432=186624 ≡ 216 mod 863
4: 4324=4322+2=4322⋅4322 ≡ 216⋅216=46656 ≡ 54 mod 863
8: 4328=4324+4=4324⋅4324 ≡ 54⋅54=2916 ≡ 327 mod 863
16: 43216=4328+8=4328⋅4328 ≡ 327⋅327=106929 ≡ 780 mod 863
32: 43232=43216+16=43216⋅43216 ≡ 780⋅780=608400 ≡ 848 mod 863
64: 43264=43232+32=43232⋅43232 ≡ 848⋅848=719104 ≡ 225 mod 863
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 632221 mod 701.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 221 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 221 an und zerlegen 221 in eine Summer von 2er-Potenzen:
221 = 128+64+16+8+4+1
1: 6321=632
2: 6322=6321+1=6321⋅6321 ≡ 632⋅632=399424 ≡ 555 mod 701
4: 6324=6322+2=6322⋅6322 ≡ 555⋅555=308025 ≡ 286 mod 701
8: 6328=6324+4=6324⋅6324 ≡ 286⋅286=81796 ≡ 480 mod 701
16: 63216=6328+8=6328⋅6328 ≡ 480⋅480=230400 ≡ 472 mod 701
32: 63232=63216+16=63216⋅63216 ≡ 472⋅472=222784 ≡ 567 mod 701
64: 63264=63232+32=63232⋅63232 ≡ 567⋅567=321489 ≡ 431 mod 701
128: 632128=63264+64=63264⋅63264 ≡ 431⋅431=185761 ≡ 697 mod 701
632221
= 632128+64+16+8+4+1
= 632128⋅63264⋅63216⋅6328⋅6324⋅6321
≡ 697 ⋅ 431 ⋅ 472 ⋅ 480 ⋅ 286 ⋅ 632 mod 701
≡ 300407 ⋅ 472 ⋅ 480 ⋅ 286 ⋅ 632 mod 701 ≡ 379 ⋅ 472 ⋅ 480 ⋅ 286 ⋅ 632 mod 701
≡ 178888 ⋅ 480 ⋅ 286 ⋅ 632 mod 701 ≡ 133 ⋅ 480 ⋅ 286 ⋅ 632 mod 701
≡ 63840 ⋅ 286 ⋅ 632 mod 701 ≡ 49 ⋅ 286 ⋅ 632 mod 701
≡ 14014 ⋅ 632 mod 701 ≡ 695 ⋅ 632 mod 701
≡ 439240 mod 701 ≡ 414 mod 701
Es gilt also: 632221 ≡ 414 mod 701
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 54.
Also bestimme x, so dass 54 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 54
| =>83 | = 1⋅54 + 29 |
| =>54 | = 1⋅29 + 25 |
| =>29 | = 1⋅25 + 4 |
| =>25 | = 6⋅4 + 1 |
| =>4 | = 4⋅1 + 0 |
also gilt: ggt(83,54)=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= 54-1⋅29 | eingesetzt in die Zeile drüber: | 1 |
= -6⋅29 +7⋅(54 -1⋅ 29)
= -6⋅29 +7⋅54 -7⋅ 29) = 7⋅54 -13⋅ 29 (=1) |
| 29= 83-1⋅54 | eingesetzt in die Zeile drüber: | 1 |
= 7⋅54 -13⋅(83 -1⋅ 54)
= 7⋅54 -13⋅83 +13⋅ 54) = -13⋅83 +20⋅ 54 (=1) |
Es gilt also: ggt(83,54)=1 = -13⋅83 +20⋅54
oder wenn man -13⋅83 auf die linke Seite bringt:
1 +13⋅83 = +20⋅54
Es gilt also: 20⋅54 = 13⋅83 +1
Somit 20⋅54 = 1 mod 83
20 ist also das Inverse von 54 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 53 und q = 37. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
