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: (36009 - 893) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(36009 - 893) mod 9 ≡ (36009 mod 9 - 893 mod 9) mod 9.
36009 mod 9 ≡ 0 mod 9 kann man relativ leicht bestimmen, weil ja 36009
= 36000
893 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 893
= 900
Somit gilt:
(36009 - 893) mod 9 ≡ (0 - 2) mod 9 ≡ -2 mod 9 ≡ 7 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (26 ⋅ 67) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(26 ⋅ 67) mod 9 ≡ (26 mod 9 ⋅ 67 mod 9) mod 9.
26 mod 9 ≡ 8 mod 9 kann man relativ leicht bestimmen, weil ja 26 = 18 + 8 = 2 ⋅ 9 + 8 ist.
67 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 67 = 63 + 4 = 7 ⋅ 9 + 4 ist.
Somit gilt:
(26 ⋅ 67) mod 9 ≡ (8 ⋅ 4) mod 9 ≡ 32 mod 9 ≡ 5 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 34216 mod 593.
Die 16 im Exponent ist ja ein reine 2er-Potenz (24).
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. 342 -> x
2. mod(x²,593) -> 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: 3421=342
2: 3422=3421+1=3421⋅3421 ≡ 342⋅342=116964 ≡ 143 mod 593
4: 3424=3422+2=3422⋅3422 ≡ 143⋅143=20449 ≡ 287 mod 593
8: 3428=3424+4=3424⋅3424 ≡ 287⋅287=82369 ≡ 535 mod 593
16: 34216=3428+8=3428⋅3428 ≡ 535⋅535=286225 ≡ 399 mod 593
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 931197 mod 991.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 197 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 197 an und zerlegen 197 in eine Summer von 2er-Potenzen:
197 = 128+64+4+1
1: 9311=931
2: 9312=9311+1=9311⋅9311 ≡ 931⋅931=866761 ≡ 627 mod 991
4: 9314=9312+2=9312⋅9312 ≡ 627⋅627=393129 ≡ 693 mod 991
8: 9318=9314+4=9314⋅9314 ≡ 693⋅693=480249 ≡ 605 mod 991
16: 93116=9318+8=9318⋅9318 ≡ 605⋅605=366025 ≡ 346 mod 991
32: 93132=93116+16=93116⋅93116 ≡ 346⋅346=119716 ≡ 796 mod 991
64: 93164=93132+32=93132⋅93132 ≡ 796⋅796=633616 ≡ 367 mod 991
128: 931128=93164+64=93164⋅93164 ≡ 367⋅367=134689 ≡ 904 mod 991
931197
= 931128+64+4+1
= 931128⋅93164⋅9314⋅9311
≡ 904 ⋅ 367 ⋅ 693 ⋅ 931 mod 991
≡ 331768 ⋅ 693 ⋅ 931 mod 991 ≡ 774 ⋅ 693 ⋅ 931 mod 991
≡ 536382 ⋅ 931 mod 991 ≡ 251 ⋅ 931 mod 991
≡ 233681 mod 991 ≡ 796 mod 991
Es gilt also: 931197 ≡ 796 mod 991
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 43.
Also bestimme x, so dass 43 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 43
| =>83 | = 1⋅43 + 40 |
| =>43 | = 1⋅40 + 3 |
| =>40 | = 13⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(83,43)=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= 40-13⋅3 | |||
| 3= 43-1⋅40 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅40 -13⋅(43 -1⋅ 40)
= 1⋅40 -13⋅43 +13⋅ 40) = -13⋅43 +14⋅ 40 (=1) |
| 40= 83-1⋅43 | eingesetzt in die Zeile drüber: | 1 |
= -13⋅43 +14⋅(83 -1⋅ 43)
= -13⋅43 +14⋅83 -14⋅ 43) = 14⋅83 -27⋅ 43 (=1) |
Es gilt also: ggt(83,43)=1 = 14⋅83 -27⋅43
oder wenn man 14⋅83 auf die linke Seite bringt:
1 -14⋅83 = -27⋅43
-27⋅43 = -14⋅83 + 1 |+83⋅43
-27⋅43 + 83⋅43 = -14⋅83 + 83⋅43 + 1
(-27 + 83) ⋅ 43 = (-14 + 43) ⋅ 83 + 1
56⋅43 = 29⋅83 + 1
Es gilt also: 56⋅43 = 29⋅83 +1
Somit 56⋅43 = 1 mod 83
56 ist also das Inverse von 43 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 31 und q = 41. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
