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.
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
796 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 796
= 700
Somit gilt:
(197 + 796) mod 4 ≡ (1 + 0) mod 4 ≡ 1 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (81 ⋅ 83) mod 10.
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.
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.
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:
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.
