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: (5005 - 1498) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(5005 - 1498) mod 5 ≡ (5005 mod 5 - 1498 mod 5) mod 5.
5005 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 5005
= 5000
1498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 1498
= 1400
Somit gilt:
(5005 - 1498) mod 5 ≡ (0 - 3) mod 5 ≡ -3 mod 5 ≡ 2 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (88 ⋅ 90) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(88 ⋅ 90) mod 10 ≡ (88 mod 10 ⋅ 90 mod 10) mod 10.
88 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 88 = 80 + 8 = 8 ⋅ 10 + 8 ist.
90 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 90 = 90 + 0 = 9 ⋅ 10 + 0 ist.
Somit gilt:
(88 ⋅ 90) mod 10 ≡ (8 ⋅ 0) mod 10 ≡ 0 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 28132 mod 631.
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. 281 -> x
2. mod(x²,631) -> 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: 2811=281
2: 2812=2811+1=2811⋅2811 ≡ 281⋅281=78961 ≡ 86 mod 631
4: 2814=2812+2=2812⋅2812 ≡ 86⋅86=7396 ≡ 455 mod 631
8: 2818=2814+4=2814⋅2814 ≡ 455⋅455=207025 ≡ 57 mod 631
16: 28116=2818+8=2818⋅2818 ≡ 57⋅57=3249 ≡ 94 mod 631
32: 28132=28116+16=28116⋅28116 ≡ 94⋅94=8836 ≡ 2 mod 631
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 511100 mod 653.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 100 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 100 an und zerlegen 100 in eine Summer von 2er-Potenzen:
100 = 64+32+4
1: 5111=511
2: 5112=5111+1=5111⋅5111 ≡ 511⋅511=261121 ≡ 574 mod 653
4: 5114=5112+2=5112⋅5112 ≡ 574⋅574=329476 ≡ 364 mod 653
8: 5118=5114+4=5114⋅5114 ≡ 364⋅364=132496 ≡ 590 mod 653
16: 51116=5118+8=5118⋅5118 ≡ 590⋅590=348100 ≡ 51 mod 653
32: 51132=51116+16=51116⋅51116 ≡ 51⋅51=2601 ≡ 642 mod 653
64: 51164=51132+32=51132⋅51132 ≡ 642⋅642=412164 ≡ 121 mod 653
511100
= 51164+32+4
= 51164⋅51132⋅5114
≡ 121 ⋅ 642 ⋅ 364 mod 653
≡ 77682 ⋅ 364 mod 653 ≡ 628 ⋅ 364 mod 653
≡ 228592 mod 653 ≡ 42 mod 653
Es gilt also: 511100 ≡ 42 mod 653
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 50.
Also bestimme x, so dass 50 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 50
| =>67 | = 1⋅50 + 17 |
| =>50 | = 2⋅17 + 16 |
| =>17 | = 1⋅16 + 1 |
| =>16 | = 16⋅1 + 0 |
also gilt: ggt(67,50)=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= 17-1⋅16 | |||
| 16= 50-2⋅17 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅17 -1⋅(50 -2⋅ 17)
= 1⋅17 -1⋅50 +2⋅ 17) = -1⋅50 +3⋅ 17 (=1) |
| 17= 67-1⋅50 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅50 +3⋅(67 -1⋅ 50)
= -1⋅50 +3⋅67 -3⋅ 50) = 3⋅67 -4⋅ 50 (=1) |
Es gilt also: ggt(67,50)=1 = 3⋅67 -4⋅50
oder wenn man 3⋅67 auf die linke Seite bringt:
1 -3⋅67 = -4⋅50
-4⋅50 = -3⋅67 + 1 |+67⋅50
-4⋅50 + 67⋅50 = -3⋅67 + 67⋅50 + 1
(-4 + 67) ⋅ 50 = (-3 + 50) ⋅ 67 + 1
63⋅50 = 47⋅67 + 1
Es gilt also: 63⋅50 = 47⋅67 +1
Somit 63⋅50 = 1 mod 67
63 ist also das Inverse von 50 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 61 und q = 31. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
