On primitive and free roots in a finite field (Q1201337)

For \(q\) a prime power and \(m>1,\) let \(F_{q^ m}\) denote the finite field of order \(q^ m\) so that \(F_{q^ m}\) can be viewed as a vector space of dimension \(m\) over the field \(F_ q.\) A basis of \(F_{q^ m}\) over \(F_ q\) of the form \(\alpha, \alpha ^ q, \dots, \alpha ^{q^{m- 1}}\) is called a normal basis and the author refers to \(\alpha \) as a free root. Such a basis is said to be a primitive normal basis if the element \(\alpha\) is also a primitive element (of multiplicative order \(q^ m-1\)) in \(F_{q^ m}.\) From \textit{H. W. Lenstra jun.} and \textit{R. J. Schoof} [Math. Comput. 48, 217-231 (1987; Zbl 0615.12023)], such a primitive normal basis exists for every \(q\) and every \(m.\) In this paper the author studies \(F_{q^ m}\) from an algebraic point of view and in particular he views the additive group of \(F_{q^ m}\) as a cyclic module over the principal ideal domain \(F_ q[x].\) He then investigates a new class of polynomials, which he calls \(\pi\)- polynomials, over \(F_ q.\) Roots of a \(\pi\)-polynomial are the elements of \(F_ q\) of a given additive order. In addition the author studies a recursive algorithm, analogous to that for computing cyclotomic polynomials over the rationals, to compute these polynomials. As a consequence, he is at least theoretically able, to compute all primitive normal basis generators, and more generally, all elements of any given additive and multiplicative orders. While the details are too complicated to be discussed here, this paper introduces a new theoretical technique that unifies into one theory the existence of elements of prescribed additive and multiplicative orders. Because of the increased importance of computational and theoretical algorithms, this paper is an important one.