Cryptography Reference
In-Depth Information
4.1.1
Potenzen modulo n
Folgen von Potenzen in einem Galois-Körper
Für ein Beispiel wählen wir einen kleinen Galois-Körper GF(5) mit den 5 Elementen a
[0, 4],
vgl. Kap. 2.1.2. Der Körper basiert auf der Arithmetik modulo 5. Für jedes Element a bilden
wir die Folge der Potenzen a
1
, a
2
, a
3
,... Die Folgen sind in den einzelnen Spalten der Tab. 4-1
zu sehen. In einer Spalte erhalten wir die nächste Potenz durch Multiplikation mit a modulo 5.
Die Potenzen 0
i
sind alle 0 und die Potenzen von 1
i
sind alle 1. Die Zahl der 5 Elemente ist
endlich. Deshalb müssen in der Folge Wiederholungen und Zyklen auftreten.
Tab. 4-1: Folge der Potenzen, Modul n=5, Elemente a
[0, 4] aus GF(5)
a = a
1
0
1
2
3
4
a
2
0
1
4
4
1
a
3
0
1
3
2
4
a
4
0
1
1
1
1
a
5
0
1
2
3
4
Wir bemerken:
In der Spalte für a=2 und a=3 treten alle Elemente b0 auf. Das bedeutet, wir können alle
Elemente b0 als Potenz von a=2 bzw. a=3 darstellen (es gibt ein i so, dass b=a
i
). Elemente
mit dieser Eigenschaft werden als
Generator-Element
oder
Primitivwurzel
bezeichnet. Ge-
neratorelemente werden für das Diffie-Hellman-Verfahren (Kap. 4.3) und das ElGamal-
Verfahren (Kap. 4.4) benötigt.
Für jedes Element a0 ergibt die vierte Potenz den Wert 1, a
4
1 (mod5). Vermutete Ver-
allgemeinerung: 4=51=p1.
Für jedes Element (einschließlich a=0) ergibt sich a
5
a (mod5). Vermutete Verallgemeine-
rung: 5=p.
Der vermutete allgemeine Zusammenhang lautet:
p1
a
1
( od p)
für
a
[1, p
1]
(4.1-1)
p
aa( d )
f r
a[ , p ]
(4.1-2)
Die erste Formel (4.1-1) ist bekannt als
Kleiner Satz von Fermat
(Pierre de Fermat, 1601 -
1665, französischer Mathematiker), bzw. verallgemeinert als
Satz von Euler
(Leonhard Euler,
1707 - 1783, schweizer Mathematiker).
