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 is an element of K whose orbit G center dot alpha forms an F-basis of K. Such an alpha is called a normal element, and G center dot alpha is a normal basis. We introduce a probabilistic algorithm for testing whether a given alpha is an element of 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 Sigma(g is an element of G)g(alpha)g is an element of 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.