Spur-kompatible Polynomfolgen über endlichen Körpern

Alfred Scheerhorn Deutsche Bundespost Telekom Forschungs- und Technologiezentrum, FZ 123b 64276 Darmstadt Germany

1 Einführung

Spur-kompatible Polynomfolgen über endlichen Körpern finden Anwendung in der Computeralgebra bei der Implementierung des algebraischen Abschlusses endlicher Körper (siehe [5]). Es wird beschrieben, wie in einigen speziellen Fällen sehr schnell spur-kompatible Folgen erzeugt werden können. Die Beweise sämtlicher hier aufgeführter Sätze findet man in [5].

Die Definition des Begriffes Spur-Kompatibilität erfordert einige Vorbereitungen. Es bezeichne q > 1 eine Primzahlpotenz und K = GF(q) den endlichen Körper der Ordnung q. Sei α ein Element des Erweiterungskörpers E = GF(q^{m}), m ∈ IN, und E die kleinste Erweiterung von GF(q), die α enthält. Die Elemente

α, α^{q}, …, α^{q^{m−1}}

heißen die Konjugierten von α über GF(q). Die Spur T_{E/K}(α) von α über GF(q) ist definiert als die Summe der Konjugierten von α über GF(q):

T_{E/K}(α) = ∑_{i=0}^{m−1} α^{q^{i}}.

Eine Basis {α, α^{q}, …, α^{q^{m−1}}} von GF(q^{m}) über GF(q), die aus den Konjugierten eines Elements α ∈ GF(q^{m}) besteht, wird Normalbasis genannt. Erzeugt α eine Normalbasis von GF(q^{m}) über GF(q), dann heißt α normal in GF(q^{m}) über GF(q). Mit α wird auch das Minimalpolynom

f(X) = ∏_{i=0}^{m−1}(X − α^{q^{i}}) ∈ GF(q)[X]

von α über GF(q) normal genannt.

Zur die Definition der Kompatibilität sei I eine unter Teilbarkeit abgeschlossenen Menge natürlicher Zahlen, d.h. mit n ∈ I gehören auch alle Teiler von n zu I.

Definition 1 Eine Folge (α_{n})_{n∈I} von Elementen α_{n} ∈ GF(q^{n}) heißt spur-kompati-bel über GF(q), wenn für alle n ∈ I gilt:

1. α_{n} ist normal in GF(q^{n}) über GF(q) und

2. Für alle Teiler d von n gilt für die Spur T_{n:d}(α_{n}) von GF(q^{n}) auf GF(q^{d}):

T_{n:d}(α_{n}) = α_{d}.

Eine Folge (f_{n})_{n∈I} von Polynomen f_{n} ∈ GF(q)[X], deg(f_{n}) = n, heißt spur-kompa-tibel über GF(q), wenn für alle n ∈ I gilt:

1. f_{n} ist normal über GF(q) und

2. Für jede Wurzel α ∈ GF(q^{n}) von f_{n} ist die Spur T_{n:d}(α) von α über GF(q^{d}) eine Wurzel von f_{d}, für alle Teiler d von n.

Die Existenz spur-kompatibler Elementefolgen (α_{n})_{n∈IN} wird in [4] bewiesen.

Sei nun (α_{n})_{n∈IN} spur-kompatible über GF(q). Wenn man für alle n ∈ IN die Elemente von GF(q^{n}) bezüglich der von α_{n} erzeugten Normalbasis darstellt, erhält man leicht berechenbare Einbettungen zwischen den Normalbasis-Darstellungen verschiedener Erweitrungen: γ ∈ GF(q^{d}) habe die Darstellung

γ = ∑_{i=0}^{d−1} c_{i}α_{d}^{q^{i}}, c_{i} ∈ GF(q),

bezüglich der von α_{d} erzeugten Normalbasis. Wegen

T_{m:d}(α_{m}) = ∑_{j=0}^{(m/d)−1} α^{q^{dj}} = α_{d},

folgt nun

γ = ∑_{i=0}^{d−1} c_{i}T_{m:d}(α_{m})^{q^{i}} = ∑_{i=0}^{d−1} c_{i} ∑_{j=0}^{(m/d)−1} α_{m}^{q^{jd+i}} = ∑_{i=0}^{m−1} c_{(i mod d)}α_{m}^{q^{i}}.

Die Einbettung der Normalbasis-Darstellung von GF(q^{d}) in die von GF(q^{m}) entspricht somit einer (m/d)-fachen Konkatenation des Koordinatenvektors (c_{0}, c_{1}, …, c_{d−1}) von γ.

Mit dem folgendem Satz läßt sich die Bestimmung eines spur-kompatiblen Elementes in GF(q^{n}), n = ∏ p^{e_{p}}, reduzieren auf die Bestimmung spur-kompatibler Elemente in den Erweiterungen der Primzahlpotenzgrade p^{e_{p}} über GF(q).

Satz 1 Für Primzahlen p seien bereits spur-kompatible Elementefolgen (α_{p^{e}})_{e≥0} über GF(q) gegeben. Dann ist die Folge (α_{n})_{n≥1} spur-kompatibel über GF(q), wenn für alle zusammengesetzten n ∈ IN mit der Primfaktorisierung n = ∏_{i=1}^{r} p_{i}^{e_{i}} definiert wird:

α_{n} = α_{1}^{1−r} ∏_{i=1}^{r} α_{p_{i}^{e_{i}}}.

In [5] Kapitel 2.6 wird ein Algorithmus zur Berechnung spur-kompatibler Elementefolgen (α_{p^{e}})_{e≥0}, p prim, über GF(q) beschrieben, der eine Komplexität von O(m^{3} log m log q) GF(q)-Operationen hat. Wir beschreiben im folgenden, wie für spezielle Paare (q, p) auf einfachere Weise spur-kompatible Folgen berechnet werden können.

2 Der Fall char(GF(q)) = p

Diese Situation ist aus der Artin-Schreier-Theorie wohlbekannt. Die Untersuchungen orientieren sich an Trinomen der Form

X^{p} − X − α.

Hier gilt ein sehr einfaches Normalitätskriterium: Ein Element α_{n} vom Grad p^{n} über GF(q) ist genau dann normal über GF(q), wenn die Spur von α_{n} über GF(q) ungleich 0 ist. Diese Spur ist am Minimalpolynom von α_{n} über GF(q) ablesbar.

Zur Beschreibung des folgenden Ergebnisses benötigen wir reziproke Polynome. Für f(X) = X^{m} + a_{m−1}X^{m−1} + … + a_{1}X + a_{0} aus GF(q)[X] heißt

f^{∗}(X) := \frac{1}{a_{0}} (a_{0}X^{m} + a_{1}X^{m−1} + … + a_{m−1}X + 1) = \frac{1}{a_{0}} X^{m}f(\frac{1}{X})

das zu f reziproke Polynom.

Satz 2 Sei K = GF(q) ein endlicher Körper der Charakteristik p und β_{0} ∈ K mit absoluter Spur T_{K}(β_{0}) ≠ 0 und T_{K}(β_{0}^{−1}) ≠ 0. Weiter sei f_{1}(X) = X^{p} − X − β_{0}^{−1} ∈ K[X]. Für n > 0 definieren wir bei ungeradem p rekursiv jedes Polynom g_{n} ∈ K[X] durch Wahl einer der drei Möglichkeiten

1. g_{n}(X) = −f_{n}^{∗}(−1 − X) oder

2. g_{n}(X) = −f_{n}^{∗}(1 − X) oder

3. X^{p^{n}}g_{n}(X − X^{−1}) = −f^{∗}(−X)f(X),

für p = 2 definieren wir g_{n}(X) = f_{n}^{∗}(X + 1). Unabhängig von der Charakteristik sei f_{n+1} ∈ K[X] durch f_{n+1}(X) = g_{n}^{∗}(X^{p} − X) definiert. Dann ist die Folge von Polynomen (g_{n})_{n≥1} spur-kompatibel über K.

Auf die folgende Weise läßt sich ein Element β_{0} ∈ K = GF(p^{r}) berechnen, dessen absolute Spur T_{K}(β_{0}) ≠ 0 ≠ T_{K}(β_{0}^{−1}) ist:

Gilt ggT(p, r) = 1, dann wählen wir β_{0} = 1 ∈ K und haben T_{K}(β_{0}) = T_{K}(β_{0}^{−1}) = r ≠ 0.

Gilt ggT(p, r) > 1 dann sei r = p^{s}u mit ggT(u, p) = 1. Jetzt liefert uns Satz 2 angewandt auf K = GF(p^{u}) und β_{0} = 1 ein Polynom g_{s} ∈ GF(p^{u})[X], dessen Wurzeln in GF(p^{r}) die gewünschten Bedingungen erfüllen.

3 Der Fall p = 2, q ungerade

Für geeignete Polynome f_{1} ∈ GF(q)[X] vom Grad 2 sind alle Polynome der Folge (f_{n})_{n≥1}, definiert durch

f_{n+1}(X) = (2X)^{2^{n}}f_{n}(\frac{X + X^{−1}}{2} ), n ≥ 1,

irreduzibel über GF(q) (vergleiche Cohen [2]). In [5] Kapitel 3.3 wird gezeigt, daß die Polynome dieser Folge (bei geeignetem f_{1}) für q ≡ ±3 mod 8 und q ≡ 9 mod 16 normal über GF(q) sind. Durch eine leichte Abänderung der obigen Rekursionsvorschrift zu

g_{n+1}(X) = X^{2^{n}}g_{n}(X + 2^{−2n}X^{−1}), n ≥ 1,

erhält man (bei geeignetem g_{1}) in den angegebenen Fällen eine spur-kompatible Polynomfolge. Wir vermuten, daß das dieses Verfahren unabhängig von q in ungerader Charakteristik eine spur-kompatible Polynomfolge liefert.

Satz 3 Sei q ≡ ±3 mod 8 oder q ≡ 9 mod 16 und sei g_{1} ∈ GF(q)[X] normiert, irreduzibel vom Grad 2 und normal über GF(q). Im Falle q ≡ 1 mod 4 sei g_{1} selbstreziprok gewählt. Weiter sei g_{1}(1)g_{1}(−1) kein Quadrat in GF(q). Dann ist die Folge (g_{n})_{n≥1}, definiert durch

g_{n+1}(X) = X^{2^{n}}g_{n}(X + 2^{−2n}X^{−1}), n ≥ 1,

spur-kompatibel über GF(q).

An der folgenden Überlegung erkennt man, daß es Startpolynome f = g_{1} für solche Folgen gibt.

• Sei q ≡ 1 mod 4. Es gibt nach Cohen [1] (q−1)/2 selbstreziproke, irreduzible, normierte Polynome vom Grad 2 über GF(q). Zu diesen Polynomen gehört nicht (X^{2} + 1), da −1 ein Quadrat in GF(q) ist. Deshalb sind alle irreduziblen Polynome der Art f(X) = X^{2} + aX + 1 normal über GF(q), d.h. es gilt a ≠ 0. Wegen der Irreduzibilität von f ist 4−a^{2} = f(1)f(−1) kein Quadrat in GF(q).

• Sei q ≡ 3 mod 4. Dann gibt es keine selbstreziproken, irreduziblen, normierten Polynome f vom Grad 2 über GF(q), für die f(1)f(−1) kein Quadrat in GF(q) ist. Denn f(X) = X^{2} + aX + 1 ist genau dann irreduzibel, wenn a^{2} − 4 kein Quadrat in GF(q) ist. Damit ist aber −(a^{2} − 4) = f(1)f(−1) ein Quadrat in GF(q).

Sei nun f(X) = X^{2}+aX +b irreduzibel und f(1)f(−1) kein Quadrat in GF(q). Dann ist f auch schon normal über GF(q), denn a = 0 würde f(1)f(−1) = (1 + b)^{2} implizieren. Die Anzahl der gesuchten Polynome f stimmt überein mit der Anzahl selbstreziproker, irreduzibler, normierter Polynome vom Grad 4 über GF(q), die nach Cohen [1] durch (q^{2} − 1)/4 gegeben ist.

4 Der Fall p|(q − 1), wobei q ≡ 1 mod 4, falls p = 2

Für n ≥ 0 bezeichne ξ_{n} eine primitve p^{n}-te Einheitswurzel über GF(q) mit

ξ_{n+1}^{p} = ξ_{n} und K_{n} := GF(q^{p^{n}}).

Sei r der Exponent von p in (q − 1):

q − 1 = p^{r}u, ggT(p, u) = 1.

Dann gilt ξ_{1}, …, ξ_{r} ∈ GF(q) und nach [3] Theorem 3.75 ist X^{p^{n}} − ξ_{r} für alle n ≥ 0 irreduzibel über GF(q), so daß

ξ_{r+n} ∈ K_{n} und K_{n+1} = K_{n}(ξ_{n+1+r}).

Nun gilt Lemma 1 Für alle n ≥ 1 ist (ξ_{n+r} − 1)^{−1} normal in K_{n} über GF(q) mit der Spur

T_{K_{n}/K_{n−1}}(\frac{1}{ξ_{n+r} − 1}) = p\frac{1}{ξ_{n−1+r} − 1}.

Diese Lemma erlaubt die Konstruktion spur-kompatibler Folgen mit Satz 4 Die Folge (γ_{n})_{n≥0}, definiert durch

γ_{n} = \frac{1}{p^{n}} · \frac{1}{ξ_{n+r} − 1}, n ≥ 0,

ist spur-kompatible über GF(q). Für n ≥ 0 ist f_{n}(X) = X^{p^{n}} −ξ_{r} das Minimalpolynom von ξ_{n+r} über GF(q). Deshalb ist

(p^{np^{n}}f_{n}(\frac{X}{p^{n}} + 1))^{∗}

das Minimalpolynom von γ_{n} über GF(q). Dieses Polynom hat die explizite Form

f_{n}(X) = X^{p^{n}} − \frac{1}{ξ_{r} − 1} ∑_{0≤i<p^{n}} \binom{p^{n}}{i}(p^{n})^{i−p^{n}}X^{i}.

5 Der Fall p|(q + 1), p ungerade

Es bezeichne wiederum ξ_{n} eine primitive p^{n}-te Einheitswurzel über GF(q), K_{n} = GF(q^{p^{n}}) und r den Exponenten von p in (q^{2} − 1). Wegen p|(q^{2} − 1) und [3] Theorem 3.75 ist in diesem Fall ξ_{n+r} ∈ GF(q^{2p^{n}}) vom Grad 2p^{n} über GF(q). Aus p|/(q −1) folgt p^{r}|(q + 1), so daß

T_{GF(q^{2})/GF(q)}(ξ_{r}) = ξ_{r} + ξ_{r}^{q} = ξ_{r} + ξ_{r}^{−1}.

Allgemeiner ist (ξ_{n+r} + ξ_{n+r}^{−1}) ∈ K_{n} vom Grad p^{n} über GF(q). Nun gilt

Lemma 2 Für n ≥ 1 ist (ξ_{n+r} + ξ_{n+r}^{−1})^{−1} normal in K_{n} über GF(q) mit der Spur

T_{K_{n}/K_{n−1}}(\frac{1}{ξ_{n+r} + ξ_{n+r}^{−1}} ) = p(−1)^{(p−1)/2} \frac{1}{ξ_{n−1+r} + ξ_{n−1+r}^{−1}} .

Diese Lemma erlaubt die Konstruktion spur-kompatibler Folgen mit

Satz 5 Sei c = p(−1)^{(p−1)/2}. Dann ist die Folge (γ_{n})_{n≥0}, definiert durch

γ_{n} = \frac{1}{c^{n}} · \frac{1}{ξ_{n+r} + ξ_{n+r}^{−1}} ,

spur-kompatible über GF(q).

Zur Berechnung der Minimalpolynome dieser Elemente benötigen wir normalisierte Tschebyscheff-Polynome 1.Art C_{n}, die rekursiv definiert sind durch

C_{0}(X) = 2, C_{1}(X) = X, C_{n+1}(X) = XC_{n}(X) − C_{n−1}(X), n ≥ 1.

Diese Polynome erfüllen

C_{n}(X + X^{−1}) = X^{n} + X^{−n}

für n ≥ 0 und sind unter Komposition abgeschlossen, d.h. für n, m ∈ IN gilt

C_{n}(C_{m}) = C_{nm} = C_{m}(C_{n}).

Das Minimalpolynom von (ξ_{n+r} + ξ_{n+r}^{−1}) läßt sich damit ausdrücken als f_{n}(X) := C_{p^{n}}(X) − ξ_{r} − ξ_{r}^{−1}. Weiter ergibt sich das Minimalpolynom des Elementes γ_{n} zu

(c^{np^{n}}f_{n}(\frac{X}{c^{n}}))^{∗},

wobei c = p(−1)^{(p−1)/2}. Dieses Polynom hat die explizite Form

f_{n}(X) = X^{p^{n}} − \frac{1}{ξ_{r} + ξ_{r}^{−1}} ∑_{i=0}^{(p^{n}−1)/2} \frac{p^{n}}{p^{n} − i}\binom{p^{n} − i}{i}(−1)^{i}(\frac{X}{c^{n}} )^{2i}.

6 Der Fall: q primitiv modulo p und q^{p−1} ≢ 1 mod p^{2}

In diesem Fall ist q für alle n ≥ 1 primitiv modulo p^{n}. Weiter impliziert diese Bedingung, daß p ungerade ist und jede primitive p^{n+1}-te Einheitswurzel

ξ_{n+1} ∈ GF(q^{(p−1)p^{n}})

für alle n ≥ 0 vom Grad p^{n} über GF(q^{(p−1)}) ist.

Satz 6 Für n ≥ 1 bezeichne α_{n} die Spur von ξ_{n+1} auf GF(q^{p^{n}}). Weiter sei s das multiplikative Inverse von p modulo der Charakteristik von GF(q): sp ≡ 1(mod char GF(q)). Dann ist die Folge (γ_{n})_{n≥0}, definiert durch

γ_{0} = 1, γ_{n} = (α_{n} + s)γ_{n−1}, n ≥ 1,

spur-kompatibel über GF(q).

References

[1] Cohen S.D., On Irreducible Polynomials of certain Types over Finite Fields, Proc. Camb. Phil. Soc. 66, S. 335-344, (1969).

[2] Cohen S.D., The explicit Construction of Irreducible Polynomials over Finite Fields, Designs, Codes and Cryptography 2, S.169-174, (1992).

[3] Lidl R., Niederreiter H., Finite Fields, Encyclopedia of Mathematics and its Applications, vol.20, Addison-Wesley, Reading, Mass. (1983).

[4] Scheerhorn A., Trace- and Norm-Compatible Extensions of Finite Fields, erscheint in Appl. Alg. in Eng., Comm. and Comp.

[5] Scheerhorn A., Darstellungen des algebraischen Abschlusses endlicher Körper und spur-kompatible Polynomfolgen, Dissertation, Erlangen, (1993).