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: (3000 - 5998) mod 3.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(3000 - 5998) mod 3 ≡ (3000 mod 3 - 5998 mod 3) mod 3.

3000 mod 3 ≡ 0 mod 3 kann man relativ leicht bestimmen, weil ja 3000 = 3000+0 = 3 ⋅ 1000 +0.

5998 mod 3 ≡ 1 mod 3 kann man relativ leicht bestimmen, weil ja 5998 = 6000-2 = 3 ⋅ 2000 -2 = 3 ⋅ 2000 - 3 + 1.

Somit gilt:

(3000 - 5998) mod 3 ≡ (0 - 1) mod 3 ≡ -1 mod 3 ≡ 2 mod 3.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (63 ⋅ 77) mod 11.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(63 ⋅ 77) mod 11 ≡ (63 mod 11 ⋅ 77 mod 11) mod 11.

63 mod 11 ≡ 8 mod 11 kann man relativ leicht bestimmen, weil ja 63 = 55 + 8 = 5 ⋅ 11 + 8 ist.

77 mod 11 ≡ 0 mod 11 kann man relativ leicht bestimmen, weil ja 77 = 77 + 0 = 7 ⋅ 11 + 0 ist.

Somit gilt:

(63 ⋅ 77) mod 11 ≡ (8 ⋅ 0) mod 11 ≡ 0 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 38264 mod 479.

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. 382 -> x
2. mod(x²,479) -> 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: 3821=382

2: 3822=3821+1=3821⋅3821 ≡ 382⋅382=145924 ≡ 308 mod 479

4: 3824=3822+2=3822⋅3822 ≡ 308⋅308=94864 ≡ 22 mod 479

8: 3828=3824+4=3824⋅3824 ≡ 22⋅22=484 ≡ 5 mod 479

16: 38216=3828+8=3828⋅3828 ≡ 5⋅5=25 ≡ 25 mod 479

32: 38232=38216+16=38216⋅38216 ≡ 25⋅25=625 ≡ 146 mod 479

64: 38264=38232+32=38232⋅38232 ≡ 146⋅146=21316 ≡ 240 mod 479

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 527159 mod 569.

Lösung einblenden

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

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

159 = 128+16+8+4+2+1

1: 5271=527

2: 5272=5271+1=5271⋅5271 ≡ 527⋅527=277729 ≡ 57 mod 569

4: 5274=5272+2=5272⋅5272 ≡ 57⋅57=3249 ≡ 404 mod 569

8: 5278=5274+4=5274⋅5274 ≡ 404⋅404=163216 ≡ 482 mod 569

16: 52716=5278+8=5278⋅5278 ≡ 482⋅482=232324 ≡ 172 mod 569

32: 52732=52716+16=52716⋅52716 ≡ 172⋅172=29584 ≡ 565 mod 569

64: 52764=52732+32=52732⋅52732 ≡ 565⋅565=319225 ≡ 16 mod 569

128: 527128=52764+64=52764⋅52764 ≡ 16⋅16=256 ≡ 256 mod 569

527159

= 527128+16+8+4+2+1

= 527128⋅52716⋅5278⋅5274⋅5272⋅5271

256 ⋅ 172 ⋅ 482 ⋅ 404 ⋅ 57 ⋅ 527 mod 569
44032 ⋅ 482 ⋅ 404 ⋅ 57 ⋅ 527 mod 569 ≡ 219 ⋅ 482 ⋅ 404 ⋅ 57 ⋅ 527 mod 569
105558 ⋅ 404 ⋅ 57 ⋅ 527 mod 569 ≡ 293 ⋅ 404 ⋅ 57 ⋅ 527 mod 569
118372 ⋅ 57 ⋅ 527 mod 569 ≡ 20 ⋅ 57 ⋅ 527 mod 569
1140 ⋅ 527 mod 569 ≡ 2 ⋅ 527 mod 569
1054 mod 569 ≡ 485 mod 569

Es gilt also: 527159 ≡ 485 mod 569

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 39 ⋅ x ≡ 1 mod 89 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 89 und 39

=>89 = 2⋅39 + 11
=>39 = 3⋅11 + 6
=>11 = 1⋅6 + 5
=>6 = 1⋅5 + 1
=>5 = 5⋅1 + 0

also gilt: ggt(89,39)=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= 6-1⋅5
5= 11-1⋅6 eingesetzt in die Zeile drüber: 1 = 1⋅6 -1⋅(11 -1⋅ 6)
= 1⋅6 -1⋅11 +1⋅ 6)
= -1⋅11 +2⋅ 6 (=1)
6= 39-3⋅11 eingesetzt in die Zeile drüber: 1 = -1⋅11 +2⋅(39 -3⋅ 11)
= -1⋅11 +2⋅39 -6⋅ 11)
= 2⋅39 -7⋅ 11 (=1)
11= 89-2⋅39 eingesetzt in die Zeile drüber: 1 = 2⋅39 -7⋅(89 -2⋅ 39)
= 2⋅39 -7⋅89 +14⋅ 39)
= -7⋅89 +16⋅ 39 (=1)

Es gilt also: ggt(89,39)=1 = -7⋅89 +16⋅39

oder wenn man -7⋅89 auf die linke Seite bringt:

1 +7⋅89 = +16⋅39

Es gilt also: 16⋅39 = 7⋅89 +1

Somit 16⋅39 = 1 mod 89

16 ist also das Inverse von 39 mod 89

Schlüsselpaar für RSA

Beispiel:

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