Subquadratic-Time Algorithms for Normal Bases

For any finite Galois field extension K/F, with Galois group G = Gal (K/F), there exists an element $$\alpha \in $$ K whose orbit $$G\cdot\alpha$$ forms an F-basis of K. Such an $$\alpha$$ is called a normal element, and $$G\cdot\alpha$$ is a normal basis. We introduce a probabilistic algorithm for testing whether a given $$\alpha \in$$ K is normal, when G is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether $$\alpha$$ is normal can be reduced to deciding whether $$\sum_{g \in G} g(\alpha)g \in$$ K[G] is invertible; it requires a slightly subquadratic number of operations. Once we know that $$\alpha$$ is normal, we show how to perform conversions between the power basis of K/F and the normal basis with the same asymptotic cost.