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: (3602 - 361) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3602 - 361) mod 9 ≡ (3602 mod 9 - 361 mod 9) mod 9.

3602 mod 9 ≡ 2 mod 9 kann man relativ leicht bestimmen, weil ja 3602 = 3600+2 = 9 ⋅ 400 +2.

361 mod 9 ≡ 1 mod 9 kann man relativ leicht bestimmen, weil ja 361 = 360+1 = 9 ⋅ 40 +1.

Somit gilt:

(3602 - 361) mod 9 ≡ (2 - 1) mod 9 ≡ 1 mod 9.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (67 ⋅ 45) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(67 ⋅ 45) mod 11 ≡ (67 mod 11 ⋅ 45 mod 11) mod 11.

67 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 67 = 66 + 1 = 6 ⋅ 11 + 1 ist.

45 mod 11 ≡ 1 mod 11 kann man relativ leicht bestimmen, weil ja 45 = 44 + 1 = 4 ⋅ 11 + 1 ist.

Somit gilt:

(67 ⋅ 45) mod 11 ≡ (1 ⋅ 1) mod 11 ≡ 1 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 27216 mod 467.

Lösung einblenden

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. 272 -> x
2. mod(x²,467) -> 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: 2721=272

2: 2722=2721+1=2721⋅2721 ≡ 272⋅272=73984 ≡ 198 mod 467

4: 2724=2722+2=2722⋅2722 ≡ 198⋅198=39204 ≡ 443 mod 467

8: 2728=2724+4=2724⋅2724 ≡ 443⋅443=196249 ≡ 109 mod 467

16: 27216=2728+8=2728⋅2728 ≡ 109⋅109=11881 ≡ 206 mod 467

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 214146 mod 233.

Lösung einblenden

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

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

146 = 128+16+2

1: 2141=214

2: 2142=2141+1=2141⋅2141 ≡ 214⋅214=45796 ≡ 128 mod 233

4: 2144=2142+2=2142⋅2142 ≡ 128⋅128=16384 ≡ 74 mod 233

8: 2148=2144+4=2144⋅2144 ≡ 74⋅74=5476 ≡ 117 mod 233

16: 21416=2148+8=2148⋅2148 ≡ 117⋅117=13689 ≡ 175 mod 233

32: 21432=21416+16=21416⋅21416 ≡ 175⋅175=30625 ≡ 102 mod 233

64: 21464=21432+32=21432⋅21432 ≡ 102⋅102=10404 ≡ 152 mod 233

128: 214128=21464+64=21464⋅21464 ≡ 152⋅152=23104 ≡ 37 mod 233

214146

= 214128+16+2

= 214128⋅21416⋅2142

37 ⋅ 175 ⋅ 128 mod 233
6475 ⋅ 128 mod 233 ≡ 184 ⋅ 128 mod 233
23552 mod 233 ≡ 19 mod 233

Es gilt also: 214146 ≡ 19 mod 233

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 43 ⋅ x ≡ 1 mod 101 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 101 und 43

=>101 = 2⋅43 + 15
=>43 = 2⋅15 + 13
=>15 = 1⋅13 + 2
=>13 = 6⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(101,43)=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= 13-6⋅2
2= 15-1⋅13 eingesetzt in die Zeile drüber: 1 = 1⋅13 -6⋅(15 -1⋅ 13)
= 1⋅13 -6⋅15 +6⋅ 13)
= -6⋅15 +7⋅ 13 (=1)
13= 43-2⋅15 eingesetzt in die Zeile drüber: 1 = -6⋅15 +7⋅(43 -2⋅ 15)
= -6⋅15 +7⋅43 -14⋅ 15)
= 7⋅43 -20⋅ 15 (=1)
15= 101-2⋅43 eingesetzt in die Zeile drüber: 1 = 7⋅43 -20⋅(101 -2⋅ 43)
= 7⋅43 -20⋅101 +40⋅ 43)
= -20⋅101 +47⋅ 43 (=1)

Es gilt also: ggt(101,43)=1 = -20⋅101 +47⋅43

oder wenn man -20⋅101 auf die linke Seite bringt:

1 +20⋅101 = +47⋅43

Es gilt also: 47⋅43 = 20⋅101 +1

Somit 47⋅43 = 1 mod 101

47 ist also das Inverse von 43 mod 101

Schlüsselpaar für RSA

Beispiel:

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