Armin
Jamshidpey,
Postdoctoral
fellow
David
R.
Cheriton
School
of
Computer
Science
It is well known that for any finite Galois extension field K/F, with Galois group G = Gal(K/F), there exists an element α in K whose orbit G·α forms an F-basis of K. Such an element α is called normal and G·α is called a normal basis.
In this talk, 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 α in K is normal can be reduced to deciding whether Σσ in G σ(α)σ in K[G] is invertible. In an algebraic model, the cost of our algorithm is quadratic in the size of G for metacyclic G and slightly subquadratic for abelian G.
This is a joint work with Mark Giesbrecht and Eric Schost (both University Waterloo).