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: (2996 - 5995) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2996 - 5995) mod 6 ≡ (2996 mod 6 - 5995 mod 6) mod 6.

2996 mod 6 ≡ 2 mod 6 kann man relativ leicht bestimmen, weil ja 2996 = 3000-4 = 6 ⋅ 500 -4 = 6 ⋅ 500 - 6 + 2.

5995 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 5995 = 6000-5 = 6 ⋅ 1000 -5 = 6 ⋅ 1000 - 6 + 1.

Somit gilt:

(2996 - 5995) mod 6 ≡ (2 - 1) mod 6 ≡ 1 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (22 ⋅ 15) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(22 ⋅ 15) mod 6 ≡ (22 mod 6 ⋅ 15 mod 6) mod 6.

22 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 22 = 18 + 4 = 3 ⋅ 6 + 4 ist.

15 mod 6 ≡ 3 mod 6 kann man relativ leicht bestimmen, weil ja 15 = 12 + 3 = 2 ⋅ 6 + 3 ist.

Somit gilt:

(22 ⋅ 15) mod 6 ≡ (4 ⋅ 3) mod 6 ≡ 12 mod 6 ≡ 0 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 45132 mod 607.

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. 451 -> x
2. mod(x²,607) -> 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: 4511=451

2: 4512=4511+1=4511⋅4511 ≡ 451⋅451=203401 ≡ 56 mod 607

4: 4514=4512+2=4512⋅4512 ≡ 56⋅56=3136 ≡ 101 mod 607

8: 4518=4514+4=4514⋅4514 ≡ 101⋅101=10201 ≡ 489 mod 607

16: 45116=4518+8=4518⋅4518 ≡ 489⋅489=239121 ≡ 570 mod 607

32: 45132=45116+16=45116⋅45116 ≡ 570⋅570=324900 ≡ 155 mod 607

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 388145 mod 599.

Lösung einblenden

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

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

145 = 128+16+1

1: 3881=388

2: 3882=3881+1=3881⋅3881 ≡ 388⋅388=150544 ≡ 195 mod 599

4: 3884=3882+2=3882⋅3882 ≡ 195⋅195=38025 ≡ 288 mod 599

8: 3888=3884+4=3884⋅3884 ≡ 288⋅288=82944 ≡ 282 mod 599

16: 38816=3888+8=3888⋅3888 ≡ 282⋅282=79524 ≡ 456 mod 599

32: 38832=38816+16=38816⋅38816 ≡ 456⋅456=207936 ≡ 83 mod 599

64: 38864=38832+32=38832⋅38832 ≡ 83⋅83=6889 ≡ 300 mod 599

128: 388128=38864+64=38864⋅38864 ≡ 300⋅300=90000 ≡ 150 mod 599

388145

= 388128+16+1

= 388128⋅38816⋅3881

150 ⋅ 456 ⋅ 388 mod 599
68400 ⋅ 388 mod 599 ≡ 114 ⋅ 388 mod 599
44232 mod 599 ≡ 505 mod 599

Es gilt also: 388145 ≡ 505 mod 599

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 25 ⋅ x ≡ 1 mod 61 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 61 und 25

=>61 = 2⋅25 + 11
=>25 = 2⋅11 + 3
=>11 = 3⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(61,25)=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= 3-1⋅2
2= 11-3⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(11 -3⋅ 3)
= 1⋅3 -1⋅11 +3⋅ 3)
= -1⋅11 +4⋅ 3 (=1)
3= 25-2⋅11 eingesetzt in die Zeile drüber: 1 = -1⋅11 +4⋅(25 -2⋅ 11)
= -1⋅11 +4⋅25 -8⋅ 11)
= 4⋅25 -9⋅ 11 (=1)
11= 61-2⋅25 eingesetzt in die Zeile drüber: 1 = 4⋅25 -9⋅(61 -2⋅ 25)
= 4⋅25 -9⋅61 +18⋅ 25)
= -9⋅61 +22⋅ 25 (=1)

Es gilt also: ggt(61,25)=1 = -9⋅61 +22⋅25

oder wenn man -9⋅61 auf die linke Seite bringt:

1 +9⋅61 = +22⋅25

Es gilt also: 22⋅25 = 9⋅61 +1

Somit 22⋅25 = 1 mod 61

22 ist also das Inverse von 25 mod 61

Schlüsselpaar für RSA

Beispiel:

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