1 Introduction and preliminaries
Throughout this note, we denote by
$\mathbb {F}_{q}$
the finite field of q elements and by
$\mathbb {F}_{q}[x]$
the ring of polynomials in the variable x with coefficients in
$\mathbb {F}_{q}$
. A generator of the cyclic group
$\mathbb {F}_{q}^{\ast }$
is called a primitive element of
$\mathbb {F}_{q}$
. A polynomial
$f \in \mathbb {F}_{q}[x]$
of degree
$m \geq 1$
is called a primitive polynomial over
$\mathbb {F}_{q}$
if it is the minimal polynomial over
$\mathbb {F}_{q}$
of a primitive element of
$\mathbb {F}_{q^{m}}$
. A primitive polynomial of degree m over
$\mathbb {F}_{q}$
is a monic irreducible polynomial in
$\mathbb {F}_{q}[x]$
that has a root
$\alpha \in \mathbb {F}_{q^{m}}$
generating the multiplicative group
$\mathbb {F}_{q^{m}}^{\ast }$
.
Let
$f(x) = \sum _{i=0}^{n} a_{i} x^{i} \in \mathbb {F}_{q}[x]$
be a monic polynomial with
$a_{0} \neq 0$
. The reciprocal polynomial
$f^{\ast }(x)$
of
$f(x)$
is defined by
$$ \begin{align*} f^{\ast}(x) = a_{0}^{-1} x^{n} f\bigg( \frac{1}{x} \bigg) = \sum_{i=0}^{n} a_{0}^{-1} a_{i} x^{n-i}. \end{align*} $$
Let
$f \in \mathbb {F}_q[x]$
be a nonzero polynomial.
-
• If
$f(0) \neq 0$
, then the least positive integer e such that
$f(x)$
divides
$x^{e} - 1$
is called the order of f, denoted
$\operatorname {ord}(f)$
. -
• If
$f(0) = 0$
, then
$f(x) = x^{h} g(x)$
, where
$h \in \mathbb {N}$
and
$g \in \mathbb {F}_q[x]$
with
$g(0) \neq 0$
are uniquely determined. In this case, the order of f is defined as
$\operatorname {ord}(f) = \operatorname {ord}(g)$
.
(For a proof of the existence of such an e, see [Reference Lidl and Niederreiter5, Lemma 3.1, page 84].)
Trinomials in
$\mathbb {F}_{q}[x]$
are polynomials of the form
$x^{n} + a x^{k} + b$
, where
$n> k > 0$
and
$ab \neq 0$
. Primitive trinomials play a significant role in the theory of finite fields, particularly in applications to cryptography and coding theory. The literature contains extensive research on primitive polynomials over finite fields. The Handbook [Reference Mullen and Panario6] gives a comprehensive overview of the state of the art in the theory and applications of finite fields; in particular, Section 4.3 presents several results on primitive polynomials. There are many results on the factorisation of trinomials and the conditions under which primitive trinomials exist (for detailed results and background, see [Reference Alizadeh1, Reference Cherchem, Bouguebrine and Boughambouz3, Reference Lidl and Niederreiter5]). Most existing research has concentrated on trinomials over the binary field
$\mathbb {F}_{2}$
, due to their use in coding and information theory. Many fundamental questions about the structure and properties of trinomials over general finite fields remain open, and this area continues to be an active field of research with numerous unsolved problems and conjectures (see [Reference Brent and Zimmermann2]).
2 Preliminary lemmas
Some of the following results are well known. We have included them here for completeness.
Lemma 2.1 [Reference Lidl and Niederreiter5, Theorem 3.13].
Let
$f(x) \in \mathbb {F}_{q}[x]$
be a nonzero polynomial. Then,
$$ \begin{align*} \operatorname{ord}(f(x)) = \operatorname{ord}(f^{\ast}(x)). \end{align*} $$
It is clear from this lemma that
$f(x)$
is primitive over
$\mathbb {F}_{q}$
if and only if
$f^{\ast }(x)$
is primitive over
$\mathbb {F}_{q}$
.
Lemma 2.2. Let
$f(x) \in \mathbb {F}_{q}[x]$
be a primitive polynomial of degree n and let
$c \in \mathbb {F}_{q}^{\ast }$
. Then, the polynomial
$c^{-n} f(c x)$
is primitive over
$\mathbb {F}_{q}$
and has degree n.
Proof. Let
$\alpha \in \mathbb {F}_{q^n}$
be a root of
$f(x)$
. Multiplication by a nonzero scalar
$c^{-1} \in \mathbb {F}_q^{\ast }$
defines a group automorphism of
$\mathbb {F}_{q^n}^{\ast }$
and therefore preserves orders. Since
$\alpha $
is primitive, so is
$c^{-1} \alpha $
. Thus,
$c^{-n} f(c x)$
is a primitive polynomial over
$\mathbb {F}_q$
of degree n.
The main results of this paper are based on the following lemma.
Lemma 2.3. Let
$f(x) = \sum _{i=0}^{n} a_{i} x^{i} \in \mathbb {F}_{q^{m}}[x]$
. If
$f(x)$
is primitive over
$\mathbb {F}_{q^{m}}$
, then
$$ \begin{align*} \mathbb{F}_{q}(a_{0}, a_{1}, \ldots, a_{n}) = \mathbb{F}_{q^{m}}. \end{align*} $$
Proof. Suppose that
$f(x)$
is primitive over
$\mathbb {F}_{q^{m}}$
of degree n, and
$$ \begin{align*} \mathbb{F}_{q}(a_{0}, a_{1}, \ldots, a_{n}) = \mathbb{F}_{q^{s}} \subsetneqq \mathbb{F}_{q^{m}} \end{align*} $$
for some proper divisor s of m. Then,
$f(x)$
has coefficients in
$\mathbb {F}_{q^{s}}$
, and since it is primitive over
$\mathbb {F}_{q^{m}}$
, it must be irreducible over
$\mathbb {F}_{q^{m}}$
, and hence also irreducible over
$\mathbb {F}_{q^{s}}$
. Now, let
$\alpha \in \mathbb {F}_{q^{mn}}$
be a root of
$f(x)$
. The primitivity of
$f(x)$
over
$\mathbb {F}_{q^{m}}$
implies that
$\operatorname {ord}(\alpha ) = q^{mn} - 1$
, and the irreducibility of
$f(x)$
over
$\mathbb {F}_{q^{s}}$
implies that
$\operatorname {ord}(\alpha )$
divides
$q^{sn} - 1$
, which is impossible since s is a proper divisor of m.
3 Main results
The following result, originally due to Li et al. [Reference Li, Wang and Zhao4], provides a criterion for the nonprimitivity of a trinomial over
$\mathbb {F}_{q^{m}}$
. We present a significantly shorter and self-contained proof that avoids reliance on the theory of linear recurrences.
Theorem 3.1 [Reference Li, Wang and Zhao4, Theorem 1.1].
Let
$m, n \in \mathbb {N}$
with
$m, n \geq 2$
, and let
$a, b \in \mathbb {F}_{q^{m}}^{\ast }$
. Suppose there exists a positive integer u such that
$u < m$
and
$$ \begin{align*} a^{n} b^{1-n} \in \mathbb{F}_{q^{u}}^{\ast}. \end{align*} $$
Then, the trinomial
$x^{n} + a x + b$
is not primitive over
$\mathbb {F}_{q^{m}}$
.
Proof. Set
$f(x) = x^{n} + a x + b$
. Then, the reciprocal polynomial of f is given by
$$ \begin{align*} f^{\ast}(x) = x^{n} + a b^{-1} x^{n-1} + b^{-1}. \end{align*} $$
Suppose that
$f(x)$
is primitive over
$\mathbb {F}_{q^{m}}$
. By Lemma 2.1, it follows that
$f^{\ast }(x)$
is also primitive over
$\mathbb {F}_{q^{m}}$
. Now, by Lemma 2.2, the polynomial
$$ \begin{align*} g(x) = a^{-n} b^{n} f^{\ast}(a b^{-1} x) = x^{n} + x^{n-1} + a^{-n} b^{n-1} \end{align*} $$
is primitive over
$\mathbb {F}_{q^{m}}$
. Therefore, by Lemma 2.3, it follows that
$a^{n} b^{1-n} \notin \mathbb {F}_{q^{u}}^{\ast }$
for any positive integer
$u < m$
. This contradicts the hypothesis, completing the proof.
The following theorem is a generalisation of Theorem 3.1.
Theorem 3.2. Let
$m, n, k \in \mathbb {N}$
with
$m, n \geq 2$
and
$1 \leq k < n$
. Let
$a, b \in \mathbb {F}_{q^{m}}^{\ast }$
. Suppose there exists a positive integer
$u < m$
such that
$$ \begin{align*} a^{n} b^{k-n} \in \mathbb{F}_{q^{u}}^{\ast}. \end{align*} $$
Then, the trinomial
$x^{n} + a^{k} x^{k} + b^{k}$
is not primitive over
$\mathbb {F}_{q^{m}}$
.
Proof. Let
$f(x) = x^{n} + a^{k} x^{k} + b^{k}$
. Then, the reciprocal polynomial of f is given by
$$ \begin{align*} f^{\ast}(x) = x^{n} + a^{k} b^{-k} x^{n-k} + b^{-k}. \end{align*} $$
Suppose that
$f(x)$
is primitive over
$\mathbb {F}_{q^{m}}$
. By Lemma 2.1, it follows that
$f^{\ast }(x)$
is also primitive over
$\mathbb {F}_{q^{m}}$
. Now, by Lemma 2.2, the polynomial
$$ \begin{align*} g(x) = a^{-n} b^{n} f^{\ast}(a b^{-1} x) = x^{n} + x^{n-k} + a^{-n} b^{n-k} \end{align*} $$
is primitive over
$\mathbb {F}_{q^{m}}$
. Therefore, by Lemma 2.3, we conclude that
$a^{n} b^{k-n} \notin \mathbb {F}_{q^{u}}^{\ast }$
for any positive integer
$u < m$
, which completes the proof.
Corollary 3.3. Let
$m, n, k \in \mathbb {N}$
with
$m, n \geq 2$
and
$k \geq 1$
. Let
$a, b \in \mathbb {F}_{q^{m}}^{\ast }$
.
-
(i) If
$n \equiv k \pmod {q^m - 1}$
and
$a^{k} \in \mathbb {F}_{q^{s}} \subsetneqq \mathbb {F}_{q^{m}}$
, then the trinomial
$x^{n} + a^{k} x^{k} + b^{k}$
is not primitive over
$\mathbb {F}_{q^{m}}$
. -
(ii) If
$k \equiv 1 \pmod {q^m - 1}$
and
$a^{n} b^{1-n} \in \mathbb {F} _{q^{s}} \subsetneqq \mathbb {F}_{q^{m}}$
, then the trinomial
$x^{n} + a^{k} x^{k} + b^{k}$
is not primitive over
$\mathbb {F}_{q^{m}}$
.
Proof. Note that if
$n \equiv k \pmod {q^m - 1}$
, then
$a^{n} b^{k-n} = a^{k}$
, and if
$k \equiv 1 \pmod {q^m - 1}$
, then
$a^{n} b^{k-n} = a^{n} b^{1-n}$
. The conclusion follows immediately from Theorem 3.2.
Example 3.4. Let
$\mathbb {F}_{2^{2}}^{\ast } = \langle \alpha \rangle $
, where
$\alpha ^{2} + \alpha + 1 = 0$
. Then, for all positive integers
$k, k'$
, the trinomial
$$ \begin{align*} x^{3k' + k} + x^{k} + \beta^{k} \end{align*} $$
is not primitive over
$\mathbb {F}_{2^{2}}[x]$
.
The following theorem provides a generalisation of Theorems 3.1 and 3.2 covering another class of polynomials.
Theorem 3.5. Let
$m, n \in \mathbb {N}$
with
$m, n \geq 2$
and let
$I \subset \{1, 2, \ldots , n-1\}$
. Let
$a \in \mathbb {F}_{q^{m}}^{\ast }$
. Suppose that there exists a positive integer
$u < m$
such that
$$ \begin{align*} a^{n} \in \mathbb{F}_{q^{u}}^{\ast}. \end{align*} $$
Then, the polynomial
$$ \begin{align*} x^{n} + \sum_{k \in I} a^{k} x^{k} + 1 \end{align*} $$
is not primitive over
$\mathbb {F}_{q^{m}}$
.
Proof. Set
$f(x) = x^{n} + \sum _{k \in I} a^{k} x^{k} + 1$
. Then, the reciprocal polynomial of f is
$$ \begin{align*} f^{\ast}(x) = x^{n} + \sum_{k \in I} a^{k} x^{n-k} + 1. \end{align*} $$
Suppose
$f(x)$
is primitive over
$\mathbb {F}_{q^{m}}$
. By Lemma 2.1,
$f^{\ast }(x)$
is also primitive over
$\mathbb {F}_{q^{m}}$
. By Lemma 2.2, the polynomial
$$ \begin{align*} g(x) = a^{-n} f^{\ast}(a x) = x^{n} + \sum_{k \in I} x^{n-k} + a^{-n} \end{align*} $$
is primitive over
$\mathbb {F}_{q^{m}}$
. Therefore, by Lemma 2.3, it follows that
$a^{n} \notin \mathbb {F}_{q^{u}}^{\ast }$
for any positive integer
$u < m$
, which contradicts the hypothesis. Hence,
$f(x)$
is not primitive over
$\mathbb {F}_{q^{m}}$
.
The following example provides a nonprimitive polynomial that is not covered by Theorem 3.5.
Example 3.6. Consider
$(q, m, n) = (2, 3, 8)$
. Let
$\mathbb {F}_{2^3} = \mathbb {F}_2[a]$
, where a is a root of the primitive polynomial
$x^3 + x + 1$
over
$\mathbb {F}_2$
. Then,
$a^8 = a \notin \mathbb {F}_{q^u}^\ast $
for any positive integer
$u < 3$
. Nevertheless, the polynomial
$$ \begin{align*} f(x) = x^8 + a^6 x^6 + a^5 x^5 + a^4 x^4 + a^3 x^3 + a^2 x^2 + a x + 1 \end{align*} $$
is irreducible but not primitive over
$\mathbb {F}_{2^3}$
.
Acknowledgement
We thank the anonymous referee for carefully reading our manuscript and for the valuable suggestions, which have significantly improved its presentation.
