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: (2806 + 21007) mod 7.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(2806 + 21007) mod 7 ≡ (2806 mod 7 + 21007 mod 7) mod 7.

2806 mod 7 ≡ 6 mod 7 kann man relativ leicht bestimmen, weil ja 2806 = 2800+6 = 7 ⋅ 400 +6.

21007 mod 7 ≡ 0 mod 7 kann man relativ leicht bestimmen, weil ja 21007 = 21000+7 = 7 ⋅ 3000 +7.

Somit gilt:

(2806 + 21007) mod 7 ≡ (6 + 0) mod 7 ≡ 6 mod 7.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (72 ⋅ 98) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(72 ⋅ 98) mod 5 ≡ (72 mod 5 ⋅ 98 mod 5) mod 5.

72 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 72 = 70 + 2 = 14 ⋅ 5 + 2 ist.

98 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 98 = 95 + 3 = 19 ⋅ 5 + 3 ist.

Somit gilt:

(72 ⋅ 98) mod 5 ≡ (2 ⋅ 3) mod 5 ≡ 6 mod 5 ≡ 1 mod 5.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 72332 mod 743.

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. 723 -> x
2. mod(x²,743) -> 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: 7231=723

2: 7232=7231+1=7231⋅7231 ≡ 723⋅723=522729 ≡ 400 mod 743

4: 7234=7232+2=7232⋅7232 ≡ 400⋅400=160000 ≡ 255 mod 743

8: 7238=7234+4=7234⋅7234 ≡ 255⋅255=65025 ≡ 384 mod 743

16: 72316=7238+8=7238⋅7238 ≡ 384⋅384=147456 ≡ 342 mod 743

32: 72332=72316+16=72316⋅72316 ≡ 342⋅342=116964 ≡ 313 mod 743

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 531118 mod 653.

Lösung einblenden

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

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

118 = 64+32+16+4+2

1: 5311=531

2: 5312=5311+1=5311⋅5311 ≡ 531⋅531=281961 ≡ 518 mod 653

4: 5314=5312+2=5312⋅5312 ≡ 518⋅518=268324 ≡ 594 mod 653

8: 5318=5314+4=5314⋅5314 ≡ 594⋅594=352836 ≡ 216 mod 653

16: 53116=5318+8=5318⋅5318 ≡ 216⋅216=46656 ≡ 293 mod 653

32: 53132=53116+16=53116⋅53116 ≡ 293⋅293=85849 ≡ 306 mod 653

64: 53164=53132+32=53132⋅53132 ≡ 306⋅306=93636 ≡ 257 mod 653

531118

= 53164+32+16+4+2

= 53164⋅53132⋅53116⋅5314⋅5312

257 ⋅ 306 ⋅ 293 ⋅ 594 ⋅ 518 mod 653
78642 ⋅ 293 ⋅ 594 ⋅ 518 mod 653 ≡ 282 ⋅ 293 ⋅ 594 ⋅ 518 mod 653
82626 ⋅ 594 ⋅ 518 mod 653 ≡ 348 ⋅ 594 ⋅ 518 mod 653
206712 ⋅ 518 mod 653 ≡ 364 ⋅ 518 mod 653
188552 mod 653 ≡ 488 mod 653

Es gilt also: 531118 ≡ 488 mod 653

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 68 ⋅ x ≡ 1 mod 71 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 71 und 68

=>71 = 1⋅68 + 3
=>68 = 22⋅3 + 2
=>3 = 1⋅2 + 1
=>2 = 2⋅1 + 0

also gilt: ggt(71,68)=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= 68-22⋅3 eingesetzt in die Zeile drüber: 1 = 1⋅3 -1⋅(68 -22⋅ 3)
= 1⋅3 -1⋅68 +22⋅ 3)
= -1⋅68 +23⋅ 3 (=1)
3= 71-1⋅68 eingesetzt in die Zeile drüber: 1 = -1⋅68 +23⋅(71 -1⋅ 68)
= -1⋅68 +23⋅71 -23⋅ 68)
= 23⋅71 -24⋅ 68 (=1)

Es gilt also: ggt(71,68)=1 = 23⋅71 -24⋅68

oder wenn man 23⋅71 auf die linke Seite bringt:

1 -23⋅71 = -24⋅68

-24⋅68 = -23⋅71 + 1 |+71⋅68

-24⋅68 + 71⋅68 = -23⋅71 + 71⋅68 + 1

(-24 + 71) ⋅ 68 = (-23 + 68) ⋅ 71 + 1

47⋅68 = 45⋅71 + 1

Es gilt also: 47⋅68 = 45⋅71 +1

Somit 47⋅68 = 1 mod 71

47 ist also das Inverse von 68 mod 71

Schlüsselpaar für RSA

Beispiel:

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