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: (1499 - 897) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1499 - 897) mod 3 ≡ (1499 mod 3 - 897 mod 3) mod 3.

1499 mod 3 ≡ 2 mod 3 kann man relativ leicht bestimmen, weil ja 1499 = 1500-1 = 3 ⋅ 500 -1 = 3 ⋅ 500 - 3 + 2.

897 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 897 = 900-3 = 3 ⋅ 300 -3 = 3 ⋅ 300 - 3 + 0.

Somit gilt:

(1499 - 897) mod 3 ≡ (2 - 0) mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (94 ⋅ 40) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(94 ⋅ 40) mod 11 ≡ (94 mod 11 ⋅ 40 mod 11) mod 11.

94 mod 11 ≡ 6 mod 11 kann man relativ leicht bestimmen, weil ja 94 = 88 + 6 = 8 ⋅ 11 + 6 ist.

40 mod 11 ≡ 7 mod 11 kann man relativ leicht bestimmen, weil ja 40 = 33 + 7 = 3 ⋅ 11 + 7 ist.

Somit gilt:

(94 ⋅ 40) mod 11 ≡ (6 ⋅ 7) mod 11 ≡ 42 mod 11 ≡ 9 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 10164 mod 281.

Lösung einblenden

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. 101 -> x
2. mod(x²,281) -> 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: 1011=101

2: 1012=1011+1=1011⋅1011 ≡ 101⋅101=10201 ≡ 85 mod 281

4: 1014=1012+2=1012⋅1012 ≡ 85⋅85=7225 ≡ 200 mod 281

8: 1018=1014+4=1014⋅1014 ≡ 200⋅200=40000 ≡ 98 mod 281

16: 10116=1018+8=1018⋅1018 ≡ 98⋅98=9604 ≡ 50 mod 281

32: 10132=10116+16=10116⋅10116 ≡ 50⋅50=2500 ≡ 252 mod 281

64: 10164=10132+32=10132⋅10132 ≡ 252⋅252=63504 ≡ 279 mod 281

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 431223 mod 757.

Lösung einblenden

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

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

223 = 128+64+16+8+4+2+1

1: 4311=431

2: 4312=4311+1=4311⋅4311 ≡ 431⋅431=185761 ≡ 296 mod 757

4: 4314=4312+2=4312⋅4312 ≡ 296⋅296=87616 ≡ 561 mod 757

8: 4318=4314+4=4314⋅4314 ≡ 561⋅561=314721 ≡ 566 mod 757

16: 43116=4318+8=4318⋅4318 ≡ 566⋅566=320356 ≡ 145 mod 757

32: 43132=43116+16=43116⋅43116 ≡ 145⋅145=21025 ≡ 586 mod 757

64: 43164=43132+32=43132⋅43132 ≡ 586⋅586=343396 ≡ 475 mod 757

128: 431128=43164+64=43164⋅43164 ≡ 475⋅475=225625 ≡ 39 mod 757

431223

= 431128+64+16+8+4+2+1

= 431128⋅43164⋅43116⋅4318⋅4314⋅4312⋅4311

39 ⋅ 475 ⋅ 145 ⋅ 566 ⋅ 561 ⋅ 296 ⋅ 431 mod 757
18525 ⋅ 145 ⋅ 566 ⋅ 561 ⋅ 296 ⋅ 431 mod 757 ≡ 357 ⋅ 145 ⋅ 566 ⋅ 561 ⋅ 296 ⋅ 431 mod 757
51765 ⋅ 566 ⋅ 561 ⋅ 296 ⋅ 431 mod 757 ≡ 289 ⋅ 566 ⋅ 561 ⋅ 296 ⋅ 431 mod 757
163574 ⋅ 561 ⋅ 296 ⋅ 431 mod 757 ≡ 62 ⋅ 561 ⋅ 296 ⋅ 431 mod 757
34782 ⋅ 296 ⋅ 431 mod 757 ≡ 717 ⋅ 296 ⋅ 431 mod 757
212232 ⋅ 431 mod 757 ≡ 272 ⋅ 431 mod 757
117232 mod 757 ≡ 654 mod 757

Es gilt also: 431223 ≡ 654 mod 757

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 63 ⋅ x ≡ 1 mod 83 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 83 und 63

=>83 = 1⋅63 + 20
=>63 = 3⋅20 + 3
=>20 = 6⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(83,63)=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= 20-6⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(20 -6⋅ 3)
= 1⋅3 -1⋅20 +6⋅ 3)
= -1⋅20 +7⋅ 3 (=1)
3= 63-3⋅20 eingesetzt in die Zeile drüber: 1 = -1⋅20 +7⋅(63 -3⋅ 20)
= -1⋅20 +7⋅63 -21⋅ 20)
= 7⋅63 -22⋅ 20 (=1)
20= 83-1⋅63 eingesetzt in die Zeile drüber: 1 = 7⋅63 -22⋅(83 -1⋅ 63)
= 7⋅63 -22⋅83 +22⋅ 63)
= -22⋅83 +29⋅ 63 (=1)

Es gilt also: ggt(83,63)=1 = -22⋅83 +29⋅63

oder wenn man -22⋅83 auf die linke Seite bringt:

1 +22⋅83 = +29⋅63

Es gilt also: 29⋅63 = 22⋅83 +1

Somit 29⋅63 = 1 mod 83

29 ist also das Inverse von 63 mod 83

Schlüsselpaar für RSA

Beispiel:

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