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: (119 - 402) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(119 - 402) mod 4 ≡ (119 mod 4 - 402 mod 4) mod 4.

119 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 119 = 120-1 = 4 ⋅ 30 -1 = 4 ⋅ 30 - 4 + 3.

402 mod 4 ≡ 2 mod 4 kann man relativ leicht bestimmen, weil ja 402 = 400+2 = 4 ⋅ 100 +2.

Somit gilt:

(119 - 402) mod 4 ≡ (3 - 2) mod 4 ≡ 1 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (40 ⋅ 42) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(40 ⋅ 42) mod 9 ≡ (40 mod 9 ⋅ 42 mod 9) mod 9.

40 mod 9 ≡ 4 mod 9 kann man relativ leicht bestimmen, weil ja 40 = 36 + 4 = 4 ⋅ 9 + 4 ist.

42 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 42 = 36 + 6 = 4 ⋅ 9 + 6 ist.

Somit gilt:

(40 ⋅ 42) mod 9 ≡ (4 ⋅ 6) mod 9 ≡ 24 mod 9 ≡ 6 mod 9.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 34032 mod 421.

Lösung einblenden

Die 32 im Exponent ist ja ein reine 2er-Potenz (25).

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. 340 -> x
2. mod(x²,421) -> 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: 3401=340

2: 3402=3401+1=3401⋅3401 ≡ 340⋅340=115600 ≡ 246 mod 421

4: 3404=3402+2=3402⋅3402 ≡ 246⋅246=60516 ≡ 313 mod 421

8: 3408=3404+4=3404⋅3404 ≡ 313⋅313=97969 ≡ 297 mod 421

16: 34016=3408+8=3408⋅3408 ≡ 297⋅297=88209 ≡ 220 mod 421

32: 34032=34016+16=34016⋅34016 ≡ 220⋅220=48400 ≡ 406 mod 421

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 454142 mod 761.

Lösung einblenden

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

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

142 = 128+8+4+2

1: 4541=454

2: 4542=4541+1=4541⋅4541 ≡ 454⋅454=206116 ≡ 646 mod 761

4: 4544=4542+2=4542⋅4542 ≡ 646⋅646=417316 ≡ 288 mod 761

8: 4548=4544+4=4544⋅4544 ≡ 288⋅288=82944 ≡ 756 mod 761

16: 45416=4548+8=4548⋅4548 ≡ 756⋅756=571536 ≡ 25 mod 761

32: 45432=45416+16=45416⋅45416 ≡ 25⋅25=625 ≡ 625 mod 761

64: 45464=45432+32=45432⋅45432 ≡ 625⋅625=390625 ≡ 232 mod 761

128: 454128=45464+64=45464⋅45464 ≡ 232⋅232=53824 ≡ 554 mod 761

454142

= 454128+8+4+2

= 454128⋅4548⋅4544⋅4542

554 ⋅ 756 ⋅ 288 ⋅ 646 mod 761
418824 ⋅ 288 ⋅ 646 mod 761 ≡ 274 ⋅ 288 ⋅ 646 mod 761
78912 ⋅ 646 mod 761 ≡ 529 ⋅ 646 mod 761
341734 mod 761 ≡ 45 mod 761

Es gilt also: 454142 ≡ 45 mod 761

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>97 = 1⋅64 + 33
=>64 = 1⋅33 + 31
=>33 = 1⋅31 + 2
=>31 = 15⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(97,64)=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= 31-15⋅2
2= 33-1⋅31 eingesetzt in die Zeile drüber: 1 = 1⋅31 -15⋅(33 -1⋅ 31)
= 1⋅31 -15⋅33 +15⋅ 31)
= -15⋅33 +16⋅ 31 (=1)
31= 64-1⋅33 eingesetzt in die Zeile drüber: 1 = -15⋅33 +16⋅(64 -1⋅ 33)
= -15⋅33 +16⋅64 -16⋅ 33)
= 16⋅64 -31⋅ 33 (=1)
33= 97-1⋅64 eingesetzt in die Zeile drüber: 1 = 16⋅64 -31⋅(97 -1⋅ 64)
= 16⋅64 -31⋅97 +31⋅ 64)
= -31⋅97 +47⋅ 64 (=1)

Es gilt also: ggt(97,64)=1 = -31⋅97 +47⋅64

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

1 +31⋅97 = +47⋅64

Es gilt also: 47⋅64 = 31⋅97 +1

Somit 47⋅64 = 1 mod 97

47 ist also das Inverse von 64 mod 97

Schlüsselpaar für RSA

Beispiel:

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