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: (707 - 697) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(707 - 697) mod 7 ≡ (707 mod 7 - 697 mod 7) mod 7.

707 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 707 = 700+7 = 7 ⋅ 100 +7.

697 mod 7 ≡ 4 mod 7 kann man relativ leicht bestimmen, weil ja 697 = 700-3 = 7 ⋅ 100 -3 = 7 ⋅ 100 - 7 + 4.

Somit gilt:

(707 - 697) mod 7 ≡ (0 - 4) mod 7 ≡ -4 mod 7 ≡ 3 mod 7.

Modulo multiplizieren

Beispiel:

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

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(62 ⋅ 45) mod 11 ≡ (7 ⋅ 1) mod 11 ≡ 7 mod 11.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 28164 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. 281 -> 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: 2811=281

2: 2812=2811+1=2811⋅2811 ≡ 281⋅281=78961 ≡ 424 mod 557

4: 2814=2812+2=2812⋅2812 ≡ 424⋅424=179776 ≡ 422 mod 557

8: 2818=2814+4=2814⋅2814 ≡ 422⋅422=178084 ≡ 401 mod 557

16: 28116=2818+8=2818⋅2818 ≡ 401⋅401=160801 ≡ 385 mod 557

32: 28132=28116+16=28116⋅28116 ≡ 385⋅385=148225 ≡ 63 mod 557

64: 28164=28132+32=28132⋅28132 ≡ 63⋅63=3969 ≡ 70 mod 557

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 31271 mod 577.

Lösung einblenden

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

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

71 = 64+4+2+1

1: 3121=312

2: 3122=3121+1=3121⋅3121 ≡ 312⋅312=97344 ≡ 408 mod 577

4: 3124=3122+2=3122⋅3122 ≡ 408⋅408=166464 ≡ 288 mod 577

8: 3128=3124+4=3124⋅3124 ≡ 288⋅288=82944 ≡ 433 mod 577

16: 31216=3128+8=3128⋅3128 ≡ 433⋅433=187489 ≡ 541 mod 577

32: 31232=31216+16=31216⋅31216 ≡ 541⋅541=292681 ≡ 142 mod 577

64: 31264=31232+32=31232⋅31232 ≡ 142⋅142=20164 ≡ 546 mod 577

31271

= 31264+4+2+1

= 31264⋅3124⋅3122⋅3121

546 ⋅ 288 ⋅ 408 ⋅ 312 mod 577
157248 ⋅ 408 ⋅ 312 mod 577 ≡ 304 ⋅ 408 ⋅ 312 mod 577
124032 ⋅ 312 mod 577 ≡ 554 ⋅ 312 mod 577
172848 mod 577 ≡ 325 mod 577

Es gilt also: 31271 ≡ 325 mod 577

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>97 = 1⋅69 + 28
=>69 = 2⋅28 + 13
=>28 = 2⋅13 + 2
=>13 = 6⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(97,69)=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= 28-2⋅13 eingesetzt in die Zeile drüber: 1 = 1⋅13 -6⋅(28 -2⋅ 13)
= 1⋅13 -6⋅28 +12⋅ 13)
= -6⋅28 +13⋅ 13 (=1)
13= 69-2⋅28 eingesetzt in die Zeile drüber: 1 = -6⋅28 +13⋅(69 -2⋅ 28)
= -6⋅28 +13⋅69 -26⋅ 28)
= 13⋅69 -32⋅ 28 (=1)
28= 97-1⋅69 eingesetzt in die Zeile drüber: 1 = 13⋅69 -32⋅(97 -1⋅ 69)
= 13⋅69 -32⋅97 +32⋅ 69)
= -32⋅97 +45⋅ 69 (=1)

Es gilt also: ggt(97,69)=1 = -32⋅97 +45⋅69

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

1 +32⋅97 = +45⋅69

Es gilt also: 45⋅69 = 32⋅97 +1

Somit 45⋅69 = 1 mod 97

45 ist also das Inverse von 69 mod 97

Schlüsselpaar für RSA

Beispiel:

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