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: (456 - 84) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(456 - 84) mod 9 ≡ (456 mod 9 - 84 mod 9) mod 9.
456 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 456
= 450
84 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 84
= 90
Somit gilt:
(456 - 84) mod 9 ≡ (6 - 3) mod 9 ≡ 3 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (86 ⋅ 88) mod 10.
Um längere Rechnungen zu vermeiden, rechnen wir:
(86 ⋅ 88) mod 10 ≡ (86 mod 10 ⋅ 88 mod 10) mod 10.
86 mod 10 ≡ 6 mod 10 kann man relativ leicht bestimmen, weil ja 86 = 80 + 6 = 8 ⋅ 10 + 6 ist.
88 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 88 = 80 + 8 = 8 ⋅ 10 + 8 ist.
Somit gilt:
(86 ⋅ 88) mod 10 ≡ (6 ⋅ 8) mod 10 ≡ 48 mod 10 ≡ 8 mod 10.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 8268 mod 877.
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. 826 -> x
2. mod(x²,877) -> 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: 8261=826
2: 8262=8261+1=8261⋅8261 ≡ 826⋅826=682276 ≡ 847 mod 877
4: 8264=8262+2=8262⋅8262 ≡ 847⋅847=717409 ≡ 23 mod 877
8: 8268=8264+4=8264⋅8264 ≡ 23⋅23=529 ≡ 529 mod 877
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 660161 mod 811.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 161 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 161 an und zerlegen 161 in eine Summer von 2er-Potenzen:
161 = 128+32+1
1: 6601=660
2: 6602=6601+1=6601⋅6601 ≡ 660⋅660=435600 ≡ 93 mod 811
4: 6604=6602+2=6602⋅6602 ≡ 93⋅93=8649 ≡ 539 mod 811
8: 6608=6604+4=6604⋅6604 ≡ 539⋅539=290521 ≡ 183 mod 811
16: 66016=6608+8=6608⋅6608 ≡ 183⋅183=33489 ≡ 238 mod 811
32: 66032=66016+16=66016⋅66016 ≡ 238⋅238=56644 ≡ 685 mod 811
64: 66064=66032+32=66032⋅66032 ≡ 685⋅685=469225 ≡ 467 mod 811
128: 660128=66064+64=66064⋅66064 ≡ 467⋅467=218089 ≡ 741 mod 811
660161
= 660128+32+1
= 660128⋅66032⋅6601
≡ 741 ⋅ 685 ⋅ 660 mod 811
≡ 507585 ⋅ 660 mod 811 ≡ 710 ⋅ 660 mod 811
≡ 468600 mod 811 ≡ 653 mod 811
Es gilt also: 660161 ≡ 653 mod 811
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 72.
Also bestimme x, so dass 72 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 72
| =>97 | = 1⋅72 + 25 |
| =>72 | = 2⋅25 + 22 |
| =>25 | = 1⋅22 + 3 |
| =>22 | = 7⋅3 + 1 |
| =>3 | = 3⋅1 + 0 |
also gilt: ggt(97,72)=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= 22-7⋅3 | |||
| 3= 25-1⋅22 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅22 -7⋅(25 -1⋅ 22)
= 1⋅22 -7⋅25 +7⋅ 22) = -7⋅25 +8⋅ 22 (=1) |
| 22= 72-2⋅25 | eingesetzt in die Zeile drüber: | 1 |
= -7⋅25 +8⋅(72 -2⋅ 25)
= -7⋅25 +8⋅72 -16⋅ 25) = 8⋅72 -23⋅ 25 (=1) |
| 25= 97-1⋅72 | eingesetzt in die Zeile drüber: | 1 |
= 8⋅72 -23⋅(97 -1⋅ 72)
= 8⋅72 -23⋅97 +23⋅ 72) = -23⋅97 +31⋅ 72 (=1) |
Es gilt also: ggt(97,72)=1 = -23⋅97 +31⋅72
oder wenn man -23⋅97 auf die linke Seite bringt:
1 +23⋅97 = +31⋅72
Es gilt also: 31⋅72 = 23⋅97 +1
Somit 31⋅72 = 1 mod 97
31 ist also das Inverse von 72 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 43 und q = 101. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.
