Cryptography Reference
In-Depth Information
Aus dem Beispiel von (2.1-17) / (2.1-18) kann herausgelesen werden, dass ggT(n, a) allge-
mein als Linearkombination LK(n, a) entsprechend (2.1-14) darstellbar ist.
Der Euklidische Algorithmus ist auch für sehr große Zahlen von n anwendbar. Die Zahl der
Ersetzungsschritte steigt ungefähr nur linear mit der Stellenlänge von n. (Die Länge der Folge
1·a, 2·a, 3·a, … steigt dagegen exponentiell mit der Stellenlänge von n.)
2.1.4 Übungen
Übung 1
Weisen Sie die Erfüllung von Axiom 6 für das Produkt a·b in Arithmetik modulo n in entspre-
chender Weise wie für Axiom 1 nach (vgl. Kap. 2.1.2.1 Formel (2.1-6)).
Lösung
a·b(a+i·n)·(b+j·n)=a·b+n·(a·j+b·i+i·j·n)(a·b)mod n. Das Ergebnis (a·b)mod n hängt nur von a
und b, nicht aber von i und j ab.
Übung 2
a) Stellen Sie die Multiplikationstafel für die Arithmetik modulo 6 auf. Zu welchen Elementen
0 existiert kein multiplikativ inverses Element?
Lösung
• 0 1 2 3 4 5 Produkt modulo 6
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1
Zu den Elementen 2, 3 und 4 existiert kein multiplikativ inverses Element. Sie sind nicht teiler-
fremd zu dem Modul n=6. Die Elemente 1 und 5 sind zu sich selbst multiplikativ invers.
b) Zeichnen Sie entsprechend Abb. 2-2 die Folge der Produkte 1·a, 2·a, 3·a als Folge der Pfeile
für a=4 und a=5.
Lösung
a = 4
a = 5
0
0
5
1
5
1
4
2
4
2
3
3
Search WWH ::




Custom Search