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: (2996 - 5995) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2996 - 5995) mod 6 ≡ (2996 mod 6 - 5995 mod 6) mod 6.
2996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 2996
= 3000
5995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 5995
= 6000
Somit gilt:
(2996 - 5995) mod 6 ≡ (2 - 1) mod 6 ≡ 1 mod 6.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (22 ⋅ 15) mod 6.
Um längere Rechnungen zu vermeiden, rechnen wir:
(22 ⋅ 15) mod 6 ≡ (22 mod 6 ⋅ 15 mod 6) mod 6.
22 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 22 = 18 + 4 = 3 ⋅ 6 + 4 ist.
15 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 15 = 12 + 3 = 2 ⋅ 6 + 3 ist.
Somit gilt:
(22 ⋅ 15) mod 6 ≡ (4 ⋅ 3) mod 6 ≡ 12 mod 6 ≡ 0 mod 6.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 45132 mod 607.
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. 451 -> x
2. mod(x²,607) -> 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: 4511=451
2: 4512=4511+1=4511⋅4511 ≡ 451⋅451=203401 ≡ 56 mod 607
4: 4514=4512+2=4512⋅4512 ≡ 56⋅56=3136 ≡ 101 mod 607
8: 4518=4514+4=4514⋅4514 ≡ 101⋅101=10201 ≡ 489 mod 607
16: 45116=4518+8=4518⋅4518 ≡ 489⋅489=239121 ≡ 570 mod 607
32: 45132=45116+16=45116⋅45116 ≡ 570⋅570=324900 ≡ 155 mod 607
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 388145 mod 599.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 145 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 145 an und zerlegen 145 in eine Summer von 2er-Potenzen:
145 = 128+16+1
1: 3881=388
2: 3882=3881+1=3881⋅3881 ≡ 388⋅388=150544 ≡ 195 mod 599
4: 3884=3882+2=3882⋅3882 ≡ 195⋅195=38025 ≡ 288 mod 599
8: 3888=3884+4=3884⋅3884 ≡ 288⋅288=82944 ≡ 282 mod 599
16: 38816=3888+8=3888⋅3888 ≡ 282⋅282=79524 ≡ 456 mod 599
32: 38832=38816+16=38816⋅38816 ≡ 456⋅456=207936 ≡ 83 mod 599
64: 38864=38832+32=38832⋅38832 ≡ 83⋅83=6889 ≡ 300 mod 599
128: 388128=38864+64=38864⋅38864 ≡ 300⋅300=90000 ≡ 150 mod 599
388145
= 388128+16+1
= 388128⋅38816⋅3881
≡ 150 ⋅ 456 ⋅ 388 mod 599
≡ 68400 ⋅ 388 mod 599 ≡ 114 ⋅ 388 mod 599
≡ 44232 mod 599 ≡ 505 mod 599
Es gilt also: 388145 ≡ 505 mod 599
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 25.
Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 61 gilt:
Berechnung des größten gemeinsamen Teilers von 61 und 25
| =>61 | = 2⋅25 + 11 |
| =>25 | = 2⋅11 + 3 |
| =>11 | = 3⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(61,25)=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= 3-1⋅2 | |||
| 2= 11-3⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(11 -3⋅ 3)
= 1⋅3 -1⋅11 +3⋅ 3) = -1⋅11 +4⋅ 3 (=1) |
| 3= 25-2⋅11 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅11 +4⋅(25 -2⋅ 11)
= -1⋅11 +4⋅25 -8⋅ 11) = 4⋅25 -9⋅ 11 (=1) |
| 11= 61-2⋅25 | eingesetzt in die Zeile drüber: | 1 |
= 4⋅25 -9⋅(61 -2⋅ 25)
= 4⋅25 -9⋅61 +18⋅ 25) = -9⋅61 +22⋅ 25 (=1) |
Es gilt also: ggt(61,25)=1 = -9⋅61 +22⋅25
oder wenn man -9⋅61 auf die linke Seite bringt:
1 +9⋅61 = +22⋅25
Es gilt also: 22⋅25 = 9⋅61 +1
Somit 22⋅25 = 1 mod 61
22 ist also das Inverse von 25 mod 61
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 101 und q = 53. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.