On the construction of a primitive normal basis in a finite field

Let $n$ be a natural number, $q$ a prime power, and $\theta$ a primitive element of the field $GF(q^n)$. This paper shows that there exist absolute constants $c_1,c_2>0$ such that for $N\geqslant\max(\exp\exp(c_1\ln^2n),c_2n\ln q)$ the set of elements $\theta^k$, $k=1,\dots,N$, includes at least one which generates a primitive normal basis of $GF(q^n)$ over $GF(q)$. For fixed $n$, this gives a polynomial time algorithm in $\ln q$ which, given an arbitrary primitive element $\theta\in GF(q^n)$, finds an element which generates a primitive normal basis for $GF(q^n)$ over $GF(q)$.
Bibliography: 17 titles.