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: (25005 - 1501) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(25005 - 1501) mod 5 ≡ (25005 mod 5 - 1501 mod 5) mod 5.
25005 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 25005
= 25000
1501 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 1501
= 1500
Somit gilt:
(25005 - 1501) mod 5 ≡ (0 - 1) mod 5 ≡ -1 mod 5 ≡ 4 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (47 ⋅ 99) mod 8.
Um längere Rechnungen zu vermeiden, rechnen wir:
(47 ⋅ 99) mod 8 ≡ (47 mod 8 ⋅ 99 mod 8) mod 8.
47 mod 8 ≡ 7 mod 8 kann man relativ leicht bestimmen, weil ja 47 = 40 + 7 = 5 ⋅ 8 + 7 ist.
99 mod 8 ≡ 3 mod 8 kann man relativ leicht bestimmen, weil ja 99 = 96 + 3 = 12 ⋅ 8 + 3 ist.
Somit gilt:
(47 ⋅ 99) mod 8 ≡ (7 ⋅ 3) mod 8 ≡ 21 mod 8 ≡ 5 mod 8.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 49032 mod 647.
Die 32 im Exponent ist ja ein reine 2er-Potenz (25).
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. 490 -> x
2. mod(x²,647) -> 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: 4901=490
2: 4902=4901+1=4901⋅4901 ≡ 490⋅490=240100 ≡ 63 mod 647
4: 4904=4902+2=4902⋅4902 ≡ 63⋅63=3969 ≡ 87 mod 647
8: 4908=4904+4=4904⋅4904 ≡ 87⋅87=7569 ≡ 452 mod 647
16: 49016=4908+8=4908⋅4908 ≡ 452⋅452=204304 ≡ 499 mod 647
32: 49032=49016+16=49016⋅49016 ≡ 499⋅499=249001 ≡ 553 mod 647
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 354240 mod 389.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 240 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 240 an und zerlegen 240 in eine Summer von 2er-Potenzen:
240 = 128+64+32+16
1: 3541=354
2: 3542=3541+1=3541⋅3541 ≡ 354⋅354=125316 ≡ 58 mod 389
4: 3544=3542+2=3542⋅3542 ≡ 58⋅58=3364 ≡ 252 mod 389
8: 3548=3544+4=3544⋅3544 ≡ 252⋅252=63504 ≡ 97 mod 389
16: 35416=3548+8=3548⋅3548 ≡ 97⋅97=9409 ≡ 73 mod 389
32: 35432=35416+16=35416⋅35416 ≡ 73⋅73=5329 ≡ 272 mod 389
64: 35464=35432+32=35432⋅35432 ≡ 272⋅272=73984 ≡ 74 mod 389
128: 354128=35464+64=35464⋅35464 ≡ 74⋅74=5476 ≡ 30 mod 389
354240
= 354128+64+32+16
= 354128⋅35464⋅35432⋅35416
≡ 30 ⋅ 74 ⋅ 272 ⋅ 73 mod 389
≡ 2220 ⋅ 272 ⋅ 73 mod 389 ≡ 275 ⋅ 272 ⋅ 73 mod 389
≡ 74800 ⋅ 73 mod 389 ≡ 112 ⋅ 73 mod 389
≡ 8176 mod 389 ≡ 7 mod 389
Es gilt also: 354240 ≡ 7 mod 389
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-79-Inverse zur Zahl 55.
Also bestimme x, so dass 55 ⋅ x ≡ 1 mod 79 gilt:
Berechnung des größten gemeinsamen Teilers von 79 und 55
| =>79 | = 1⋅55 + 24 |
| =>55 | = 2⋅24 + 7 |
| =>24 | = 3⋅7 + 3 |
| =>7 | = 2⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(79,55)=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= 55-2⋅24 | eingesetzt in die Zeile drüber: | 1 |
= -2⋅24 +7⋅(55 -2⋅ 24)
= -2⋅24 +7⋅55 -14⋅ 24) = 7⋅55 -16⋅ 24 (=1) |
| 24= 79-1⋅55 | eingesetzt in die Zeile drüber: | 1 |
= 7⋅55 -16⋅(79 -1⋅ 55)
= 7⋅55 -16⋅79 +16⋅ 55) = -16⋅79 +23⋅ 55 (=1) |
Es gilt also: ggt(79,55)=1 = -16⋅79 +23⋅55
oder wenn man -16⋅79 auf die linke Seite bringt:
1 +16⋅79 = +23⋅55
Es gilt also: 23⋅55 = 16⋅79 +1
Somit 23⋅55 = 1 mod 79
23 ist also das Inverse von 55 mod 79
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 41 und q = 83. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.