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: (1002 + 1499) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(1002 + 1499) mod 5 ≡ (1002 mod 5 + 1499 mod 5) mod 5.

1002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 1002 = 1000+2 = 5 ⋅ 200 +2.

1499 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 1499 = 1400+99 = 5 ⋅ 280 +99.

Somit gilt:

(1002 + 1499) mod 5 ≡ (2 + 4) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (63 ⋅ 83) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 83) mod 10 ≡ (63 mod 10 ⋅ 83 mod 10) mod 10.

63 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 63 = 60 + 3 = 6 ⋅ 10 + 3 ist.

83 mod 10 ≡ 3 mod 10 kann man relativ leicht bestimmen, weil ja 83 = 80 + 3 = 8 ⋅ 10 + 3 ist.

Somit gilt:

(63 ⋅ 83) mod 10 ≡ (3 ⋅ 3) mod 10 ≡ 9 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 10164 mod 269.

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²,269) -> 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 ≡ 248 mod 269

4: 1014=1012+2=1012⋅1012 ≡ 248⋅248=61504 ≡ 172 mod 269

8: 1018=1014+4=1014⋅1014 ≡ 172⋅172=29584 ≡ 263 mod 269

16: 10116=1018+8=1018⋅1018 ≡ 263⋅263=69169 ≡ 36 mod 269

32: 10132=10116+16=10116⋅10116 ≡ 36⋅36=1296 ≡ 220 mod 269

64: 10164=10132+32=10132⋅10132 ≡ 220⋅220=48400 ≡ 249 mod 269

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 292203 mod 349.

Lösung einblenden

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

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

203 = 128+64+8+2+1

1: 2921=292

2: 2922=2921+1=2921⋅2921 ≡ 292⋅292=85264 ≡ 108 mod 349

4: 2924=2922+2=2922⋅2922 ≡ 108⋅108=11664 ≡ 147 mod 349

8: 2928=2924+4=2924⋅2924 ≡ 147⋅147=21609 ≡ 320 mod 349

16: 29216=2928+8=2928⋅2928 ≡ 320⋅320=102400 ≡ 143 mod 349

32: 29232=29216+16=29216⋅29216 ≡ 143⋅143=20449 ≡ 207 mod 349

64: 29264=29232+32=29232⋅29232 ≡ 207⋅207=42849 ≡ 271 mod 349

128: 292128=29264+64=29264⋅29264 ≡ 271⋅271=73441 ≡ 151 mod 349

292203

= 292128+64+8+2+1

= 292128⋅29264⋅2928⋅2922⋅2921

151 ⋅ 271 ⋅ 320 ⋅ 108 ⋅ 292 mod 349
40921 ⋅ 320 ⋅ 108 ⋅ 292 mod 349 ≡ 88 ⋅ 320 ⋅ 108 ⋅ 292 mod 349
28160 ⋅ 108 ⋅ 292 mod 349 ≡ 240 ⋅ 108 ⋅ 292 mod 349
25920 ⋅ 292 mod 349 ≡ 94 ⋅ 292 mod 349
27448 mod 349 ≡ 226 mod 349

Es gilt also: 292203 ≡ 226 mod 349

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 75 ⋅ x ≡ 1 mod 79 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 79 und 75

=>79 = 1⋅75 + 4
=>75 = 18⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(79,75)=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= 4-1⋅3
3= 75-18⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(75 -18⋅ 4)
= 1⋅4 -1⋅75 +18⋅ 4)
= -1⋅75 +19⋅ 4 (=1)
4= 79-1⋅75 eingesetzt in die Zeile drüber: 1 = -1⋅75 +19⋅(79 -1⋅ 75)
= -1⋅75 +19⋅79 -19⋅ 75)
= 19⋅79 -20⋅ 75 (=1)

Es gilt also: ggt(79,75)=1 = 19⋅79 -20⋅75

oder wenn man 19⋅79 auf die linke Seite bringt:

1 -19⋅79 = -20⋅75

-20⋅75 = -19⋅79 + 1 |+79⋅75

-20⋅75 + 79⋅75 = -19⋅79 + 79⋅75 + 1

(-20 + 79) ⋅ 75 = (-19 + 75) ⋅ 79 + 1

59⋅75 = 56⋅79 + 1

Es gilt also: 59⋅75 = 56⋅79 +1

Somit 59⋅75 = 1 mod 79

59 ist also das Inverse von 75 mod 79

Schlüsselpaar für RSA

Beispiel:

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