On the Density of Normal Bases in Finite Fields

Gudmund Skovbjerg Frandsen

December 1997

Abstract:

Let tex2html_wrap_inline56 denote the finite field with tex2html_wrap_inline58 elements, for q being a prime power. tex2html_wrap_inline56 may be regarded as an n-dimensional vector space over tex2html_wrap_inline66. tex2html_wrap_inline68 generates a normal basis for this vector space (tex2html_wrap_inline70), if tex2html_wrap_inline72 are linearly independent over tex2html_wrap_inline66. Let N(q,n) denote the number of elements in tex2html_wrap_inline56 that generate a normal basis for tex2html_wrap_inline70, and let tex2html_wrap_inline82 denote the frequency of such elements.

We show that there exists a constant c>0 such that
displaymath86
and this is optimal up to a constant factor in that we show
displaymath88
We also obtain an explicit lower bound:
displaymath90

Available as PostScript, PDF, DVI.

 

Last modified: 2003-06-08 by webmaster.