The trace of an optimal normal element and low complexity normal bases

Let ${\mathbb{F}}_{q}$ be a finite field and consider an extension ${\mathbb{F}}_{q^{n}}$ where an optimal normal element exists. Using the trace of an optimal normal element in ${\mathbb{F}}_{q^{n}}$ , we provide low complexity normal elements in ${\mathbb{F}}_{q^{m}}$ , with m = n/k. We give theorems for Type I and Type II optimal normal elements. When Type I normal elements are used with m = n/2, m odd and q even, our construction gives Type II optimal normal elements in ${\mathbb{F}}_{q^{m}}$ ; otherwise we give low complexity normal elements. Since optimal normal elements do not exist for every extension degree m of every finite field ${\mathbb{F}}_{q}$ , our results could have a practical impact in expanding the available extension degrees for fast arithmetic using normal bases.