О построении примитивного нормального базиса конечного поля

Пусть $n$ натуральное, $q$ – степень простого числа, $\theta$ – примитивный элемент поля $GF(q^n)$. В работе доказано, что существуют такие абсолютные постоянные $c_1,c_2>0$, что при $N\geqslant\max(\exp\exp(c_1\ln^2n),c_2n\ln q)$ среди элементов $\theta^k$, $k=1,\dots,N$, найдется хотя бы один порождающий примитивный нормальный базис поля $GF(q^n)$ над полем $GF(q)$. При фиксированном $n$ отсюда следует полиномиальный в зависимости от $\ln q$ алгоритм перехода от произвольного примитивного элемента $\theta\in GF(q^n)$ к элементу, порождающему примитивный нормальный базис поля $GF(q^n)$ над полем $GF(q)$.
Библиография: 17 названий.