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: (402 - 7998) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(402 - 7998) mod 4 ≡ (402 mod 4 - 7998 mod 4) mod 4.
402 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 402
= 400
7998 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 7998
= 7000
Somit gilt:
(402 - 7998) mod 4 ≡ (2 - 2) mod 4 ≡ 0 mod 4.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (81 ⋅ 35) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(81 ⋅ 35) mod 10 ≡ (81 mod 10 ⋅ 35 mod 10) mod 10.
81 mod 10 ≡ 1 mod 10 kann man relativ leicht bestimmen, weil ja 81 = 80 + 1 = 8 ⋅ 10 + 1 ist.
35 mod 10 ≡ 5 mod 10 kann man relativ leicht bestimmen, weil ja 35 = 30 + 5 = 3 ⋅ 10 + 5 ist.
Somit gilt:
(81 ⋅ 35) mod 10 ≡ (1 ⋅ 5) mod 10 ≡ 5 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 151128 mod 433.
Die 128 im Exponent ist ja ein reine 2er-Potenz (27).
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. 151 -> x
2. mod(x²,433) -> 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: 1511=151
2: 1512=1511+1=1511⋅1511 ≡ 151⋅151=22801 ≡ 285 mod 433
4: 1514=1512+2=1512⋅1512 ≡ 285⋅285=81225 ≡ 254 mod 433
8: 1518=1514+4=1514⋅1514 ≡ 254⋅254=64516 ≡ 432 mod 433
16: 15116=1518+8=1518⋅1518 ≡ 432⋅432=186624 ≡ 1 mod 433
32: 15132=15116+16=15116⋅15116 ≡ 1⋅1=1 ≡ 1 mod 433
64: 15164=15132+32=15132⋅15132 ≡ 1⋅1=1 ≡ 1 mod 433
128: 151128=15164+64=15164⋅15164 ≡ 1⋅1=1 ≡ 1 mod 433
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 201249 mod 307.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 249 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 249 an und zerlegen 249 in eine Summer von 2er-Potenzen:
249 = 128+64+32+16+8+1
1: 2011=201
2: 2012=2011+1=2011⋅2011 ≡ 201⋅201=40401 ≡ 184 mod 307
4: 2014=2012+2=2012⋅2012 ≡ 184⋅184=33856 ≡ 86 mod 307
8: 2018=2014+4=2014⋅2014 ≡ 86⋅86=7396 ≡ 28 mod 307
16: 20116=2018+8=2018⋅2018 ≡ 28⋅28=784 ≡ 170 mod 307
32: 20132=20116+16=20116⋅20116 ≡ 170⋅170=28900 ≡ 42 mod 307
64: 20164=20132+32=20132⋅20132 ≡ 42⋅42=1764 ≡ 229 mod 307
128: 201128=20164+64=20164⋅20164 ≡ 229⋅229=52441 ≡ 251 mod 307
201249
= 201128+64+32+16+8+1
= 201128⋅20164⋅20132⋅20116⋅2018⋅2011
≡ 251 ⋅ 229 ⋅ 42 ⋅ 170 ⋅ 28 ⋅ 201 mod 307
≡ 57479 ⋅ 42 ⋅ 170 ⋅ 28 ⋅ 201 mod 307 ≡ 70 ⋅ 42 ⋅ 170 ⋅ 28 ⋅ 201 mod 307
≡ 2940 ⋅ 170 ⋅ 28 ⋅ 201 mod 307 ≡ 177 ⋅ 170 ⋅ 28 ⋅ 201 mod 307
≡ 30090 ⋅ 28 ⋅ 201 mod 307 ≡ 4 ⋅ 28 ⋅ 201 mod 307
≡ 112 ⋅ 201 mod 307
≡ 22512 mod 307 ≡ 101 mod 307
Es gilt also: 201249 ≡ 101 mod 307
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 = 101 und q = 59. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
