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: (2501 + 250) mod 5.
Um längere Rechnungen zu vermeiden, rechnen wir:
(2501 + 250) mod 5 ≡ (2501 mod 5 + 250 mod 5) mod 5.
2501 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 2501
= 2500
250 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 250
= 250
Somit gilt:
(2501 + 250) mod 5 ≡ (1 + 0) mod 5 ≡ 1 mod 5.
Modulo multiplizieren
Beispiel:
Berechne ohne WTR: (96 ⋅ 62) mod 4.
Um längere Rechnungen zu vermeiden, rechnen wir:
(96 ⋅ 62) mod 4 ≡ (96 mod 4 ⋅ 62 mod 4) mod 4.
96 mod 4 ≡ 0 mod 4 kann man relativ leicht bestimmen, weil ja 96 = 96 + 0 = 24 ⋅ 4 + 0 ist.
62 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 62 = 60 + 2 = 15 ⋅ 4 + 2 ist.
Somit gilt:
(96 ⋅ 62) mod 4 ≡ (0 ⋅ 2) mod 4 ≡ 0 mod 4.
modulo Potenzieren einfach
Beispiel:
Berechne möglichst geschickt: 63464 mod 719.
Die 64 im Exponent ist ja ein reine 2er-Potenz (26).
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. 634 -> x
2. mod(x²,719) -> 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: 6341=634
2: 6342=6341+1=6341⋅6341 ≡ 634⋅634=401956 ≡ 35 mod 719
4: 6344=6342+2=6342⋅6342 ≡ 35⋅35=1225 ≡ 506 mod 719
8: 6348=6344+4=6344⋅6344 ≡ 506⋅506=256036 ≡ 72 mod 719
16: 63416=6348+8=6348⋅6348 ≡ 72⋅72=5184 ≡ 151 mod 719
32: 63432=63416+16=63416⋅63416 ≡ 151⋅151=22801 ≡ 512 mod 719
64: 63464=63432+32=63432⋅63432 ≡ 512⋅512=262144 ≡ 428 mod 719
modulo Potenzieren große Zahlen
Beispiel:
Berechne möglichst geschickt: 10078 mod 281.
Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 78 (grauer Kasten).
Dann schauen wir die Binärdarstellung von 78 an und zerlegen 78 in eine Summer von 2er-Potenzen:
78 = 64+8+4+2
1: 1001=100
2: 1002=1001+1=1001⋅1001 ≡ 100⋅100=10000 ≡ 165 mod 281
4: 1004=1002+2=1002⋅1002 ≡ 165⋅165=27225 ≡ 249 mod 281
8: 1008=1004+4=1004⋅1004 ≡ 249⋅249=62001 ≡ 181 mod 281
16: 10016=1008+8=1008⋅1008 ≡ 181⋅181=32761 ≡ 165 mod 281
32: 10032=10016+16=10016⋅10016 ≡ 165⋅165=27225 ≡ 249 mod 281
64: 10064=10032+32=10032⋅10032 ≡ 249⋅249=62001 ≡ 181 mod 281
10078
= 10064+8+4+2
= 10064⋅1008⋅1004⋅1002
≡ 181 ⋅ 181 ⋅ 249 ⋅ 165 mod 281
≡ 32761 ⋅ 249 ⋅ 165 mod 281 ≡ 165 ⋅ 249 ⋅ 165 mod 281
≡ 41085 ⋅ 165 mod 281 ≡ 59 ⋅ 165 mod 281
≡ 9735 mod 281 ≡ 181 mod 281
Es gilt also: 10078 ≡ 181 mod 281
erweiterter Euklid'scher Algorithmus
Beispiel:
Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-67-Inverse zur Zahl 35.
Also bestimme x, so dass 35 ⋅ x ≡ 1 mod 67 gilt:
Berechnung des größten gemeinsamen Teilers von 67 und 35
| =>67 | = 1⋅35 + 32 |
| =>35 | = 1⋅32 + 3 |
| =>32 | = 10⋅3 + 2 |
| =>3 | = 1⋅2 + 1 |
| =>2 | = 2⋅1 + 0 |
also gilt: ggt(67,35)=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= 3-1⋅2 | |||
| 2= 32-10⋅3 | eingesetzt in die Zeile drüber: | 1 |
= 1⋅3 -1⋅(32 -10⋅ 3)
= 1⋅3 -1⋅32 +10⋅ 3) = -1⋅32 +11⋅ 3 (=1) |
| 3= 35-1⋅32 | eingesetzt in die Zeile drüber: | 1 |
= -1⋅32 +11⋅(35 -1⋅ 32)
= -1⋅32 +11⋅35 -11⋅ 32) = 11⋅35 -12⋅ 32 (=1) |
| 32= 67-1⋅35 | eingesetzt in die Zeile drüber: | 1 |
= 11⋅35 -12⋅(67 -1⋅ 35)
= 11⋅35 -12⋅67 +12⋅ 35) = -12⋅67 +23⋅ 35 (=1) |
Es gilt also: ggt(67,35)=1 = -12⋅67 +23⋅35
oder wenn man -12⋅67 auf die linke Seite bringt:
1 +12⋅67 = +23⋅35
Es gilt also: 23⋅35 = 12⋅67 +1
Somit 23⋅35 = 1 mod 67
23 ist also das Inverse von 35 mod 67
Schlüsselpaar für RSA
Beispiel:
Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 83 und q = 79. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.