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: (25002 - 24995) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(25002 - 24995) mod 5 ≡ (25002 mod 5 - 24995 mod 5) mod 5.

25002 mod 5 ≡ 2 mod 5 kann man relativ leicht bestimmen, weil ja 25002 = 25000+2 = 5 ⋅ 5000 +2.

24995 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 24995 = 24000+995 = 5 ⋅ 4800 +995.

Somit gilt:

(25002 - 24995) mod 5 ≡ (2 - 0) mod 5 ≡ 2 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (88 ⋅ 59) mod 6.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(88 ⋅ 59) mod 6 ≡ (88 mod 6 ⋅ 59 mod 6) mod 6.

88 mod 6 ≡ 4 mod 6 kann man relativ leicht bestimmen, weil ja 88 = 84 + 4 = 14 ⋅ 6 + 4 ist.

59 mod 6 ≡ 5 mod 6 kann man relativ leicht bestimmen, weil ja 59 = 54 + 5 = 9 ⋅ 6 + 5 ist.

Somit gilt:

(88 ⋅ 59) mod 6 ≡ (4 ⋅ 5) mod 6 ≡ 20 mod 6 ≡ 2 mod 6.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 50916 mod 571.

Lösung einblenden

Die 16 im Exponent ist ja ein reine 2er-Potenz (24).

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. 509 -> x
2. mod(x²,571) -> 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: 5091=509

2: 5092=5091+1=5091⋅5091 ≡ 509⋅509=259081 ≡ 418 mod 571

4: 5094=5092+2=5092⋅5092 ≡ 418⋅418=174724 ≡ 569 mod 571

8: 5098=5094+4=5094⋅5094 ≡ 569⋅569=323761 ≡ 4 mod 571

16: 50916=5098+8=5098⋅5098 ≡ 4⋅4=16 ≡ 16 mod 571

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 452119 mod 641.

Lösung einblenden

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

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

119 = 64+32+16+4+2+1

1: 4521=452

2: 4522=4521+1=4521⋅4521 ≡ 452⋅452=204304 ≡ 466 mod 641

4: 4524=4522+2=4522⋅4522 ≡ 466⋅466=217156 ≡ 498 mod 641

8: 4528=4524+4=4524⋅4524 ≡ 498⋅498=248004 ≡ 578 mod 641

16: 45216=4528+8=4528⋅4528 ≡ 578⋅578=334084 ≡ 123 mod 641

32: 45232=45216+16=45216⋅45216 ≡ 123⋅123=15129 ≡ 386 mod 641

64: 45264=45232+32=45232⋅45232 ≡ 386⋅386=148996 ≡ 284 mod 641

452119

= 45264+32+16+4+2+1

= 45264⋅45232⋅45216⋅4524⋅4522⋅4521

284 ⋅ 386 ⋅ 123 ⋅ 498 ⋅ 466 ⋅ 452 mod 641
109624 ⋅ 123 ⋅ 498 ⋅ 466 ⋅ 452 mod 641 ≡ 13 ⋅ 123 ⋅ 498 ⋅ 466 ⋅ 452 mod 641
1599 ⋅ 498 ⋅ 466 ⋅ 452 mod 641 ≡ 317 ⋅ 498 ⋅ 466 ⋅ 452 mod 641
157866 ⋅ 466 ⋅ 452 mod 641 ≡ 180 ⋅ 466 ⋅ 452 mod 641
83880 ⋅ 452 mod 641 ≡ 550 ⋅ 452 mod 641
248600 mod 641 ≡ 533 mod 641

Es gilt also: 452119 ≡ 533 mod 641

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>53 = 1⋅44 + 9
=>44 = 4⋅9 + 8
=>9 = 1⋅8 + 1
=>8 = 8⋅1 + 0

also gilt: ggt(53,44)=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= 9-1⋅8
8= 44-4⋅9 eingesetzt in die Zeile drüber: 1 = 1⋅9 -1⋅(44 -4⋅ 9)
= 1⋅9 -1⋅44 +4⋅ 9)
= -1⋅44 +5⋅ 9 (=1)
9= 53-1⋅44 eingesetzt in die Zeile drüber: 1 = -1⋅44 +5⋅(53 -1⋅ 44)
= -1⋅44 +5⋅53 -5⋅ 44)
= 5⋅53 -6⋅ 44 (=1)

Es gilt also: ggt(53,44)=1 = 5⋅53 -6⋅44

oder wenn man 5⋅53 auf die linke Seite bringt:

1 -5⋅53 = -6⋅44

-6⋅44 = -5⋅53 + 1 |+53⋅44

-6⋅44 + 53⋅44 = -5⋅53 + 53⋅44 + 1

(-6 + 53) ⋅ 44 = (-5 + 44) ⋅ 53 + 1

47⋅44 = 39⋅53 + 1

Es gilt also: 47⋅44 = 39⋅53 +1

Somit 47⋅44 = 1 mod 53

47 ist also das Inverse von 44 mod 53

Schlüsselpaar für RSA

Beispiel:

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