\documentclass[12pt]{article} \usepackage{amsfonts} % %\renewcommand{\baselinestretch}{1.2} \setlength{\textwidth}{15cm} \setlength{\textheight}{22.5cm} \setlength{\oddsidemargin}{0.5cm} \setlength{\evensidemargin}{0.5cm} \setlength{\topmargin}{0cm} % \begin{document} \title{Spur-kompatible Polynomfolgen \"uber endlichen K\"orpern} \author{Alfred Scheerhorn\\ Deutsche Bundespost Telekom\\ Forschungs- und Technologiezentrum, FZ 123b\\ 64276 Darmstadt\\ Germany} \date{ } % Abk\"urzungen \def\N{\hbox{\rm I\kern-0.2em N}} \def\Z{\hbox{\rm Z\kern-0.3em Z}} \renewcommand{\gcd}{\hbox{\rm ggT}} \newcommand{\lcm}{\hbox{\rm kgV}} \newcommand{\Char}{\hbox{\rm char}} \newcommand{\AI}{(\alpha_n)_{n\in I}} \newcommand{\Sub}[2]{\scriptsize{\begin{array}{c} #1\\ #2 \end{array}}} \newcommand{\lit}{\sc} \newcommand{\GF}{\hbox{\rm G\kern-0.1emF}} \newcommand{\T}{\hbox{\rm T}} \newcommand{\rf}[1]{(\ref{#1})} \newtheorem{theorem}{Satz} \newtheorem{lemma}{Lemma} \newtheorem{definition}{Definition} \newtheorem{corollary}[lemma]{Korollar} \hyphenation{end-licher Ele-men-tes Ele-men-te-fol-gen un-gera-der selbst-reziprok} \maketitle \section{Einf\"uhrung} Spur-kompatible Polynomfolgen \"uber endlichen K\"orpern finden Anwendung in der Computeralgebra bei der Implementierung des algebraischen Abschlusses endlicher K\"orper (siehe \cite{dis}). Es wird beschrieben, wie in einigen speziellen F\"allen sehr schnell spur-kompatible Folgen erzeugt werden k\"onnen. Die Beweise s\"amtlicher hier auf\-ge\-f\"uhr\-ter S\"atze findet man in \cite{dis}. Die Definition des Begriffes Spur-Kompatibilit\"at erfordert einige Vorbereitungen. Es bezeichne $q>1$ eine Primzahlpotenz und $K=\GF(q)$ den endlichen K\"orper der Ordnung $q$. Sei $\alpha$ ein Element des Erweiterungsk\"orpers $E=\GF(q^m)$, $m\in\N$, und $E$ die kleinste Erweiterung von $\GF(q)$, die $\alpha$ enth\"alt. Die Elemente \[ \alpha,\alpha^q,\ldots,\alpha^{q^{m-1}} \] hei{\ss}en die {\em Konjugierten} von $\alpha$ \"uber $\GF(q)$. Die {\em Spur} $\T_{E/K}(\alpha)$ von $\alpha$ \"uber $\GF(q)$ ist definiert als die Summe der Konjugierten von $\alpha$ \"uber $\GF(q)$: \[ \T_{E/K}(\alpha) = \sum_{i=0}^{m-1}\alpha^{q^i}. \] Eine Basis $\{\alpha,\alpha^q,\dots,\alpha^{q^{m-1}}\}$ von $\GF(q^m)$ \"uber $\GF(q)$, die aus den Konjugierten eines Elements $\alpha\in\GF(q^m)$ besteht, wird {\em Normalbasis} genannt. Erzeugt $\alpha$ eine Normalbasis von $\GF(q^m)$ \"uber $\GF(q)$, dann hei{\ss}t $\alpha$ {\em normal} in $\GF(q^m)$ \"uber $\GF(q)$. Mit $\alpha$ wird auch das Minimalpolynom \[ f(X)=\prod_{i=0}^{m-1}(X-\alpha^{q^i})\in\GF(q)[X] \] von $\alpha$ \"uber $\GF(q)$ normal genannt. Zur die Definition der Kompatibilit\"at sei $I$ eine unter Teilbarkeit abgeschlossenen Menge nat\"urlicher Zahlen, d.h. mit $n\in I$ geh\"oren auch alle Teiler von $n$ zu $I$. \begin{definition} Eine Folge $\AI$ von Elementen $\alpha_n\in\GF(q^n)$ hei{\ss}t {\em spur-kom\-pa\-ti\-bel} \"uber $\GF(q)$, wenn f\"ur alle $n\in I$ gilt: \begin{enumerate} \item $\alpha_n$ ist normal in $\GF(q^n)$ \"uber $\GF(q)$ und \item F\"ur alle Teiler $d$ von $n$ gilt f\"ur die Spur $\T_{n:d}(\alpha_n)$ von $\GF(q^n)$ auf $\GF(q^d)$: \[ \T_{n:d}(\alpha_n)=\alpha_d. \] \end{enumerate} Eine Folge $(f_n)_{n\in I}$ von Polynomen $f_n\in\GF(q)[X],\ \deg(f_n)=n$, hei{\ss}t {\em spur-kom\-pa\-ti\-bel} \"uber $\GF(q)$, wenn f\"ur alle $n\in I$ gilt: \begin{enumerate} \item $f_n$ ist normal \"uber $\GF(q)$ und \item F\"ur jede Wurzel $\alpha\in\GF(q^n)$ von $f_n$ ist die Spur $\T_{n:d}(\alpha)$ von $\alpha$ \"uber $\GF(q^d)$ eine Wurzel von $f_d$, f\"ur alle Teiler $d$ von $n$. \end{enumerate} \end{definition} Die Existenz spur-kompatibler Elementefolgen $(\alpha_n)_{n\in{\N}}$ wird in \cite{S91} bewiesen. Sei nun $(\alpha_n)_{n\in{\N}}$ spur-kompatible \"uber $\GF(q)$. Wenn man f\"ur alle $n\in\N$ die Elemente von $\GF(q^n)$ bez\"uglich der von $\alpha_n$ erzeugten Normalbasis darstellt, erh\"alt man leicht berechenbare Einbettungen zwischen den Normalbasis-Darstellungen verschiedener Erweitrungen: $\gamma\in\GF(q^d)$ habe die Darstellung \[ \gamma=\sum_{i=0}^{d-1}c_i\alpha_d^{q^i},\ \ c_i\in\GF(q), \] bez\"uglich der von $\alpha_d$ erzeugten Normalbasis. Wegen \[ \T_{m:d}(\alpha_m)=\sum_{j=0}^{(m/d)-1}\alpha^{q^{dj}}=\alpha_d, \] folgt nun \[ \gamma=\sum_{i=0}^{d-1}c_i\T_{m:d}(\alpha_m)^{q^i}= \sum_{i=0}^{d-1}c_i\sum_{j=0}^{(m/d)-1}\alpha_m^{q^{jd+i}}= \sum_{i=0}^{m-1}c_{(i\ \bmod\ d)}\alpha_m^{q^i}. \] Die Einbettung der Normalbasis-Darstellung von $\GF(q^d)$ in die von $\GF(q^m)$ \mbox{entspricht} somit einer $(m/d)$-fachen Konkatenation des Koordinatenvektors $(c_0,c_1,\dots,c_{d-1})$ von $\gamma$. Mit dem folgendem Satz l\"a{\ss}t sich die Bestimmung eines spur-kompatiblen Elementes in $\GF(q^n)$, $n=\prod p^{e_p}$, reduzieren auf die Bestimmung spur-kompatibler Elemente in den Erweiterungen der Primzahlpotenzgrade $p^{e_p}$ \"uber $\GF(q)$. \begin{theorem} F\"ur Primzahlen $p$ seien bereits spur-kompatible Elementefolgen $(\alpha_{p^e})_{e\geq 0}$ \"uber $\GF(q)$ gegeben. Dann ist die Folge $(\alpha_n)_{n\geq 1}$ spur-kompatibel \"uber $\GF(q)$, wenn f\"ur alle zusammengesetzten $n\in\N$ mit der Primfaktorisierung $n=\prod_{i=1}^rp_i^{e_i}$ definiert wird: \[ \alpha_n=\alpha_1^{1-r}\prod_{i=1}^r\alpha_{p_i^{e_i}}. \] \end{theorem} In \cite{dis} Kapitel 2.6 wird ein Algorithmus zur Berechnung spur-kompatibler Elementefolgen $(\alpha_{p^e})_{e\geq 0}$, $p$ prim, \"uber $\GF(q)$ beschrieben, der eine Komplexit\"at von $O(m^3\log m\log q)$ $\GF(q)$-Operationen hat. Wir beschreiben im folgenden, wie f\"ur spezielle Paare $(q,p)$ auf einfachere Weise spur-kompatible Folgen berechnet werden k\"onnen. \bigskip \section{Der Fall $\Char(\GF(q))=p$} Diese Situation ist aus der Artin-Schreier-Theorie wohl\-be\-kannt. Die Untersuchungen orientieren sich an Trinomen der Form \[ X^p-X-\alpha. \] Hier gilt ein sehr einfaches Normalit\"atskriterium: Ein Element $\alpha_n$ vom Grad $p^n$ \"uber $\GF(q)$ ist genau dann normal \"uber $\GF(q)$, wenn die Spur von $\alpha_n$ \"uber $\GF(q)$ ungleich $0$ ist. Diese Spur ist am Minimalpolynom von $\alpha_n$ \"uber $\GF(q)$ ablesbar. Zur Beschreibung des folgenden Ergebnisses ben\"otigen wir {\em reziproke} Polynome. F\"ur $f(X)=X^m+a_{m-1}X^{m-1}+\ldots+a_1X+a_0$ aus $\GF(q)[X]$ hei{\ss}t \[ f^*(X):=\frac{1}{a_0}(a_0X^m+a_1X^{m-1}+\ldots+a_{m-1}X+1)= \frac{1}{a_0}X^mf(\frac{1}{X}) \] das zu $f$ reziproke Polynom. \begin{theorem}\label{spur-kompp3} Sei $K=\GF(q)$ ein endlicher K\"orper der Charakteristik $p$ und $\beta_0\in K$ mit absoluter Spur $\T_K(\beta_0)\neq 0$ und $\T_K(\beta_0^{-1})\neq 0$. Weiter sei $f_1(X)=X^p-X-\beta_0^{-1}\in K[X]$. F\"ur $n>0$ definieren wir bei ungeradem $p$ rekursiv jedes Polynom $g_n\in K[X]$ durch Wahl einer der drei M\"oglichkeiten \begin{enumerate} \item $ g_n(X)=-f_n^*(-1-X)$ oder \item $ g_n(X)=-f_n^*(1-X)$ oder \item $ X^{p^n}g_n(X-X^{-1}) = -f^*(-X)f(X)$, \end{enumerate} f\"ur $p=2$ definieren wir $g_n(X)=f_n^*(X+1)$. Unabh\"angig von der Charakteristik sei $f_{n+1}\in K[X]$ durch $f_{n+1}(X)=g_n^*(X^p-X)$ definiert. Dann ist die Folge von Polynomen $(g_n)_{n\geq 1}$ spur-kompatibel \"uber $K$. \end{theorem} Auf die folgende Weise l\"a{\ss}t sich ein Element $\beta_0\in K=\GF(p^r)$ berechnen, dessen absolute Spur $\T_K(\beta_0)\neq 0 \neq \T_K(\beta_0^{-1})$ ist: Gilt $\gcd(p,r)=1$, dann w\"ahlen wir $\beta_0=1\in K$ und haben $\T_K(\beta_0) = \T_K(\beta^{-1}_0) = r \neq 0$. Gilt $\gcd(p,r)>1$ dann sei $r=p^su$ mit $\gcd(u,p)=1$. Jetzt liefert uns Satz~\ref{spur-kompp3} angewandt auf $K=\GF(p^u)$ und $\beta_0=1$ ein Polynom $g_s\in \GF(p^u)[X]$, dessen Wurzeln in $\GF(p^r)$ die gew\"unschten Bedingungen erf\"ullen. \bigskip \section{Der Fall $p=2$, $q$ ungerade} F\"ur geeignete Polynome $f_1\in\GF(q)[X]$ vom Grad 2 sind alle Polynome der Folge $(f_n)_{n\geq 1}$, definiert durch \[ f_{n+1}(X)=(2X)^{2^n}f_{n}(\frac{X+X^{-1}}{2}), \ \ n\geq 1, \] irreduzibel \"uber $\GF(q)$ (vergleiche {\lit Cohen} \cite{Co91}). In \cite{dis} Kapitel 3.3 wird gezeigt, da{\ss} die Polynome dieser Folge (bei geeignetem $f_1$) f\"ur $q\equiv \pm 3\bmod 8$ und $q\equiv 9\bmod 16$ normal \"uber $\GF(q)$ sind. Durch eine leichte Ab\"anderung der obigen Rekursionsvorschrift zu \[ g_{n+1}(X)=X^{2^n}g_n(X+2^{-2n}X^{-1}), \ \ n\geq 1, \] erh\"alt man (bei geeignetem $g_1$) in den angegebenen F\"allen eine spur-kompatible Polynomfolge. Wir vermuten, da{\ss} das dieses Verfahren unabh\"angig von $q$ in ungerader Charakteristik eine spur-kompatible Polynomfolge liefert. \begin{theorem}\label{twotrcomp} Sei $q\equiv\pm 3\bmod 8$ oder $q\equiv 9 \bmod 16$ und sei $g_1\in \GF(q)[X]$ normiert, irreduzibel vom Grad 2 und normal \"uber $\GF(q)$. Im Falle $q\equiv 1\bmod 4$ sei $g_1$ selbstreziprok gew\"ahlt. Weiter sei $g_1(1)g_1(-1)$ kein Quadrat in $\GF(q)$. Dann ist die Folge $(g_n)_{n\geq 1}$, definiert durch \[ g_{n+1}(X) = X^{2^n} g_n(X+2^{-2n}X^{-1}),\ \ n\geq 1, \] spur-kompatibel \"uber $\GF(q)$. \end{theorem} An der folgenden \"Uberlegung erkennt man, da{\ss} es Startpolynome $f=g_1$ f\"ur solche Folgen gibt. \begin{itemize} \item Sei $q\equiv 1 \bmod 4$. Es gibt nach {\lit Cohen} \cite{Co69} $(q-1)/2$ selbstreziproke, irreduzible, normierte Polynome vom Grad $2$ \"uber $\GF(q)$. Zu diesen Polynomen geh\"ort 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 \"uber $\GF(q)$, d.h.~es gilt $a\neq 0$. Wegen der Irreduzibilit\"at von $f$ ist $4-a^2=f(1)f(-1)$ kein Quadrat in $\GF(q)$. \item Sei $q\equiv 3 \bmod 4$. Dann gibt es keine selbstreziproken, irreduziblen, normierten Polynome $f$ vom Grad $2$ \"uber $\GF(q)$, f\"ur 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 \"uber $\GF(q)$, denn $a=0$ w\"urde $f(1)f(-1)=(1+b)^2$ implizieren. Die Anzahl der gesuchten Polynome $f$ stimmt \"uberein mit der Anzahl selbstreziproker, irreduzibler, normierter Polynome vom Grad $4$ \"uber $\GF(q)$, die nach {\lit Cohen} \cite{Co69} durch $(q^2-1)/4$ gegeben ist. \end{itemize} \bigskip \section{Der Fall $p|(q-1)$, wobei $q\equiv 1\bmod 4$, falls $p=2$} F\"ur $n\geq 0$ bezeichne $\xi_n$ eine primitve $p^n$-te Einheitswurzel \"uber $\GF(q)$ mit \[ \xi_{n+1}^p=\xi_n\ \ \hbox{und} \ \ K_n:=\GF(q^{p^n}). \] Sei $r$ der Exponent von $p$ in $(q-1)$: \[ q-1=p^ru,\ \ \gcd(p,u)=1. \] Dann gilt $\xi_1,\ldots,\xi_r\in\GF(q)$ und nach \cite{LN83} Theorem~3.75 ist $X^{p^n}-\xi_r$ f\"ur alle $n\geq 0$ irreduzibel \"uber $\GF(q)$, so da{\ss} \[ \xi_{r+n}\in K_n \ \ \hbox{und} \ \ K_{n+1}=K_n(\xi_{n+1+r}). \] Nun gilt \begin{lemma}\label{pq4spur} F\"ur alle $n\geq 1$ ist $(\xi_{n+r}-1)^{-1}$ normal in $K_n$ \"uber $\GF(q)$ mit der Spur \[ \T_{K_n/K_{n-1}}\big(\frac{1}{\xi_{n+r}-1}\big)= p\frac{1}{\xi_{n-1+r}-1}. \] \end{lemma} Diese Lemma erlaubt die Konstruktion spur-kompatibler Folgen mit \begin{theorem}\label{pq5s1} Die Folge $(\gamma_n)_{n\geq 0}$, definiert durch \[ \gamma_n=\frac{1}{p^n}\cdot\frac{1}{\xi_{n+r}-1}, \ \ n\geq 0, \] ist spur-kompatible \"uber $\GF(q)$. \end{theorem} F\"ur $n\geq 0$ ist $f_n(X)=X^{p^n}-\xi_r$ das Minimalpolynom von $\xi_{n+r}$ \"uber $\GF(q)$. Deshalb ist \[\Big(p^{np^n}f_n(\frac{X}{p^n}+1)\Big)^*\] das Minimalpolynom von $\gamma_n$ \"uber $\GF(q)$. Dieses Polynom hat die explizite Form \[ f_n(X)=X^{p^n}-\frac{1}{\xi_r-1} \sum_{0\leq i