ON THE CONSTRUCTION OF A PRIMITIVE NORMAL BASIS IN A FINITE FIELD
С. А. Степанов, Igor E. Shparlinski · Mathematics of the USSR-Sbornik · 1990
Let n be a natural number, q a prime power, and θ a primitive element of the field GF(qn). This paper shows that there exist absolute constants c1, c2 > 0 such that for N ≥ max(exp exp(c1ln2n), c2n ln q) the set of elements θ1, ..., θN includes at least one which generates a primitive normal basis of GF(qn) over GF(q). For fixed n, this gives a polynomial time algorithm in ln q which, given an arbitrary primitive element θGF(qn), finds an element which generates a primitive normal basis for GF(qn) over GF(q). Bibliography: 17 titles.