The Construction and Determination of Irreducible Polynomials Over Finite Fields

Abstract

The approach for constructing the irreducible polynomials of arbitrary degree n over finite fields which is based on the number of the roots over the extension field is presented. At the same time, this paper includes a sample to illustrate the specific construction procedures. Then in terms of the relationship between the order of a polynomial over finite fields and the order of the multiplicative group of the extension field, a method which can determine whether a polynomial over finite fields is irreducible or not is proposed. By applying the Euclidean Algorithm, this judgment can be verified easily.

1 Introduction

Generating irreducible polynomials and determining their irreducibility is one of the challenging and important problems in the theory of finite fields and its applications, especially computer algebra [1], coding theory [2] and cryptography [3]. For instance, irreducible polynomials are often used as a basic unit in constructing stream ciphers for implementing linear feedback shift register. Since linear feedback shift registers are described by coefficients of polynomials, these polynomials should be treated as the key information. Due to their important role in various applications, recent advances in these areas have awakened an even more interest to the subject of such polynomials [4–9]. Let $F_{q}$ be the finite field of order $q = p^{k}$, where $p$ is a prime and $k$ is a positive integer. According to the field structure of $F_{q}$, there exists an irreducible polynomial of degree $n$ over finite field $F_{q}$ [9]. Kyuregyan [10, 11] presented some results on the constructive theory of synthesis of irreducible polynomials over $F_{{2^{s} }}$. Abrahamyan et al. [12, 13] considered recursive constructions of irreducible polynomials over finite fields.

This paper proposes a method for constructing irreducible polynomials over $F_{q}$ in terms of the number of the roots over the extension field. If $\varphi (q^{n} - 1) = q^{n} - q$, the irreducible polynomials of arbitrary degree $n$ over finite fields can be obtained by factoring $Q_{{q^{n} - 1}} (x)$, because the primitive polynomials over $F_{q}$ of degree $n$ are all the irreducible polynomials; If $\varphi (q^{n} - 1) \ne q^{n} - q$, the irreducible polynomials of arbitrary degree $n$ over finite fields can be obtained by factoring $I(q,n;x)$. Furthermore, The correlation between the order of a polynomial over finite fields and the order of the multiplicative group of the extension field is analyzed, and a sufficient and necessary condition on judging whether a polynomial of arbitrary degree $n$ over finite fields is irreducible or not is presented.

2 The Construction of Irreducible Polynomials Over $F_{q}$

In this section, we will construct the irreducible polynomials of arbitrary degree $n$ over finite fields based on the number of the roots over the extension field. Only monic polynomials, i.e., the polynomials whose leading coefficient is equal to 1, are studied in this paper.

Definition 2.1

[14]. Let $f(x) \in F_{q} [x]$ be a nonzero polynomial. If $f(0) \ne 0$, then the least positive integer $e$ for which $f(x)$ divides $x^{e} - 1$ is called the order of $f(x)$ and is denoted by ord$(f(x))$. If $f(0) = 0$, then $f(x) = x^{h} g(x)$, where $h \in N$ and $g(x) \in F_{q} [x]$ with $g(0) \ne 0$ are uniquely determined; ord$(f(x))$ is then defined to be ord$(g(x))$.

Theorem 2.2

[12]. Let $K$ be a field of characteristic $p$, $n$ a positive integer not divisible by $p$, and $\zeta$ a primitive $n$th root of unity over $K$. Then the polynomial $Q_{n} (x) = \prod\limits_{s = 1,\gcd (s,n) = 1}^{n} {(x - \zeta^{s} } )$ is called the $n$th cyclotomic polynomial over $K$.

By Definition 2.1, the order of any root of $Q_{n} (x)$ is $n$.

Theorem 2.3

[10]. Let $(q,n) = 1$. $Q_{n} (x)$ factors into $\frac{{\phi_{n} (x)}}{d}$ distinct monic irreducible polynomials in $F_{q} [x]$ of the same degree $d$, where $d$ is the least positive integer such that $q^{d} \equiv 1$ mod $n$.

Theorem 2.4.

Let $T_{q}^{n}$ be the number of irreducible polynomials in $F_{q} [x]$ of degree $n$, then

$$ \frac{{\phi (q^{n} - 1)}}{n} \le T_{q}^{n} \le \left[ {\frac{{q^{n} - q}}{n}} \right]. $$

In particular, for the case $\phi (q^{n} - 1) = q^{n} - q$, $T_{q}^{n} = \frac{{q^{n} - q}}{n}$.

Proof.

If $f(x)$ is an irreducible polynomial in $F_{q} [x]$ of degree $n$, then all roots of $f(x)$ are in $F_{{q^{n} }} - F_{q}$. Thus we have

$$ T_{q}^{n} \le \left[ {\frac{{q^{n} - q}}{n}} \right]. $$

The number of primitive polynomials in $F_{{q^{n} }} [x]$ of degree $n$ is $\frac{{\phi (q^{n} - 1)}}{n}$. Since the primitive polynomial over finite fields is irreducible as well, it follows that

$$ \frac{{\phi (q^{n} - 1)}}{n} \le T_{q}^{n} . $$

Therefore

$$ \frac{{\phi (q^{n} - 1)}}{n} \le T_{q}^{n} \le \left[ {\frac{{q^{n} - q}}{n}} \right]. $$

In particular, if $\phi (q^{n} - 1) = q^{n} - q$, $T_{q}^{n} = \frac{{q^{n} - q}}{n}$.

Corollary 2.5.

Let $T_{2}^{n}$ be the number of irreducible polynomial in $F_{2} [x]$ of degree $n$. If $2^{n} - 1$ is Mersenne prime, then $T_{2}^{n} = \frac{2}{n}(2^{n - 1} - 1)$.

Note that all the irreducible polynomials over $F_{q}$ of degree $n$ are primitive if $\phi (q^{n} - 1) = q^{n} - q$ by Theorem 2.4. Besides, the product of all primitive polynomials over $F_{q}$ of degree $n$ is equal to the cyclotomic polynomial $Q_{e} (x)$ with $e = q^{n} - 1$. Therefore, we will present a factorization method for $Q_{e} (x)$ over $F_{q}$.

Lemma 2.6

[14] (Berlekamp Algorithm). Let $f(x)$ be a polynomial over $F_{q}$ of degree $k$, $h(x) \in F_{q} [x]$, and $h(x) = \sum\limits_{l = 0}^{m - 1} {h_{l} } x^{l}$. Then we have

$$ f(x) = \prod\limits_{{c \in F_{q} }} {\gcd (f(x),h(x) - c)} h^{q} (x) \equiv h(x)\bmod (f(x)). $$

Note that the key to factoring the polynomial of degree $k$ by applying Berlekamp algorithm is to find the polynomial $h(x)$ whose degree is at most $k - 1$. Similarly, the first method of factoring $Q_{{q^{n} - 1}} (x)$ over $F_{q}$ is given by the following theorem.

Theorem 2.7.

Let $h(x) \in F_{q} [x]$ and $h(x) = \sum\limits_{l = 0}^{m - 1} {h_{l} } x^{l}$, where $(m,q) = 1$.

If $h_{lq\;\bmod \;m} = h_{1} \left( {l = 0,1, \ldots ,m - 1} \right)$, then $h(x)^{q} = h(x)\bmod Q_{m} (x)$ and we have $Q_{m} (x) = \prod\limits_{{c \in F_{q} }} {\gcd (Q_{m} (x),h(x) - c)}$.

Proof.

We first prove that $h\left( x \right)^{q} = h\left( x \right)\bmod \left( {x^{m} - 1} \right)$.

Let $s_{l} = lq(\bmod \;m)$ and $l = 0,1, \ldots ,m - 1$. Since $(m,q) = 1$, then $s_{1} \;\bmod \;m$ will go through all the elements in $0,1, \ldots ,m - 1$. Thus we have

$$ \begin{aligned} h(x)^{q} & = \sum\limits_{l = 0}^{m - 1} {h_{l} } x^{{s_{l} }} \bmod (x^{m} - 1) = \sum\limits_{l = 0}^{m - 1} {h_{{s_{l} }} } x^{{s_{l} }} = \sum\limits_{l = 0}^{m - 1} {h_{l} } x^{l} = h(x), \\ h(x)^{q} & = h(x)\bmod (x^{m} - 1). \\ \end{aligned} $$

Note that

$$ Q_{m} (x)|x^{m} - 1, $$

So

$$ h(x)^{q} = h(x)\bmod Q_{m} (x). $$

The conclusion then follows from Lemma 2.6.

Example 2.8.

We construct all irreducible polynomials in $F_{2} [x]$ of degree 3 in accordance with Theorem 2.7.

Since $2^{3} - 1$ is a Mersenne prime, then all the irreducible polynomials over $F_{2}$ of degree 3 are primitive, which can be obtained by factoring $Q_{7} (x)$ over $F_{2}$, where $Q_{7} (x) = x^{6} + x^{5} + x^{4} + x^{3} + x^{2} + x + 1$. By Theorem 2.7, $l \to 2l\bmod n$ is a permutation of $\left\{ {0,1, \ldots ,n - 1} \right\}$.

Let $U_{7} = \{ 0,1,2,3,4,5,6\}$. The permutation of $U_{7}$ can be expressed as $\left( \begin{aligned} 0123456 \hfill \\ 0246135 \hfill \\ \end{aligned} \right)$, which implies three cycle including $\left( 0 \right),\left( {1,2,4} \right)$ and $(3,6,5)$. Each of cycles can determine a polynomial satisfying Theorem 2.7, $h_{1} (x) = 1,h_{2} (x) = x^{4} + x^{2} + x,h_{3} (x) = x^{6} + x^{5} + x^{3}$.

By Theorem 2.7 and Euclidean algorithm, we have

$$ (Q_{7} (x),h_{2} (x)) = x^{3} + x + 1, $$

$$ (Q_{7} (x),h_{2} (x) + 1) = x^{3} + x^{2} + 1. $$

Hence, $Q_{7} (x) = (x^{3} + x^{2} + 1)(x^{3} + x + 1)$ and all irreducible polynomials in $F_{2} [x]$ of degree 3 are $x^{3} + x^{2} + 1$ and $x^{3} + x + 1$.

Remark.

If $\phi (q^{n} - 1) \ne q^{n} - q$, all irreducible polynomials in $F_{q} [x]$ can be determined by factoring $I(q,n;x)$ which is the product of all irreducible polynomials in $F_{q} [x]$ of degree $n$ [14].

3 The Determination of Irreducible Polynomials Over $F_{q}$

According to the relationship between the order of a polynomial over finite fields and the order of the multiplicative group of the extension field, and the construction of irreducible polynomials above, we will present a sufficient and necessary condition on judging whether a polynomial of arbitrary degree $n$ over finite fields is irreducible or not.

For irreducible polynomials in $F_{q} [x]$ of degree $n$, which satisfy $\phi (q^{n} - 1) = q^{n} - q$,

we can get the following theorem by the discussion in Sect. 2.

Theorem 3.1.

Let $f(x) \in F_{q} [x]$ be a polynomial over $F_{q}$ of degree $n$ and $\phi (q^{n} - 1) = q^{n} - q$. $f(x)$ is irreducible if and only if ord$(f(x)) = q^{n} - 1$.

Lemma 3.2

[12]. For every finite field $F_{q}$ and every $n \in N$, the product of all irreducible polynomials over $F_{q}$ whose degree divides $n$ is equal to $x^{{q^{n} }} - x$.

Lemma 3.3

[12]. Let $c$ be a positive integer. Then the polynomial $f(x) \in F_{q} [x]$ with $f(0) \ne 0$ divides $x^{c} - 1$ if and only if ord$(f(x))|c$.

Let $f(x)$ be a polynomials in $F_{q} [x]$ of degree $n$, and $n = p_{1}^{{t_{1} }} p_{2}^{{t_{2} }} \ldots p_{s}^{{t_{s} }}$ is the prime factor decomposition of $n$. Let $n_{i} = n/p_{i}$.

Theorem 3.4.

Let $f(x)$ be a polynomial over $F_{q}$ of degree $n$. If $f(x)$ satisfies the following properties:

• (1) ord$(f(x))|q^{n} - 1$;

• (2) For every $c \in F_{q}$, $f(c) \ne 0$;

• (3) gcd(ord$(f(x)),q^{{n_{i} }} - 1) = 1$, $\left( {i = 1,2, \ldots ,s} \right)$

then $f(x)$ is an irreducible polynomial over $F_{q}$.

Proof.

Since ord$(f(x))|q^{n} - 1$,we have $f(x)|x^{{q^{n} - 1}} - 1$.

According to Lemma 3.3, $f(x)$ has no repeated factor. Suppose $f(x)$ were reducible over $F_{q}$. Then we have a factorization $f(x) = f_{1} (x)f_{2} (x) \ldots f_{t} (x)$, where each $f_{j} (x)$ $(j = 1,2, \ldots ,t)$ are pairwise relatively prime. Since $f_{j} (x)|x^{{q^{n} - 1}} - 1$, then

$$ {\rm deg}(f_{j} (x))|n\;\;(j = 1,2, \ldots ,t). $$

we claim that

Suppose ${\rm deg}(f_{j} (x))|n_{k}$ for some $1 \le k \le s$. Then

$$ f_{j} (x)|x^{{q^{{n_{k} }} }} - x\quad {\text{and}}\quad f_{j} (x)|x^{{q^{{n_{k} }} - 1}} - 1. $$

By Lemma 3.2, since

$$ {\text{ord}}\left( {f_{j} \left( x \right)} \right) | {\text{q}}^{{n_{k} }} { - 1}\;{\text{and ord}}\;f_{j} \left( x \right)|{\text{ord}}\;f\left( x \right), $$

by Lemma 3.3, we have

$$ { \gcd }\left( {{\text{ord}}\left( {f\left( x \right)} \right),q^{{n_{k} }} - 1} \right) \ne 1. $$

a contradiction to (3). Therefore, ${\rm deg }(f_{j} (x)) = n$ and $f_{j} (x) = f(x)$. Hence,$f(x)$ is an irreducible polynomial over $F_{q}$.

Theorem 3.5.

If $f(x)$ is an irreducible polynomial over $F_{q}$, then

• (1) ord$(f(x))|q^{n} - 1$;

• (2) For every $c \in F_{q}$,$f(c) \ne 0$;

• (3)

Proof.

Since $f(x)$ is an irreducible polynomial over $F_{q}$ of degree $n$, then $f(c) \ne 0$ for every $c \in F_{q}$, and ord$(f(x))|q^{n} - 1$.

Suppose

$$ {\text{ord}}\left( {f\left( x \right)} \right) |\;q^{{n_{k} }} - 1\;\;{\text{for some}}\;\;\; 1\le k \le s. $$

According to Lemma 3.3,

$$ f(x)|x^{{q^{{n_{k} }} - 1}} - 1. $$

Then

$$ f(x)|x^{{q^{{n_{k} }} }} - x. $$

Hence, ${\rm deg}(f(x))|n_{{_{k} }}$, a contradiction to ${\rm deg}(f(x)) = n$ by Lemma 3.2. Therefore,

The following results can be implied by above two theorems.

Corollary 3.6.

Let $f(x)$ be a polynomial over $F_{q}$ of degree $p$, where $p$ is a prime. Then $f(x)$ is irreducible if and only if:

• (1) ord$(f(x))|q^{p} - 1$;

• (2) For every $c \in F_{q}$, $f(c) \ne 0$.

Corollary 3.7.

Let $f(x)$ be a polynomial over $F_{q}$ of degree $n = p_{1} p_{2}$, where $p_{1}$ and $p_{2}$ are prime numbers. Then $f(x)$ is irreducible if and only if:

• (1) ord$(f(x))|q^{n} - 1$;

• (2) For every $c \in F_{q}$, $f(c) \ne 0$;

• (3)

4 Conclusion

Irreducible polynomials over finite fields play an important role in computer algebra, coding theory and cryptography. This paper constructed the irreducible polynomials of arbitrary degree n over finite fields based on the number of the roots over the extension field and determined whether a polynomial over finite fields is irreducible or not in terms of the relationship between the order of a polynomial over finite fields and the order of the multiplicative group of the extension field. Furthermore, a relevant example was analyzed to show the specific construction procedures.