Normal bases over GF(q)

For q a power of a prime p, it is known that if m is a power of p or m itse lf is a prime different from p having (I as one of its primitive roots, the n the roots of any irreducible polynomial of degree m and of non-zero trace are linearly independent over GF(q). As a consequence the roots of such an mth degree polynomial form a basis of GF(q(m)) over GF(q). Such a basis is called a normal basis over GF(q) and the polynomial is called normal over CF(q). Normal bases over finite fields have proved very useful for fast ari thmetic computations with potential applications to coding theory and to cr yptography. In this paper, we prove that for mth degree irreducible polynom ials the above two conditions are indeed necessary and sufficient condition s for the equivalence between the properties of having a non-zero trace and being normal over GF(q). (C) 2001 Academic Press.