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: (5005 - 1498) mod 5.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(5005 - 1498) mod 5 ≡ (5005 mod 5 - 1498 mod 5) mod 5.

5005 mod 5 ≡ 0 mod 5 kann man relativ leicht bestimmen, weil ja 5005 = 5000+5 = 5 ⋅ 1000 +5.

1498 mod 5 ≡ 3 mod 5 kann man relativ leicht bestimmen, weil ja 1498 = 1400+98 = 5 ⋅ 280 +98.

Somit gilt:

(5005 - 1498) mod 5 ≡ (0 - 3) mod 5 ≡ -3 mod 5 ≡ 2 mod 5.

Modulo multiplizieren

Beispiel:

Berechne ohne WTR: (88 ⋅ 90) mod 10.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(88 ⋅ 90) mod 10 ≡ (88 mod 10 ⋅ 90 mod 10) mod 10.

88 mod 10 ≡ 8 mod 10 kann man relativ leicht bestimmen, weil ja 88 = 80 + 8 = 8 ⋅ 10 + 8 ist.

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

Somit gilt:

(88 ⋅ 90) mod 10 ≡ (8 ⋅ 0) mod 10 ≡ 0 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 28132 mod 631.

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. 281 -> x
2. mod(x²,631) -> 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: 2811=281

2: 2812=2811+1=2811⋅2811 ≡ 281⋅281=78961 ≡ 86 mod 631

4: 2814=2812+2=2812⋅2812 ≡ 86⋅86=7396 ≡ 455 mod 631

8: 2818=2814+4=2814⋅2814 ≡ 455⋅455=207025 ≡ 57 mod 631

16: 28116=2818+8=2818⋅2818 ≡ 57⋅57=3249 ≡ 94 mod 631

32: 28132=28116+16=28116⋅28116 ≡ 94⋅94=8836 ≡ 2 mod 631

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 511100 mod 653.

Lösung einblenden

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

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

100 = 64+32+4

1: 5111=511

2: 5112=5111+1=5111⋅5111 ≡ 511⋅511=261121 ≡ 574 mod 653

4: 5114=5112+2=5112⋅5112 ≡ 574⋅574=329476 ≡ 364 mod 653

8: 5118=5114+4=5114⋅5114 ≡ 364⋅364=132496 ≡ 590 mod 653

16: 51116=5118+8=5118⋅5118 ≡ 590⋅590=348100 ≡ 51 mod 653

32: 51132=51116+16=51116⋅51116 ≡ 51⋅51=2601 ≡ 642 mod 653

64: 51164=51132+32=51132⋅51132 ≡ 642⋅642=412164 ≡ 121 mod 653

511100

= 51164+32+4

= 51164⋅51132⋅5114

121 ⋅ 642 ⋅ 364 mod 653
77682 ⋅ 364 mod 653 ≡ 628 ⋅ 364 mod 653
228592 mod 653 ≡ 42 mod 653

Es gilt also: 511100 ≡ 42 mod 653

erweiterter Euklid'scher Algorithmus

Beispiel:

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

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

Lösung einblenden

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

=>67 = 1⋅50 + 17
=>50 = 2⋅17 + 16
=>17 = 1⋅16 + 1
=>16 = 16⋅1 + 0

also gilt: ggt(67,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= 17-1⋅16
16= 50-2⋅17 eingesetzt in die Zeile drüber: 1 = 1⋅17 -1⋅(50 -2⋅ 17)
= 1⋅17 -1⋅50 +2⋅ 17)
= -1⋅50 +3⋅ 17 (=1)
17= 67-1⋅50 eingesetzt in die Zeile drüber: 1 = -1⋅50 +3⋅(67 -1⋅ 50)
= -1⋅50 +3⋅67 -3⋅ 50)
= 3⋅67 -4⋅ 50 (=1)

Es gilt also: ggt(67,50)=1 = 3⋅67 -4⋅50

oder wenn man 3⋅67 auf die linke Seite bringt:

1 -3⋅67 = -4⋅50

-4⋅50 = -3⋅67 + 1 |+67⋅50

-4⋅50 + 67⋅50 = -3⋅67 + 67⋅50 + 1

(-4 + 67) ⋅ 50 = (-3 + 50) ⋅ 67 + 1

63⋅50 = 47⋅67 + 1

Es gilt also: 63⋅50 = 47⋅67 +1

Somit 63⋅50 = 1 mod 67

63 ist also das Inverse von 50 mod 67

Schlüsselpaar für RSA

Beispiel:

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