Quadratic-Time Algorithms for Normal Elements
Mark W. Giesbrecht, Armin Jamshidpey, Éric Schost · 2019
For any finite Galois field extension K/F, with Galois group G = Gal(K/F), there exists an element K whose orbit G · forms an F-basis of K. Such an is called a normal element and G · is a normal basis. We introduce a probabilistic algorithm for finding a normal element when G is either a finite abelian or a metacyclic group. The algorithm is based on the fact that deciding whether a random element K is normal can be reduced to deciding whether () K[G] is invertible (where ranges over all of G). Our algorithm requires a quadratic number of operations in the size of G for metacyclic G, and a slightly subquadratic number of operations for abelian G.