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: (4506 - 27007) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(4506 - 27007) mod 9 ≡ (4506 mod 9 - 27007 mod 9) mod 9.
4506 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 4506
= 4500
27007 mod 9 ≡ 7 mod 9 kann man relativ leicht bestimmen, weil ja 27007
= 27000
Somit gilt:
(4506 - 27007) mod 9 ≡ (6 - 7) mod 9 ≡ -1 mod 9 ≡ 8 mod 9.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (58 ⋅ 65) mod 9.
Um längere Rechnungen zu vermeiden, rechnen wir:
(58 ⋅ 65) mod 9 ≡ (58 mod 9 ⋅ 65 mod 9) mod 9.
58 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 58 = 54 + 4 = 6 ⋅ 9 + 4 ist.
65 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 65 = 63 + 2 = 7 ⋅ 9 + 2 ist.
Somit gilt:
(58 ⋅ 65) mod 9 ≡ (4 ⋅ 2) mod 9 ≡ 8 mod 9.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 68716 mod 751.
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. 687 -> x
2. mod(x²,751) -> 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: 6871=687
2: 6872=6871+1=6871⋅6871 ≡ 687⋅687=471969 ≡ 341 mod 751
4: 6874=6872+2=6872⋅6872 ≡ 341⋅341=116281 ≡ 627 mod 751
8: 6878=6874+4=6874⋅6874 ≡ 627⋅627=393129 ≡ 356 mod 751
16: 68716=6878+8=6878⋅6878 ≡ 356⋅356=126736 ≡ 568 mod 751
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 39071 mod 853.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 71 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 71 an und zerlegen 71 in eine Summer von 2er-Potenzen:
71 = 64+4+2+1
1: 3901=390
2: 3902=3901+1=3901⋅3901 ≡ 390⋅390=152100 ≡ 266 mod 853
4: 3904=3902+2=3902⋅3902 ≡ 266⋅266=70756 ≡ 810 mod 853
8: 3908=3904+4=3904⋅3904 ≡ 810⋅810=656100 ≡ 143 mod 853
16: 39016=3908+8=3908⋅3908 ≡ 143⋅143=20449 ≡ 830 mod 853
32: 39032=39016+16=39016⋅39016 ≡ 830⋅830=688900 ≡ 529 mod 853
64: 39064=39032+32=39032⋅39032 ≡ 529⋅529=279841 ≡ 57 mod 853
39071
= 39064+4+2+1
= 39064⋅3904⋅3902⋅3901
≡ 57 ⋅ 810 ⋅ 266 ⋅ 390 mod 853
≡ 46170 ⋅ 266 ⋅ 390 mod 853 ≡ 108 ⋅ 266 ⋅ 390 mod 853
≡ 28728 ⋅ 390 mod 853 ≡ 579 ⋅ 390 mod 853
≡ 225810 mod 853 ≡ 618 mod 853
Es gilt also: 39071 ≡ 618 mod 853
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-97-Inverse zur Zahl 30.
Also bestimme x, so dass 30 ⋅ x ≡ 1 mod 97 gilt:
Berechnung des größten gemeinsamen Teilers von 97 und 30
| =>97 | = 3⋅30 + 7 |
| =>30 | = 4⋅7 + 2 |
| =>7 | = 3⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(97,30)=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= 7-3⋅2 | |||
| 2= 30-4⋅7 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅7 -3⋅(30 -4⋅ 7)
= 1⋅7 -3⋅30 +12⋅ 7) = -3⋅30 +13⋅ 7 (=1) |
| 7= 97-3⋅30 | eingesetzt in die Zeile drüber: | 1 |
= -3⋅30 +13⋅(97 -3⋅ 30)
= -3⋅30 +13⋅97 -39⋅ 30) = 13⋅97 -42⋅ 30 (=1) |
Es gilt also: ggt(97,30)=1 = 13⋅97 -42⋅30
oder wenn man 13⋅97 auf die linke Seite bringt:
1 -13⋅97 = -42⋅30
-42⋅30 = -13⋅97 + 1 |+97⋅30
-42⋅30 + 97⋅30 = -13⋅97 + 97⋅30 + 1
(-42 + 97) ⋅ 30 = (-13 + 30) ⋅ 97 + 1
55⋅30 = 17⋅97 + 1
Es gilt also: 55⋅30 = 17⋅97 +1
Somit 55⋅30 = 1 mod 97
55 ist also das Inverse von 30 mod 97
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 43. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.