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: (20001 + 399) mod 4.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(20001 + 399) mod 4 ≡ (20001 mod 4 + 399 mod 4) mod 4.

20001 mod 4 ≡ 1 mod 4 kann man relativ leicht bestimmen, weil ja 20001 = 20000+1 = 4 ⋅ 5000 +1.

399 mod 4 ≡ 3 mod 4 kann man relativ leicht bestimmen, weil ja 399 = 300+99 = 4 ⋅ 75 +99.

Somit gilt:

(20001 + 399) mod 4 ≡ (1 + 3) mod 4 ≡ 4 mod 4 ≡ 0 mod 4.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (69 ⋅ 20) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(69 ⋅ 20) mod 10 ≡ (69 mod 10 ⋅ 20 mod 10) mod 10.

69 mod 10 ≡ 9 mod 10 kann man relativ leicht bestimmen, weil ja 69 = 60 + 9 = 6 ⋅ 10 + 9 ist.

20 mod 10 ≡ 0 mod 10 kann man relativ leicht bestimmen, weil ja 20 = 20 + 0 = 2 ⋅ 10 + 0 ist.

Somit gilt:

(69 ⋅ 20) mod 10 ≡ (9 ⋅ 0) mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 584128 mod 829.

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. 584 -> x
2. mod(x²,829) -> 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: 5841=584

2: 5842=5841+1=5841⋅5841 ≡ 584⋅584=341056 ≡ 337 mod 829

4: 5844=5842+2=5842⋅5842 ≡ 337⋅337=113569 ≡ 825 mod 829

8: 5848=5844+4=5844⋅5844 ≡ 825⋅825=680625 ≡ 16 mod 829

16: 58416=5848+8=5848⋅5848 ≡ 16⋅16=256 ≡ 256 mod 829

32: 58432=58416+16=58416⋅58416 ≡ 256⋅256=65536 ≡ 45 mod 829

64: 58464=58432+32=58432⋅58432 ≡ 45⋅45=2025 ≡ 367 mod 829

128: 584128=58464+64=58464⋅58464 ≡ 367⋅367=134689 ≡ 391 mod 829

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 66974 mod 811.

Lösung einblenden

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

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

74 = 64+8+2

1: 6691=669

2: 6692=6691+1=6691⋅6691 ≡ 669⋅669=447561 ≡ 700 mod 811

4: 6694=6692+2=6692⋅6692 ≡ 700⋅700=490000 ≡ 156 mod 811

8: 6698=6694+4=6694⋅6694 ≡ 156⋅156=24336 ≡ 6 mod 811

16: 66916=6698+8=6698⋅6698 ≡ 6⋅6=36 ≡ 36 mod 811

32: 66932=66916+16=66916⋅66916 ≡ 36⋅36=1296 ≡ 485 mod 811

64: 66964=66932+32=66932⋅66932 ≡ 485⋅485=235225 ≡ 35 mod 811

66974

= 66964+8+2

= 66964⋅6698⋅6692

35 ⋅ 6 ⋅ 700 mod 811
210 ⋅ 700 mod 811
147000 mod 811 ≡ 209 mod 811

Es gilt also: 66974 ≡ 209 mod 811

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 30 ⋅ x ≡ 1 mod 53 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 53 und 30

=>53 = 1⋅30 + 23
=>30 = 1⋅23 + 7
=>23 = 3⋅7 + 2
=>7 = 3⋅2 + 1
=>2 = 2⋅1 + 0

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

Es gilt also: ggt(53,30)=1 = -13⋅53 +23⋅30

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

1 +13⋅53 = +23⋅30

Es gilt also: 23⋅30 = 13⋅53 +1

Somit 23⋅30 = 1 mod 53

23 ist also das Inverse von 30 mod 53

Schlüsselpaar für RSA

Beispiel:

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