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: (299 + 61) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(299 + 61) mod 6 ≡ (299 mod 6 + 61 mod 6) mod 6.

299 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 299 = 300-1 = 6 ⋅ 50 -1 = 6 ⋅ 50 - 6 + 5.

61 mod 6 ≡ 1 mod 6 kann man relativ leicht bestimmen, weil ja 61 = 60+1 = 6 ⋅ 10 +1.

Somit gilt:

(299 + 61) mod 6 ≡ (5 + 1) mod 6 ≡ 6 mod 6 ≡ 0 mod 6.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (24 ⋅ 77) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(24 ⋅ 77) mod 5 ≡ (24 mod 5 ⋅ 77 mod 5) mod 5.

24 mod 5 ≡ 4 mod 5 kann man relativ leicht bestimmen, weil ja 24 = 20 + 4 = 4 ⋅ 5 + 4 ist.

77 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 77 = 75 + 2 = 15 ⋅ 5 + 2 ist.

Somit gilt:

(24 ⋅ 77) mod 5 ≡ (4 ⋅ 2) mod 5 ≡ 8 mod 5 ≡ 3 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 21432 mod 467.

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. 214 -> x
2. mod(x²,467) -> 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: 2141=214

2: 2142=2141+1=2141⋅2141 ≡ 214⋅214=45796 ≡ 30 mod 467

4: 2144=2142+2=2142⋅2142 ≡ 30⋅30=900 ≡ 433 mod 467

8: 2148=2144+4=2144⋅2144 ≡ 433⋅433=187489 ≡ 222 mod 467

16: 21416=2148+8=2148⋅2148 ≡ 222⋅222=49284 ≡ 249 mod 467

32: 21432=21416+16=21416⋅21416 ≡ 249⋅249=62001 ≡ 357 mod 467

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 575164 mod 647.

Lösung einblenden

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

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

164 = 128+32+4

1: 5751=575

2: 5752=5751+1=5751⋅5751 ≡ 575⋅575=330625 ≡ 8 mod 647

4: 5754=5752+2=5752⋅5752 ≡ 8⋅8=64 ≡ 64 mod 647

8: 5758=5754+4=5754⋅5754 ≡ 64⋅64=4096 ≡ 214 mod 647

16: 57516=5758+8=5758⋅5758 ≡ 214⋅214=45796 ≡ 506 mod 647

32: 57532=57516+16=57516⋅57516 ≡ 506⋅506=256036 ≡ 471 mod 647

64: 57564=57532+32=57532⋅57532 ≡ 471⋅471=221841 ≡ 567 mod 647

128: 575128=57564+64=57564⋅57564 ≡ 567⋅567=321489 ≡ 577 mod 647

575164

= 575128+32+4

= 575128⋅57532⋅5754

577 ⋅ 471 ⋅ 64 mod 647
271767 ⋅ 64 mod 647 ≡ 27 ⋅ 64 mod 647
1728 mod 647 ≡ 434 mod 647

Es gilt also: 575164 ≡ 434 mod 647

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 50 ⋅ x ≡ 1 mod 73 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 73 und 50

=>73 = 1⋅50 + 23
=>50 = 2⋅23 + 4
=>23 = 5⋅4 + 3
=>4 = 1⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(73,50)=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= 4-1⋅3
3= 23-5⋅4 eingesetzt in die Zeile drüber: 1 = 1⋅4 -1⋅(23 -5⋅ 4)
= 1⋅4 -1⋅23 +5⋅ 4)
= -1⋅23 +6⋅ 4 (=1)
4= 50-2⋅23 eingesetzt in die Zeile drüber: 1 = -1⋅23 +6⋅(50 -2⋅ 23)
= -1⋅23 +6⋅50 -12⋅ 23)
= 6⋅50 -13⋅ 23 (=1)
23= 73-1⋅50 eingesetzt in die Zeile drüber: 1 = 6⋅50 -13⋅(73 -1⋅ 50)
= 6⋅50 -13⋅73 +13⋅ 50)
= -13⋅73 +19⋅ 50 (=1)

Es gilt also: ggt(73,50)=1 = -13⋅73 +19⋅50

oder wenn man -13⋅73 auf die linke Seite bringt:

1 +13⋅73 = +19⋅50

Es gilt also: 19⋅50 = 13⋅73 +1

Somit 19⋅50 = 1 mod 73

19 ist also das Inverse von 50 mod 73

Schlüsselpaar für RSA

Beispiel:

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