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: (2806 + 7002) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2806 + 7002) mod 7 ≡ (2806 mod 7 + 7002 mod 7) mod 7.

2806 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 2806 = 2800+6 = 7 ⋅ 400 +6.

7002 mod 7 ≡ 2 mod 7 kann man relativ leicht bestimmen, weil ja 7002 = 7000+2 = 7 ⋅ 1000 +2.

Somit gilt:

(2806 + 7002) mod 7 ≡ (6 + 2) mod 7 ≡ 8 mod 7 ≡ 1 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (75 ⋅ 76) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(75 ⋅ 76) mod 5 ≡ (75 mod 5 ⋅ 76 mod 5) mod 5.

75 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 75 = 75 + 0 = 15 ⋅ 5 + 0 ist.

76 mod 5 ≡ 1 mod 5 kann man relativ leicht bestimmen, weil ja 76 = 75 + 1 = 15 ⋅ 5 + 1 ist.

Somit gilt:

(75 ⋅ 76) mod 5 ≡ (0 ⋅ 1) mod 5 ≡ 0 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 134128 mod 271.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 134 -> x
2. mod(x²,271) -> 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: 1341=134

2: 1342=1341+1=1341⋅1341 ≡ 134⋅134=17956 ≡ 70 mod 271

4: 1344=1342+2=1342⋅1342 ≡ 70⋅70=4900 ≡ 22 mod 271

8: 1348=1344+4=1344⋅1344 ≡ 22⋅22=484 ≡ 213 mod 271

16: 13416=1348+8=1348⋅1348 ≡ 213⋅213=45369 ≡ 112 mod 271

32: 13432=13416+16=13416⋅13416 ≡ 112⋅112=12544 ≡ 78 mod 271

64: 13464=13432+32=13432⋅13432 ≡ 78⋅78=6084 ≡ 122 mod 271

128: 134128=13464+64=13464⋅13464 ≡ 122⋅122=14884 ≡ 250 mod 271

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 248167 mod 653.

Lösung einblenden

Wir berechnen zuerst mal alle 2er-Potenzen, die kleiner sind 167 (grauer Kasten).

Dann schauen wir die Binärdarstellung von 167 an und zerlegen 167 in eine Summer von 2er-Potenzen:

167 = 128+32+4+2+1

1: 2481=248

2: 2482=2481+1=2481⋅2481 ≡ 248⋅248=61504 ≡ 122 mod 653

4: 2484=2482+2=2482⋅2482 ≡ 122⋅122=14884 ≡ 518 mod 653

8: 2488=2484+4=2484⋅2484 ≡ 518⋅518=268324 ≡ 594 mod 653

16: 24816=2488+8=2488⋅2488 ≡ 594⋅594=352836 ≡ 216 mod 653

32: 24832=24816+16=24816⋅24816 ≡ 216⋅216=46656 ≡ 293 mod 653

64: 24864=24832+32=24832⋅24832 ≡ 293⋅293=85849 ≡ 306 mod 653

128: 248128=24864+64=24864⋅24864 ≡ 306⋅306=93636 ≡ 257 mod 653

248167

= 248128+32+4+2+1

= 248128⋅24832⋅2484⋅2482⋅2481

257 ⋅ 293 ⋅ 518 ⋅ 122 ⋅ 248 mod 653
75301 ⋅ 518 ⋅ 122 ⋅ 248 mod 653 ≡ 206 ⋅ 518 ⋅ 122 ⋅ 248 mod 653
106708 ⋅ 122 ⋅ 248 mod 653 ≡ 269 ⋅ 122 ⋅ 248 mod 653
32818 ⋅ 248 mod 653 ≡ 168 ⋅ 248 mod 653
41664 mod 653 ≡ 525 mod 653

Es gilt also: 248167 ≡ 525 mod 653

erweiterter Euklid'scher Algorithmus

Beispiel:

Berechne mit Hilfe des erweiterten Euklid'schen Algorithmus das Modulo-73-Inverse zur Zahl 51.

Also bestimme x, so dass 51 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 51

=>73 = 1⋅51 + 22
=>51 = 2⋅22 + 7
=>22 = 3⋅7 + 1
=>7 = 7⋅1 + 0

also gilt: ggt(73,51)=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-3⋅7
7= 51-2⋅22 eingesetzt in die Zeile drüber: 1 = 1⋅22 -3⋅(51 -2⋅ 22)
= 1⋅22 -3⋅51 +6⋅ 22)
= -3⋅51 +7⋅ 22 (=1)
22= 73-1⋅51 eingesetzt in die Zeile drüber: 1 = -3⋅51 +7⋅(73 -1⋅ 51)
= -3⋅51 +7⋅73 -7⋅ 51)
= 7⋅73 -10⋅ 51 (=1)

Es gilt also: ggt(73,51)=1 = 7⋅73 -10⋅51

oder wenn man 7⋅73 auf die linke Seite bringt:

1 -7⋅73 = -10⋅51

-10⋅51 = -7⋅73 + 1 |+73⋅51

-10⋅51 + 73⋅51 = -7⋅73 + 73⋅51 + 1

(-10 + 73) ⋅ 51 = (-7 + 51) ⋅ 73 + 1

63⋅51 = 44⋅73 + 1

Es gilt also: 63⋅51 = 44⋅73 +1

Somit 63⋅51 = 1 mod 73

63 ist also das Inverse von 51 mod 73

Schlüsselpaar für RSA

Beispiel:

Berechne mit dem RSA-Verfahren ein Schlüsselpaar zu den beiden Primzahlen p = 53 und q = 37. Aus Sicherheitsgründen sollte der selbst gewählte geheime Schlüssel nicht zu klein sein, hier also mindestens 500.