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: (23996 + 2399) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(23996 + 2399) mod 6 ≡ (23996 mod 6 + 2399 mod 6) mod 6.

23996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 23996 = 24000-4 = 6 ⋅ 4000 -4 = 6 ⋅ 4000 - 6 + 2.

2399 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 2399 = 2400-1 = 6 ⋅ 400 -1 = 6 ⋅ 400 - 6 + 5.

Somit gilt:

(23996 + 2399) mod 6 ≡ (2 + 5) mod 6 ≡ 7 mod 6 ≡ 1 mod 6.

Modulo multiplizieren

Beispiel:

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

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

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

32 mod 11 ≡ 10 mod 11 kann man relativ leicht bestimmen, weil ja 32 = 22 + 10 = 2 ⋅ 11 + 10 ist.

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

Somit gilt:

(32 ⋅ 67) mod 11 ≡ (10 ⋅ 1) mod 11 ≡ 10 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 51564 mod 557.

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. 515 -> x
2. mod(x²,557) -> 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: 5151=515

2: 5152=5151+1=5151⋅5151 ≡ 515⋅515=265225 ≡ 93 mod 557

4: 5154=5152+2=5152⋅5152 ≡ 93⋅93=8649 ≡ 294 mod 557

8: 5158=5154+4=5154⋅5154 ≡ 294⋅294=86436 ≡ 101 mod 557

16: 51516=5158+8=5158⋅5158 ≡ 101⋅101=10201 ≡ 175 mod 557

32: 51532=51516+16=51516⋅51516 ≡ 175⋅175=30625 ≡ 547 mod 557

64: 51564=51532+32=51532⋅51532 ≡ 547⋅547=299209 ≡ 100 mod 557

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 551156 mod 907.

Lösung einblenden

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

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

156 = 128+16+8+4

1: 5511=551

2: 5512=5511+1=5511⋅5511 ≡ 551⋅551=303601 ≡ 663 mod 907

4: 5514=5512+2=5512⋅5512 ≡ 663⋅663=439569 ≡ 581 mod 907

8: 5518=5514+4=5514⋅5514 ≡ 581⋅581=337561 ≡ 157 mod 907

16: 55116=5518+8=5518⋅5518 ≡ 157⋅157=24649 ≡ 160 mod 907

32: 55132=55116+16=55116⋅55116 ≡ 160⋅160=25600 ≡ 204 mod 907

64: 55164=55132+32=55132⋅55132 ≡ 204⋅204=41616 ≡ 801 mod 907

128: 551128=55164+64=55164⋅55164 ≡ 801⋅801=641601 ≡ 352 mod 907

551156

= 551128+16+8+4

= 551128⋅55116⋅5518⋅5514

352 ⋅ 160 ⋅ 157 ⋅ 581 mod 907
56320 ⋅ 157 ⋅ 581 mod 907 ≡ 86 ⋅ 157 ⋅ 581 mod 907
13502 ⋅ 581 mod 907 ≡ 804 ⋅ 581 mod 907
467124 mod 907 ≡ 19 mod 907

Es gilt also: 551156 ≡ 19 mod 907

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>97 = 1⋅75 + 22
=>75 = 3⋅22 + 9
=>22 = 2⋅9 + 4
=>9 = 2⋅4 + 1
=>4 = 4⋅1 + 0

also gilt: ggt(97,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= 9-2⋅4
4= 22-2⋅9 eingesetzt in die Zeile drüber: 1 = 1⋅9 -2⋅(22 -2⋅ 9)
= 1⋅9 -2⋅22 +4⋅ 9)
= -2⋅22 +5⋅ 9 (=1)
9= 75-3⋅22 eingesetzt in die Zeile drüber: 1 = -2⋅22 +5⋅(75 -3⋅ 22)
= -2⋅22 +5⋅75 -15⋅ 22)
= 5⋅75 -17⋅ 22 (=1)
22= 97-1⋅75 eingesetzt in die Zeile drüber: 1 = 5⋅75 -17⋅(97 -1⋅ 75)
= 5⋅75 -17⋅97 +17⋅ 75)
= -17⋅97 +22⋅ 75 (=1)

Es gilt also: ggt(97,75)=1 = -17⋅97 +22⋅75

oder wenn man -17⋅97 auf die linke Seite bringt:

1 +17⋅97 = +22⋅75

Es gilt also: 22⋅75 = 17⋅97 +1

Somit 22⋅75 = 1 mod 97

22 ist also das Inverse von 75 mod 97

Schlüsselpaar für RSA

Beispiel:

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