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: (36006 + 1792) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(36006 + 1792) mod 9 ≡ (36006 mod 9 + 1792 mod 9) mod 9.
36006 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 36006
= 36000
1792 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 1792
= 1800
Somit gilt:
(36006 + 1792) mod 9 ≡ (6 + 1) mod 9 ≡ 7 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (100 ⋅ 76) mod 11.
Um längere Rechnungen zu vermeiden, rechnen wir:
(100 ⋅ 76) mod 11 ≡ (100 mod 11 ⋅ 76 mod 11) mod 11.
100 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 100 = 99 + 1 = 9 ⋅ 11 + 1 ist.
76 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 76 = 66 + 10 = 6 ⋅ 11 + 10 ist.
Somit gilt:
(100 ⋅ 76) mod 11 ≡ (1 ⋅ 10) mod 11 ≡ 10 mod 11.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 37932 mod 569.
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. 379 -> x
2. mod(x²,569) -> 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: 3791=379
2: 3792=3791+1=3791⋅3791 ≡ 379⋅379=143641 ≡ 253 mod 569
4: 3794=3792+2=3792⋅3792 ≡ 253⋅253=64009 ≡ 281 mod 569
8: 3798=3794+4=3794⋅3794 ≡ 281⋅281=78961 ≡ 439 mod 569
16: 37916=3798+8=3798⋅3798 ≡ 439⋅439=192721 ≡ 399 mod 569
32: 37932=37916+16=37916⋅37916 ≡ 399⋅399=159201 ≡ 450 mod 569
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 511112 mod 881.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 112 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 112 an und zerlegen 112 in eine Summer von 2er-Potenzen:
112 = 64+32+16
1: 5111=511
2: 5112=5111+1=5111⋅5111 ≡ 511⋅511=261121 ≡ 345 mod 881
4: 5114=5112+2=5112⋅5112 ≡ 345⋅345=119025 ≡ 90 mod 881
8: 5118=5114+4=5114⋅5114 ≡ 90⋅90=8100 ≡ 171 mod 881
16: 51116=5118+8=5118⋅5118 ≡ 171⋅171=29241 ≡ 168 mod 881
32: 51132=51116+16=51116⋅51116 ≡ 168⋅168=28224 ≡ 32 mod 881
64: 51164=51132+32=51132⋅51132 ≡ 32⋅32=1024 ≡ 143 mod 881
511112
= 51164+32+16
= 51164⋅51132⋅51116
≡ 143 ⋅ 32 ⋅ 168 mod 881
≡ 4576 ⋅ 168 mod 881 ≡ 171 ⋅ 168 mod 881
≡ 28728 mod 881 ≡ 536 mod 881
Es gilt also: 511112 ≡ 536 mod 881
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-83-Inverse zur Zahl 71.
Also bestimme x, so dass 71 ⋅ x ≡ 1 mod 83 gilt:
Berechnung des größten gemeinsamen Teilers von 83 und 71
| =>83 | = 1⋅71 + 12 |
| =>71 | = 5⋅12 + 11 |
| =>12 | = 1⋅11 + 1 |
| =>11 | = 11⋅1 + 0 |
also gilt: ggt(83,71)=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= 12-1⋅11 | |||
| 11= 71-5⋅12 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅12 -1⋅(71 -5⋅ 12)
= 1⋅12 -1⋅71 +5⋅ 12) = -1⋅71 +6⋅ 12 (=1) |
| 12= 83-1⋅71 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅71 +6⋅(83 -1⋅ 71)
= -1⋅71 +6⋅83 -6⋅ 71) = 6⋅83 -7⋅ 71 (=1) |
Es gilt also: ggt(83,71)=1 = 6⋅83 -7⋅71
oder wenn man 6⋅83 auf die linke Seite bringt:
1 -6⋅83 = -7⋅71
-7⋅71 = -6⋅83 + 1 |+83⋅71
-7⋅71 + 83⋅71 = -6⋅83 + 83⋅71 + 1
(-7 + 83) ⋅ 71 = (-6 + 71) ⋅ 83 + 1
76⋅71 = 65⋅83 + 1
Es gilt also: 76⋅71 = 65⋅83 +1
Somit 76⋅71 = 1 mod 83
76 ist also das Inverse von 71 mod 83
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 71 und q = 61. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
