Variations of the Primitive Normal Basis Theorem

Abstract

The celebrated Primitive Normal Basis Theorem states that for any $n\ge 2$ and any finite field ${\mathbb {F}}_q$, there exists an element $\alpha \in {\mathbb {F}}_{q^n}$ that is simultaneously primitive and normal over ${\mathbb {F}}_q$. In this paper, we prove some variations of this result, completing the proof of a conjecture proposed by Anderson and Mullen (2014).

Appendix A: Pseudocodes for search for 2-primitive elements with special properties

Following the approach of [11], Algorithm 1 presents a search routine for 2-primitive, k-normal elements of ${\mathbb {F}}_{q^n}$ over ${\mathbb {F}}_q$. This search is based on the original characterization of k-normal elements from [7].

Theorem A.1

Let $\alpha \in {\mathbb {F}}_{q^n}$ and let $g_\alpha (x) = \sum _{i=0}^{n-1} \alpha ^{q^i}x^{n-1-i} \in {\mathbb {F}}_{q^n}[x]$. Then $\gcd (x^n-1, g_\alpha (x))$ has degree k if and only if $\alpha$ is a k-normal element of ${\mathbb {F}}_{q^n}$ over ${\mathbb {F}}_q$.

Algorithm 1 proceeds as follows. Let ${\mathbb {F}}_{q^n}\cong {\mathbb {F}}_q[x]/(f)$ with f a primitive polynomial, and let g be a root of f. Hence, g is a generator of ${\mathbb {F}}_{q^n}^*$ and $g^i$ is 2-primitive if and only if $\gcd (i, q^n-1) = 2$. For each 2-primitive element, check its k-normality using Theorem A.1. If $k=1$, the resulting element is 2-primitive, 1-normal and is returned. The algorithm returns “Fail” if no 2-primitive 1-normal is found after $q^n-2$ iterations; that is, if all of ${\mathbb {F}}_{q^n}^*$ is traversed.