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: (351 - 2106) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(351 - 2106) mod 7 ≡ (351 mod 7 - 2106 mod 7) mod 7.

351 mod 7 ≡ 1 mod 7 kann man relativ leicht bestimmen, weil ja 351 = 350+1 = 7 ⋅ 50 +1.

2106 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 2106 = 2100+6 = 7 ⋅ 300 +6.

Somit gilt:

(351 - 2106) mod 7 ≡ (1 - 6) mod 7 ≡ -5 mod 7 ≡ 2 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (96 ⋅ 30) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(96 ⋅ 30) mod 6 ≡ (96 mod 6 ⋅ 30 mod 6) mod 6.

96 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 96 = 96 + 0 = 16 ⋅ 6 + 0 ist.

30 mod 6 ≡ 0 mod 6 kann man relativ leicht bestimmen, weil ja 30 = 30 + 0 = 5 ⋅ 6 + 0 ist.

Somit gilt:

(96 ⋅ 30) mod 6 ≡ (0 ⋅ 0) mod 6 ≡ 0 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 710128 mod 761.

Lösung einblenden

Die 128 im Exponent ist ja ein reine 2er-Potenz (27).

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. 710 -> x
2. mod(x²,761) -> 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: 7101=710

2: 7102=7101+1=7101⋅7101 ≡ 710⋅710=504100 ≡ 318 mod 761

4: 7104=7102+2=7102⋅7102 ≡ 318⋅318=101124 ≡ 672 mod 761

8: 7108=7104+4=7104⋅7104 ≡ 672⋅672=451584 ≡ 311 mod 761

16: 71016=7108+8=7108⋅7108 ≡ 311⋅311=96721 ≡ 74 mod 761

32: 71032=71016+16=71016⋅71016 ≡ 74⋅74=5476 ≡ 149 mod 761

64: 71064=71032+32=71032⋅71032 ≡ 149⋅149=22201 ≡ 132 mod 761

128: 710128=71064+64=71064⋅71064 ≡ 132⋅132=17424 ≡ 682 mod 761

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 638237 mod 839.

Lösung einblenden

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

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

237 = 128+64+32+8+4+1

1: 6381=638

2: 6382=6381+1=6381⋅6381 ≡ 638⋅638=407044 ≡ 129 mod 839

4: 6384=6382+2=6382⋅6382 ≡ 129⋅129=16641 ≡ 700 mod 839

8: 6388=6384+4=6384⋅6384 ≡ 700⋅700=490000 ≡ 24 mod 839

16: 63816=6388+8=6388⋅6388 ≡ 24⋅24=576 ≡ 576 mod 839

32: 63832=63816+16=63816⋅63816 ≡ 576⋅576=331776 ≡ 371 mod 839

64: 63864=63832+32=63832⋅63832 ≡ 371⋅371=137641 ≡ 45 mod 839

128: 638128=63864+64=63864⋅63864 ≡ 45⋅45=2025 ≡ 347 mod 839

638237

= 638128+64+32+8+4+1

= 638128⋅63864⋅63832⋅6388⋅6384⋅6381

347 ⋅ 45 ⋅ 371 ⋅ 24 ⋅ 700 ⋅ 638 mod 839
15615 ⋅ 371 ⋅ 24 ⋅ 700 ⋅ 638 mod 839 ≡ 513 ⋅ 371 ⋅ 24 ⋅ 700 ⋅ 638 mod 839
190323 ⋅ 24 ⋅ 700 ⋅ 638 mod 839 ≡ 709 ⋅ 24 ⋅ 700 ⋅ 638 mod 839
17016 ⋅ 700 ⋅ 638 mod 839 ≡ 236 ⋅ 700 ⋅ 638 mod 839
165200 ⋅ 638 mod 839 ≡ 756 ⋅ 638 mod 839
482328 mod 839 ≡ 742 mod 839

Es gilt also: 638237 ≡ 742 mod 839

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 46 ⋅ x ≡ 1 mod 59 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 59 und 46

=>59 = 1⋅46 + 13
=>46 = 3⋅13 + 7
=>13 = 1⋅7 + 6
=>7 = 1⋅6 + 1
=>6 = 6⋅1 + 0

also gilt: ggt(59,46)=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= 7-1⋅6
6= 13-1⋅7 eingesetzt in die Zeile drüber: 1 = 1⋅7 -1⋅(13 -1⋅ 7)
= 1⋅7 -1⋅13 +1⋅ 7)
= -1⋅13 +2⋅ 7 (=1)
7= 46-3⋅13 eingesetzt in die Zeile drüber: 1 = -1⋅13 +2⋅(46 -3⋅ 13)
= -1⋅13 +2⋅46 -6⋅ 13)
= 2⋅46 -7⋅ 13 (=1)
13= 59-1⋅46 eingesetzt in die Zeile drüber: 1 = 2⋅46 -7⋅(59 -1⋅ 46)
= 2⋅46 -7⋅59 +7⋅ 46)
= -7⋅59 +9⋅ 46 (=1)

Es gilt also: ggt(59,46)=1 = -7⋅59 +9⋅46

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

1 +7⋅59 = +9⋅46

Es gilt also: 9⋅46 = 7⋅59 +1

Somit 9⋅46 = 1 mod 59

9 ist also das Inverse von 46 mod 59

Schlüsselpaar für RSA

Beispiel:

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