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: (456 - 84) mod 9.

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

(456 - 84) mod 9 ≡ (456 mod 9 - 84 mod 9) mod 9.

456 mod 9 ≡ 6 mod 9 kann man relativ leicht bestimmen, weil ja 456 = 450+6 = 9 ⋅ 50 +6.

84 mod 9 ≡ 3 mod 9 kann man relativ leicht bestimmen, weil ja 84 = 90-6 = 9 ⋅ 10 -6 = 9 ⋅ 10 - 9 + 3.

Somit gilt:

(456 - 84) mod 9 ≡ (6 - 3) mod 9 ≡ 3 mod 9.

Modulo multiplizieren

Beispiel:

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

Lösung einblenden

Um längere Rechnungen zu vermeiden, rechnen wir:

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

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

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

Somit gilt:

(86 ⋅ 88) mod 10 ≡ (6 ⋅ 8) mod 10 ≡ 48 mod 10 ≡ 8 mod 10.

modulo Potenzieren einfach

Beispiel:

Berechne möglichst geschickt: 8268 mod 877.

Lösung einblenden

Die 8 im Exponent ist ja ein reine 2er-Potenz (23).

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. 826 -> x
2. mod(x²,877) -> 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: 8261=826

2: 8262=8261+1=8261⋅8261 ≡ 826⋅826=682276 ≡ 847 mod 877

4: 8264=8262+2=8262⋅8262 ≡ 847⋅847=717409 ≡ 23 mod 877

8: 8268=8264+4=8264⋅8264 ≡ 23⋅23=529 ≡ 529 mod 877

modulo Potenzieren große Zahlen

Beispiel:

Berechne möglichst geschickt: 660161 mod 811.

Lösung einblenden

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

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

161 = 128+32+1

1: 6601=660

2: 6602=6601+1=6601⋅6601 ≡ 660⋅660=435600 ≡ 93 mod 811

4: 6604=6602+2=6602⋅6602 ≡ 93⋅93=8649 ≡ 539 mod 811

8: 6608=6604+4=6604⋅6604 ≡ 539⋅539=290521 ≡ 183 mod 811

16: 66016=6608+8=6608⋅6608 ≡ 183⋅183=33489 ≡ 238 mod 811

32: 66032=66016+16=66016⋅66016 ≡ 238⋅238=56644 ≡ 685 mod 811

64: 66064=66032+32=66032⋅66032 ≡ 685⋅685=469225 ≡ 467 mod 811

128: 660128=66064+64=66064⋅66064 ≡ 467⋅467=218089 ≡ 741 mod 811

660161

= 660128+32+1

= 660128⋅66032⋅6601

741 ⋅ 685 ⋅ 660 mod 811
507585 ⋅ 660 mod 811 ≡ 710 ⋅ 660 mod 811
468600 mod 811 ≡ 653 mod 811

Es gilt also: 660161 ≡ 653 mod 811

erweiterter Euklid'scher Algorithmus

Beispiel:

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

Also bestimme x, so dass 72 ⋅ x ≡ 1 mod 97 gilt:

Lösung einblenden

Berechnung des größten gemeinsamen Teilers von 97 und 72

=>97 = 1⋅72 + 25
=>72 = 2⋅25 + 22
=>25 = 1⋅22 + 3
=>22 = 7⋅3 + 1
=>3 = 3⋅1 + 0

also gilt: ggt(97,72)=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= 22-7⋅3
3= 25-1⋅22 eingesetzt in die Zeile drüber: 1 = 1⋅22 -7⋅(25 -1⋅ 22)
= 1⋅22 -7⋅25 +7⋅ 22)
= -7⋅25 +8⋅ 22 (=1)
22= 72-2⋅25 eingesetzt in die Zeile drüber: 1 = -7⋅25 +8⋅(72 -2⋅ 25)
= -7⋅25 +8⋅72 -16⋅ 25)
= 8⋅72 -23⋅ 25 (=1)
25= 97-1⋅72 eingesetzt in die Zeile drüber: 1 = 8⋅72 -23⋅(97 -1⋅ 72)
= 8⋅72 -23⋅97 +23⋅ 72)
= -23⋅97 +31⋅ 72 (=1)

Es gilt also: ggt(97,72)=1 = -23⋅97 +31⋅72

oder wenn man -23⋅97 auf die linke Seite bringt:

1 +23⋅97 = +31⋅72

Es gilt also: 31⋅72 = 23⋅97 +1

Somit 31⋅72 = 1 mod 97

31 ist also das Inverse von 72 mod 97

Schlüsselpaar für RSA

Beispiel:

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