Small Primitive Normal Elements in Finite Fields

Abstract

Let $q=p^k$ be a prime power, let ${\mathbb{F}}_q$ be a finite field and let $n\ge 2$ be an integer. This note investigates the existence small primitive normal elements in finite field extensions ${\mathbb{F}}_{q^n}$. It is shown that a small nonstructured subset $\mathcal{A}\subset {\mathbb{F}}_{q^n}$ of cardinality $\#\mathcal{A}\gg (\log q^n)(\log \log q^n{)}^{1+\epsilon })$, where $\epsilon >0$ is a small number, contains a primitive normal element.

Thirty-Nine Pages. Keywords: Finite field; Primitive element; Normal element; Complexity of primitive normal element