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: (161 - 41) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(161 - 41) mod 4 ≡ (161 mod 4 - 41 mod 4) mod 4.
161 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 161
= 160
41 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 41
= 40
Somit gilt:
(161 - 41) mod 4 ≡ (1 - 1) mod 4 ≡ 0 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (91 ⋅ 85) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(91 ⋅ 85) mod 11 ≡ (91 mod 11 ⋅ 85 mod 11) mod 11.
91 mod 11 ≡ 3 mod 11 kann man relativ leicht bestimmen, weil ja 91 = 88 + 3 = 8 ⋅ 11 + 3 ist.
85 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 85 = 77 + 8 = 7 ⋅ 11 + 8 ist.
Somit gilt:
(91 ⋅ 85) mod 11 ≡ (3 ⋅ 8) mod 11 ≡ 24 mod 11 ≡ 2 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 4038 mod 971.
Die 8 im Exponent ist ja ein reine 2er-Potenz (23).
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. 403 -> x
2. mod(x²,971) -> 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: 4031=403
2: 4032=4031+1=4031⋅4031 ≡ 403⋅403=162409 ≡ 252 mod 971
4: 4034=4032+2=4032⋅4032 ≡ 252⋅252=63504 ≡ 389 mod 971
8: 4038=4034+4=4034⋅4034 ≡ 389⋅389=151321 ≡ 816 mod 971
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 179218 mod 523.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 218 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 218 an und zerlegen 218 in eine Summer von 2er-Potenzen:
218 = 128+64+16+8+2
1: 1791=179
2: 1792=1791+1=1791⋅1791 ≡ 179⋅179=32041 ≡ 138 mod 523
4: 1794=1792+2=1792⋅1792 ≡ 138⋅138=19044 ≡ 216 mod 523
8: 1798=1794+4=1794⋅1794 ≡ 216⋅216=46656 ≡ 109 mod 523
16: 17916=1798+8=1798⋅1798 ≡ 109⋅109=11881 ≡ 375 mod 523
32: 17932=17916+16=17916⋅17916 ≡ 375⋅375=140625 ≡ 461 mod 523
64: 17964=17932+32=17932⋅17932 ≡ 461⋅461=212521 ≡ 183 mod 523
128: 179128=17964+64=17964⋅17964 ≡ 183⋅183=33489 ≡ 17 mod 523
179218
= 179128+64+16+8+2
= 179128⋅17964⋅17916⋅1798⋅1792
≡ 17 ⋅ 183 ⋅ 375 ⋅ 109 ⋅ 138 mod 523
≡ 3111 ⋅ 375 ⋅ 109 ⋅ 138 mod 523 ≡ 496 ⋅ 375 ⋅ 109 ⋅ 138 mod 523
≡ 186000 ⋅ 109 ⋅ 138 mod 523 ≡ 335 ⋅ 109 ⋅ 138 mod 523
≡ 36515 ⋅ 138 mod 523 ≡ 428 ⋅ 138 mod 523
≡ 59064 mod 523 ≡ 488 mod 523
Es gilt also: 179218 ≡ 488 mod 523
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-61-Inverse zur Zahl 23.
Also bestimme x, so dass 23 ⋅ x ≡ 1 mod 61 gilt:
Berechnung des größten gemeinsamen Teilers von 61 und 23
| =>61 | = 2⋅23 + 15 |
| =>23 | = 1⋅15 + 8 |
| =>15 | = 1⋅8 + 7 |
| =>8 | = 1⋅7 + 1 |
| =>7 | = 7⋅1 + 0 |
also gilt: ggt(61,23)=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= 8-1⋅7 | |||
| 7= 15-1⋅8 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅8 -1⋅(15 -1⋅ 8)
= 1⋅8 -1⋅15 +1⋅ 8) = -1⋅15 +2⋅ 8 (=1) |
| 8= 23-1⋅15 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅15 +2⋅(23 -1⋅ 15)
= -1⋅15 +2⋅23 -2⋅ 15) = 2⋅23 -3⋅ 15 (=1) |
| 15= 61-2⋅23 | eingesetzt in die Zeile drüber: | 1 |
= 2⋅23 -3⋅(61 -2⋅ 23)
= 2⋅23 -3⋅61 +6⋅ 23) = -3⋅61 +8⋅ 23 (=1) |
Es gilt also: ggt(61,23)=1 = -3⋅61 +8⋅23
oder wenn man -3⋅61 auf die linke Seite bringt:
1 +3⋅61 = +8⋅23
Es gilt also: 8⋅23 = 3⋅61 +1
Somit 8⋅23 = 1 mod 61
8 ist also das Inverse von 23 mod 61
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 43 und q = 59. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.