# Revisiting the Factorization ofxn+1 over Finite Fields with Applications

Authors: Arunwan Boripan; Somphong Jitman
Journal: Journal of Mathematics
 (2021)

---

## Abstract

The polynomialxn+1 over finite fields has been of interest due to its applications in the study of negacyclic codes over finite fields. In this paper, a rigorous treatment of the factorization of xn+1 over finite fields is given as well as its applications. Explicit and recursive methods for factorizing xn+1 over finite fields are provided together with the enumeration formula. As applications, some families of negacyclic codes are revisited with more clear and simpler forms.


---

## Body

## 1. Introduction

In coding theory, the polynomialxn+1 over finite fields plays an important role in the study of negacyclic codes (see [1–5] and references therein). Precisely, a negacyclic code of length n over Fq can be uniquely determined by an ideal in the principal ring Fqx/xn+1 generated by a monic divisor of xn+1. A brief discussion on the factorization of xn+1 over finite fields Fq has been given in [3, 4]. In the case where the characteristic of Fq is even, the factorization of xn+1=xn−1 over Fq has been given and applied in the study of cyclic codes over finite fields in [6]. In [7, 8], an explicit form of the factorization of x2i+1 over finite fields of odd characteristic has been established. Some results on the factorization of xn−λ over finite fields have been presented in [5].In this paper, we focus on the factorization ofxn+1 over finite fields Fq for arbitrary positive integers n and all odd prime powers q. If the characteristic of Fq is p, we have xpsn+1=xn+1ps, for all integers n≥1 and s≥0. It is therefore sufficient to study the factorization of xn+1 over Fq such that n is coprime to q. Here, we write n=2in′ for some integer i≥0 and odd positive integer n′ such that gcdn′,q=1.Before proceeding to the general results, we consider a pattern on the factorization ofx2i11+1 over F5. We have(1)x2⋅11+1=f1xf2xf3xf4xf5xf6x,x22⋅11+1=f1x2f2x2f3x2f4x2f5x2f6x2,⋮x2i⋅11+1=f1x2i−1f2x2i−1f3x2i−1f4x2i−1f5x2i−1f6x2i−1,for all i≥1, where f1x=x+2, f2x=x+3, f3x=x5+x4+x3+2x2+x+2, f4x=x5+2x4+x3+2x2+3x+2, f5x=x5+3x4+x3+3x2+3x+3, and f6x=x5+4x4+x3+3x2+x+3. It is easily seen that the factorization can be determined recursively on the exponent i of 2 and the number of monic irreducible factors of x2i11+1 is a constant independent of i≥2.In this paper, a complete study on the above pattern of the factorization ofx2in′+1 over Fq is given. Precisely, we prove that there exists a positive integer k such that the number of monic irreducible factors of x2in′+1 over Fq becomes a constant for all positive integers i≥k. In the cases where ordn′q is odd, a complete recursive factorization of x2in′+1 over Fq is provided together with a recursive formula for the number of its monic irreducible factors for all positive integers i. In the cases where ordn′q is even, a recursive factorization of x2in′+1 over Fq is given for all positive integers i≥k. As applications, constructions and enumerations of some negacyclic codes of lengths 2in′ over Fq are given based on the above results.The paper is organized as follows. Preliminary concepts and results on the factorization ofxn+1 over finite fields are recalled in Section 2. In Section 3, the number theoretical results and properties of q-cyclotomic cosets required in the study of the factorization of x2in′+1 are established. Recursive methods for factorizing x2in′+1 and enumerating its monic irreducible factors are given in Section 4. Applications in the study of negacyclic codes over finite fields are revisited in Section 5.


## 2. Preliminary

In this section, basic concepts and tools used in the study of the factorization ofxn+1 over finite fields and the enumeration of its monic irreducible factors are recalled.For a positive integera and an integer s, the notation 2s‖a is used whenever s is the largest integer such that a is divisible by 2s, or equivalently, 2s|a but 2s+1∤a. For an integer a and a positive integer n, denote by Θna the additive order of a modulo n. In the case where gcda,n=1, denote by ordna the multiplicative order of a modulo n. By abuse of notation, we write ord1a=1.For a prime powerq, a positive integer n coprime to q, and an integer 0≤a<n, the q-cyclotomic coset moduloncontaininga is defined to be(2)Clq,na=aqjmodn|j=0,1,2,….It is not difficult to see thatClq,na=aqjmodn|0≤j<ordΘnaq and Clq,na=ordΘnaq. Moreover, Θna=Θnj for all j∈Clq,na. Let Sqn denote a complete set of representatives of the q-cyclotomic cosets modulo n, and let α be a primitive nth root of unity in some extension field of Fq. It is well known (see [9]) that(3)xn−1=∏a∈Sqnfax,where(4)fax=∏j∈Clq,nax−αj,is the minimal polynomial of αa over Fq referred as the irreducible polynomial induced by Clq,na.In [10], a basic idea for the factorization of x2in′+1 is given using (3) and the following lemmas.Lemma 1 (see [10], Lemma 2).
Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Let i≥0 and 0≤a<2i+1n′ be integers. Then, the elements in Clq,2i+1n′a have the same parity.Lemma 2 (see [10], Lemma 3).
Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Let i≥0 and 0≤a<2i+1n′ be integers. Then, the polynomial fax induced by Clq,2i+1n′a is a divisor of x2in′+1 if and only if a is odd.From Lemma1, the parity of a representative of Clq,2i+1n′a is independent of its choices. By Lemma 2, the monic irreducible divisors of x2in′+1 are induced by the q-cyclotomic cosets modulo 2i+1n′ containing odd integers. Let SOqn (resp., SEqn) denote a complete set of representatives of the q-cyclotomic cosets containing odd integers (resp., even integers) modulo n. It follows that(5)x2in′+1=x2i+1n′−1x2in′−1=∏a∈SOq2i+1n′fax,for all i≥0.For a positive integern and a prime power q, let Nqn denote the number of monic irreducible factors of xn+1 over Fq. Based on ([3], equation 3.1), it can be deduced that(6)Nq2in′=∑d|n′ϕ2i+1dord2i+1dq.As discussed above, theq-cyclotomic cosets modulo 2i+1n′ containing odd integers are key to determine the factorization of x2in′+1 over Fq and the enumeration of its monic irreducible factors. Properties of these cosets are studied in Section 3.


## 3. Number Theoretical Results and Cyclotomic Cosets

In this section, number theoretical results required in the factorization ofx2in′+1 are derived. Subsequently, properties of q-cyclotomic cosets modulo 2i+1n′ containing odd integers are established for all positive integers i and odd positive integers n′. These results are key in the study of the factorization of x2in′+1 in Section 4.A relation on the carnality of theq-cyclotomic costs containing odd integers a and a+2in′ modulo 2i+1n′ is given in the following lemma.Lemma 3.
Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Then, Clq,2i+1n′a=Clq,2i+1n′a+2in′ for all odd integers a and for all positive integers i.Proof.
Leta be an odd integer, and let i be a positive integer. Then,(7)Θ2i+1n′a=2i+1n′gcd2i+1n′,a=2i+1n′gcdn′,a=2i+1n′gcdn′,a+2in′,=2i+1n′gcd2i+1n′,a+2in′=Θ2i+1n′a+2in′.
Hence,(8)Clq,2i+1n′a=ordΘ2i+1n′aq=ordΘ2i+1n′a+2in′q=Clq,2i+1n′a+2in′,as desired.Properties ofq-cyclotomic cosets with q≡1mod4 and q≡3mod4 are given separately in the following sections.


### 3.1.q≡3mod4

In this section, we focus on properties ofq-cyclotomic cosets in the case where q≡3mod4.First, an explicit formula forord2iq is recalled for all odd prime powers q≡3mod4 and positive integers i. This result can be derived from ([11], Proposition 1). For completeness, a detailed proof is given.Lemma 4.
Letq be an odd prime power, and let β be the positive integer such that 2β‖q2−1. Let i be a positive integer. If q≡3mod4, then(9)ord2iq=1,ifi=1,2,if2≤i≤β,2i−β+1,ifi≥β+1.Proof.
Assume thatq≡3mod4. Then, 2‖q−1 and 2i|q2−1, for all 2≤i≤β. Since q3−1=q−1q2+q+1 and q2+q+1 is odd, we have 2‖q3−1. Hence, ord2q=1 and ord2iq=2, for all 2≤i≤β.
Assume thati≥β+1. Since q≡3mod4, it follows that q2j≡1mod4, for all j≥1. Hence, 2‖q2j+1, for all j≥1. Since q2i−β−1q2i−β+1=q2i−β+1−1=q2−1∏j=1i−βq2j+1, we have 2i‖q2β−i+1−1 and 2i∤q2t−1, for all t≤β+i. Hence, ord2iq=2i−β+1, for all i≥β+1.Properties ofq-cyclotomic cosets modulo 2i+1n′ containing odd integers are established in Proposition 1.Proposition 1.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ≥0 be the integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifλ=0, then the following statements hold:(a)
Clq,2i+1n′a≠Clq,2i+1n′a+2in′ all odd integers a and integers 2≤i≤β−1(b)
Clq,2i+1n′a=Clq,2i+1n′a+2in′=Clq,2in′a∪Clq,2in′a+2in′ for all odd integers a and integers i=1 or i≥β(ii)
Ifλ>0, then the following statements hold:(a)
Clq,2λ+β−1n′1≠Clq,2λ+β−1n′1+2λ+β−2n′(b)
Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′ for all odd integers a and integers i≥λ+β−1Proof.
First, we observe thatβ≥3, 2‖q−1 and 2β−1‖q+1.
To prove (i), assume thatλ=0. In this case, ordn′q is odd which implies that ordΘn′aq is odd for all odd positive integers a.
To prove (a), leta be an odd integer, and let i be an integer such that 2≤i≤β−1. By Lemma 4, it follows that ord2iq=2=ord2i+1q. Since ordΘn′aq is odd, it can be deduced that ordΘ2i+1n′aq=ord2i+1Θn′aq=lcmord2i+1q,ordΘn′aq=lcmord2iq,ordΘn′aq=ordΘ2in′aq. Suppose that Clq,2i+1n′a=Clq,2i+1n′a+2in′. Since a≢a+2in′mod2i+1n′, there exists 0<j<ordΘ2i+1n′aq such that a+2in′≡aqjmod2i+1n′. Hence, we have a≡aqjmod2in′ which implies that ordΘ2in′aq≤j<ordΘ2i+1n′aq=ordΘ2in′aq, a contradiction. Therefore, Clq,2i+1n′a≠Clq,2i+1n′a+2in′, as desired.
To prove (b), leta be an odd integer, and let i be an integer such that i=1 or i≥β. By Lemma 4, we have ord2i+1q=2ord2iq. Since ordn′q is odd, we have ord2i+1n′q=lcmord2i+1q,ordn′q=lcm2ord2iq,ordn′q=2ord2in′q which implies that aqord2in′q≢amod2i+1n′. Since aqord2in′q≡amod2in′, we have aqord2in′q≡a+2in′mod2i+1n′. Hence, a+2in′∈Clq,2i+1n′a which implies that Clq,2i+1n′a=Clq,2i+1n′a+2in′. This proves the first equality.
For the second equality, letb∈Clq,2i+1n′a. Then, b≡aqjmod2i+1n′ for some 0≤j<ordΘ2i+1n′aq. It follows that b≡aqjmod2in′. If b<2in′, then b∈Clq,2in′a. Otherwise, b−2in′∈Clq,2in′a which implies that b∈Clq,2in′a+2in′. Hence, Clq,2i+1n′a⊆Clq,2in′a∪Clq,2in′a+2in′. Since Clq,2in′a and Clq,2in′a+2n′ are disjoint sets of the same size ordΘ2in′aq, we have Clq,2in′a=ordΘ2i+1n′aq=2ordΘ2in′aq=Clq,2in′a∪Clq,2in′a+2in′. Therefore, Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′ as desired.
To prove (ii), assume thatλ>0. For (a), suppose that 1∈Clq,2λ+β−1n′1+2λ+β−2n′. If λ=1, then λ+β−1=β, we have ord2λ+β−1q=2=ord2λ+β−2q by Lemma 4. Since 2‖ordn′q, we have ordn′q/2 is odd and it follows that ord2λ+β−1n′q=lcmord2λ+β−1q,ordn′q=lcmord2λ+β−2q,ordΘn′aq=ordΘ2λ+β−2n′aq. Assume that λ≥2. Since λ+β−1≥β+1, we have ord2λ+β−1q=2λ and ord2λ+β−2q=2λ−1 by Lemma 4. Since 2λ‖ordn′q, it follows that(10)ord2λ+β−1n′q=lcmord2λ+β−1q,ordn′q=lcm2λ,ordn′q=lcm2λ−1,ordn′q=lcmord2λ+β−2q,ordn′q=ord2λ+β−2n′q.
Since2λ‖ordn′q, ordn′q/2λ is odd. Hence, ord2λ+β−1n′q=lcmord2λ+β−1q,ordn′q=lcmord2λ+β−2q,ordn′q=ord2λ+β−2n′q. Since 1+2λ+β−2n′≢1mod2λ+β−1n′, we have 1+2λ+β−2n′≡qjmod2λ+β−1n′ for some 0<j<ordΘ2λ+β−1n′1q=ord2λ+β−1n′q. It follows that 1≡qjmod2λ+β−2n′ which implies that ord2λ+β−2n′q≤j<ord2λ+β−1n′q=ord2λ+β−2n′q, a contradiction. Therefore, Clq,2λ+β−1n′1≠Clq,2λ+β−1n′1+2λ+β−2n′, as desired.
To prove (b), leta be an odd integer, and let i be an integer such that i≥λ+β−1. Then, i≥β which implies that ord2i+1q=2ord2iq and ord2iq=2i−β+1≥2λ by Lemma 4. Since 2λ‖ordn′q, ordn′q/2λ is odd and(11)ord2i+1n′q=lcmord2i+1q,ordn′q=lcm2ord2iq,ordn′q=lcm2ord2iq,ordn′q2λ=2lcmord2iq,ordn′q2λ=2lcmord2iq,ordn′q=2ord2in′q,which implies that aqord2in′q≢amod2i+1n′. Since aqord2in′q≡amod2in′, we have aqord2in′q≡a+2in′mod2i+1n′. Hence, a+2in′∈Clq,2i+1n′a which implies that Clq,2i+1n′a=Clq,2i+1n′a+2n′. The first equality holds.
For the second equality, letb∈Clq,2i+1n′a. Then, b≡aqjmod2i+1n′ for some 0≤j<ordΘ2i+1n′aq. It follows that b≡aqjmod2in′. If b<2in′, then b∈Clq,2in′a. Otherwise, b−2in′∈Clq,2in′a which implies that b∈Clq,2in′a+2in′. Hence, Clq,2i+1n′a⊆Clq,2in′a∪Clq,2in′a+2in′. Since Clq,2in′a and Clq,2in′a+2in′ are disjoint sets of the same size ordΘ2in′aq, we have Clq,2i+1n′a=ordΘ2i+1n′aq=2ordΘ2in′aq=Clq,2in′a∪Clq,2in′a+2in′. Therefore, Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′ as desired.


### 3.2.q≡1mod4

Here, we investigate properties ofq-cyclotomic cosets in the case where q≡1mod4. We begin with an explicit formula for ord2iq which can be derived from ([11], Proposition 1). For completeness, a rigorous proof is provided.Lemma 5.
Letq be an odd prime power, and let β be the positive integer such that 2β‖q2−1. Let i be a positive integer. If q≡1mod4, then(12)ord2iq=1,if1≤i≤β−1,2i−β+1,ifi≥β.Proof.
Assume thatq≡1mod4. Then, 2β−1‖q−1 which implies that ord2iq=1, for all 1≤i≤β−1. Next, assume that i≥β. Since q≡1mod4, it follows that q2j≡1mod4 for all j≥0. Hence, 2‖q2j+1 for all j≥0. Since q2i−β−1q2i−β+1=q2i−β+1−1=q−1∏j=0i−βq2j+1, it can be concluded that 2i‖q2β−i+1−1 and 2i∤q2t−1, for all t≤β+i. As desired, we have ord2iq=2i−β+1 for all i≥β.Proposition 2.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ≥0 be the integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β||q2−1. Then, the following statements hold:
(i)
Ifλ=0, then(a)
Clq,2i+1n′a≠Clq,2i+1n′a+2in′ for all odd integers a and integers 1≤i≤β−2(b)
Clq,2i+1n′a=Clq,2i+1n′a+2in′=Clq,2in′a∪Clq,2in′a+2in′ for all odd integers a and integers i≥β−1(ii)
Ifλ>0, then(a)
Clq,2λ+β−1n′1≠Clq,2iλ+β−1n′1+2λ+β−2n′(b)
Clq,2i+1n′a=Clq,2i+1n′a+2in′=Clq,2in′a∪Clq,2in′a+2in′ for odd integers a and integers i≥λ+β−1Proof.
First, we observe thatβ≥3, 2‖q+1 and 2β−1‖q−1. Using Lemma 5 and arguments similar to those in the proof of Proposition 1, the following key results can be deduced:(1)
Ifλ=0, then ordΘ2i+1n′aq=ordΘ2in′aq, for all odd integers a and integers 1≤i≤β−2, and ord2i+1n′q=2ord2in′q, for all integers i≥β−1.(2)
Ifλ>0, then ord2λ+β−1n′q=ord2λ+β−2n′q and ord2i+1n′q=2ord2in′q, for all integers i≥λ+β−1.
The complete proof can be obtained using arguments similar to those in Proposition1, while the above discussion and Lemma 5 is applied instead of Lemma 4.


## 3.1.q≡3mod4

In this section, we focus on properties ofq-cyclotomic cosets in the case where q≡3mod4.First, an explicit formula forord2iq is recalled for all odd prime powers q≡3mod4 and positive integers i. This result can be derived from ([11], Proposition 1). For completeness, a detailed proof is given.Lemma 4.
Letq be an odd prime power, and let β be the positive integer such that 2β‖q2−1. Let i be a positive integer. If q≡3mod4, then(9)ord2iq=1,ifi=1,2,if2≤i≤β,2i−β+1,ifi≥β+1.Proof.
Assume thatq≡3mod4. Then, 2‖q−1 and 2i|q2−1, for all 2≤i≤β. Since q3−1=q−1q2+q+1 and q2+q+1 is odd, we have 2‖q3−1. Hence, ord2q=1 and ord2iq=2, for all 2≤i≤β.
Assume thati≥β+1. Since q≡3mod4, it follows that q2j≡1mod4, for all j≥1. Hence, 2‖q2j+1, for all j≥1. Since q2i−β−1q2i−β+1=q2i−β+1−1=q2−1∏j=1i−βq2j+1, we have 2i‖q2β−i+1−1 and 2i∤q2t−1, for all t≤β+i. Hence, ord2iq=2i−β+1, for all i≥β+1.Properties ofq-cyclotomic cosets modulo 2i+1n′ containing odd integers are established in Proposition 1.Proposition 1.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ≥0 be the integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifλ=0, then the following statements hold:(a)
Clq,2i+1n′a≠Clq,2i+1n′a+2in′ all odd integers a and integers 2≤i≤β−1(b)
Clq,2i+1n′a=Clq,2i+1n′a+2in′=Clq,2in′a∪Clq,2in′a+2in′ for all odd integers a and integers i=1 or i≥β(ii)
Ifλ>0, then the following statements hold:(a)
Clq,2λ+β−1n′1≠Clq,2λ+β−1n′1+2λ+β−2n′(b)
Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′ for all odd integers a and integers i≥λ+β−1Proof.
First, we observe thatβ≥3, 2‖q−1 and 2β−1‖q+1.
To prove (i), assume thatλ=0. In this case, ordn′q is odd which implies that ordΘn′aq is odd for all odd positive integers a.
To prove (a), leta be an odd integer, and let i be an integer such that 2≤i≤β−1. By Lemma 4, it follows that ord2iq=2=ord2i+1q. Since ordΘn′aq is odd, it can be deduced that ordΘ2i+1n′aq=ord2i+1Θn′aq=lcmord2i+1q,ordΘn′aq=lcmord2iq,ordΘn′aq=ordΘ2in′aq. Suppose that Clq,2i+1n′a=Clq,2i+1n′a+2in′. Since a≢a+2in′mod2i+1n′, there exists 0<j<ordΘ2i+1n′aq such that a+2in′≡aqjmod2i+1n′. Hence, we have a≡aqjmod2in′ which implies that ordΘ2in′aq≤j<ordΘ2i+1n′aq=ordΘ2in′aq, a contradiction. Therefore, Clq,2i+1n′a≠Clq,2i+1n′a+2in′, as desired.
To prove (b), leta be an odd integer, and let i be an integer such that i=1 or i≥β. By Lemma 4, we have ord2i+1q=2ord2iq. Since ordn′q is odd, we have ord2i+1n′q=lcmord2i+1q,ordn′q=lcm2ord2iq,ordn′q=2ord2in′q which implies that aqord2in′q≢amod2i+1n′. Since aqord2in′q≡amod2in′, we have aqord2in′q≡a+2in′mod2i+1n′. Hence, a+2in′∈Clq,2i+1n′a which implies that Clq,2i+1n′a=Clq,2i+1n′a+2in′. This proves the first equality.
For the second equality, letb∈Clq,2i+1n′a. Then, b≡aqjmod2i+1n′ for some 0≤j<ordΘ2i+1n′aq. It follows that b≡aqjmod2in′. If b<2in′, then b∈Clq,2in′a. Otherwise, b−2in′∈Clq,2in′a which implies that b∈Clq,2in′a+2in′. Hence, Clq,2i+1n′a⊆Clq,2in′a∪Clq,2in′a+2in′. Since Clq,2in′a and Clq,2in′a+2n′ are disjoint sets of the same size ordΘ2in′aq, we have Clq,2in′a=ordΘ2i+1n′aq=2ordΘ2in′aq=Clq,2in′a∪Clq,2in′a+2in′. Therefore, Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′ as desired.
To prove (ii), assume thatλ>0. For (a), suppose that 1∈Clq,2λ+β−1n′1+2λ+β−2n′. If λ=1, then λ+β−1=β, we have ord2λ+β−1q=2=ord2λ+β−2q by Lemma 4. Since 2‖ordn′q, we have ordn′q/2 is odd and it follows that ord2λ+β−1n′q=lcmord2λ+β−1q,ordn′q=lcmord2λ+β−2q,ordΘn′aq=ordΘ2λ+β−2n′aq. Assume that λ≥2. Since λ+β−1≥β+1, we have ord2λ+β−1q=2λ and ord2λ+β−2q=2λ−1 by Lemma 4. Since 2λ‖ordn′q, it follows that(10)ord2λ+β−1n′q=lcmord2λ+β−1q,ordn′q=lcm2λ,ordn′q=lcm2λ−1,ordn′q=lcmord2λ+β−2q,ordn′q=ord2λ+β−2n′q.
Since2λ‖ordn′q, ordn′q/2λ is odd. Hence, ord2λ+β−1n′q=lcmord2λ+β−1q,ordn′q=lcmord2λ+β−2q,ordn′q=ord2λ+β−2n′q. Since 1+2λ+β−2n′≢1mod2λ+β−1n′, we have 1+2λ+β−2n′≡qjmod2λ+β−1n′ for some 0<j<ordΘ2λ+β−1n′1q=ord2λ+β−1n′q. It follows that 1≡qjmod2λ+β−2n′ which implies that ord2λ+β−2n′q≤j<ord2λ+β−1n′q=ord2λ+β−2n′q, a contradiction. Therefore, Clq,2λ+β−1n′1≠Clq,2λ+β−1n′1+2λ+β−2n′, as desired.
To prove (b), leta be an odd integer, and let i be an integer such that i≥λ+β−1. Then, i≥β which implies that ord2i+1q=2ord2iq and ord2iq=2i−β+1≥2λ by Lemma 4. Since 2λ‖ordn′q, ordn′q/2λ is odd and(11)ord2i+1n′q=lcmord2i+1q,ordn′q=lcm2ord2iq,ordn′q=lcm2ord2iq,ordn′q2λ=2lcmord2iq,ordn′q2λ=2lcmord2iq,ordn′q=2ord2in′q,which implies that aqord2in′q≢amod2i+1n′. Since aqord2in′q≡amod2in′, we have aqord2in′q≡a+2in′mod2i+1n′. Hence, a+2in′∈Clq,2i+1n′a which implies that Clq,2i+1n′a=Clq,2i+1n′a+2n′. The first equality holds.
For the second equality, letb∈Clq,2i+1n′a. Then, b≡aqjmod2i+1n′ for some 0≤j<ordΘ2i+1n′aq. It follows that b≡aqjmod2in′. If b<2in′, then b∈Clq,2in′a. Otherwise, b−2in′∈Clq,2in′a which implies that b∈Clq,2in′a+2in′. Hence, Clq,2i+1n′a⊆Clq,2in′a∪Clq,2in′a+2in′. Since Clq,2in′a and Clq,2in′a+2in′ are disjoint sets of the same size ordΘ2in′aq, we have Clq,2i+1n′a=ordΘ2i+1n′aq=2ordΘ2in′aq=Clq,2in′a∪Clq,2in′a+2in′. Therefore, Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′ as desired.


## 3.2.q≡1mod4

Here, we investigate properties ofq-cyclotomic cosets in the case where q≡1mod4. We begin with an explicit formula for ord2iq which can be derived from ([11], Proposition 1). For completeness, a rigorous proof is provided.Lemma 5.
Letq be an odd prime power, and let β be the positive integer such that 2β‖q2−1. Let i be a positive integer. If q≡1mod4, then(12)ord2iq=1,if1≤i≤β−1,2i−β+1,ifi≥β.Proof.
Assume thatq≡1mod4. Then, 2β−1‖q−1 which implies that ord2iq=1, for all 1≤i≤β−1. Next, assume that i≥β. Since q≡1mod4, it follows that q2j≡1mod4 for all j≥0. Hence, 2‖q2j+1 for all j≥0. Since q2i−β−1q2i−β+1=q2i−β+1−1=q−1∏j=0i−βq2j+1, it can be concluded that 2i‖q2β−i+1−1 and 2i∤q2t−1, for all t≤β+i. As desired, we have ord2iq=2i−β+1 for all i≥β.Proposition 2.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ≥0 be the integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β||q2−1. Then, the following statements hold:
(i)
Ifλ=0, then(a)
Clq,2i+1n′a≠Clq,2i+1n′a+2in′ for all odd integers a and integers 1≤i≤β−2(b)
Clq,2i+1n′a=Clq,2i+1n′a+2in′=Clq,2in′a∪Clq,2in′a+2in′ for all odd integers a and integers i≥β−1(ii)
Ifλ>0, then(a)
Clq,2λ+β−1n′1≠Clq,2iλ+β−1n′1+2λ+β−2n′(b)
Clq,2i+1n′a=Clq,2i+1n′a+2in′=Clq,2in′a∪Clq,2in′a+2in′ for odd integers a and integers i≥λ+β−1Proof.
First, we observe thatβ≥3, 2‖q+1 and 2β−1‖q−1. Using Lemma 5 and arguments similar to those in the proof of Proposition 1, the following key results can be deduced:(1)
Ifλ=0, then ordΘ2i+1n′aq=ordΘ2in′aq, for all odd integers a and integers 1≤i≤β−2, and ord2i+1n′q=2ord2in′q, for all integers i≥β−1.(2)
Ifλ>0, then ord2λ+β−1n′q=ord2λ+β−2n′q and ord2i+1n′q=2ord2in′q, for all integers i≥λ+β−1.
The complete proof can be obtained using arguments similar to those in Proposition1, while the above discussion and Lemma 5 is applied instead of Lemma 4.


## 4. Factorization ofxn+1 over Finite Fields

In this section, the factorization ofx2in′+1 over Fq is established. First, we prove that there exists a positive integer k such that the number of monic irreducible factors of x2in′+1 over Fq becomes a constant for all integers i≥k. In the case where ordn′q is odd, a complete recursive factorization of x2in′+1 over Fq is given together with a recursive formula for the number of its monic irreducible factors for all positive integers i in Section 4.1. In the case where ordn′q is even, a recursive factorization of x2in′+1 over Fq is given as well as a recursive formula for the number of its monic irreducible factors for all integers i≥k in Section 4.2.


### 4.1. Recursive Factorization ofxn+1 over Fq with Odd ordn′q

In this section, we establish a complete recursive factorization ofx2in′+1 over Fq in the case where ordn′q is odd. Subsequently, a formula for the number of monic irreducible factors of x2in′+1 over Fq is given recursively on i.


#### 4.1.1.q≡3mod4

We begin with useful relations betweenq-cyclotomic cosets and their induced polynomials for the case q≡3mod4.Lemma 6.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Let i be a positive integer, and let a be an odd integer. Then, one of the following statements holds:(i)
Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of degree Clq,2in′a, for all 2≤i≤β−1.(ii)
For eachi=1 or i≥β, if fx is induced by Clq,2in′a, then Clq,2in′a induces fx2.Proof.
To prove (i), assume that2≤i≤β−1. By Proposition 1 ((a) in (i)), we have Clq,2i+1n′a≠Clq,2i+1n′a+2in′. From Lemma 3, it follows that Clq,2i+1n′a=Clq,2i+1n′a+2in′ which equals to Clq,2in′a by the proof of Proposition 1 ((a) in (i)). Hence, Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of degree Clq,2in′a.
To prove (ii), assume thati=1 or i≥β. Assume that fx is induced by Clq,2in′a. Let α be a 2i+1n′th root of unity. Then, α2 is a 2in′ th root of unity and fx=∏j∈Clq,2in′ax−α2j. From Proposition 1 ((b) in (i)), we have Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′. It follows that(13)∏j∈Clq,2i+1n′ax−αj=∏j∈Clq,2in′a∪Clq,2in′a+2in′x−αj,=∏j∈Clq,2in′ax−αj×∏j∈Clq,2in′a+2in′x−αj=∏j∈Clq,2in′ax−αjx−αj+2in′=∏j∈Clq,2in′ax−αjx+αj=∏j∈Clq,2in′ax−α2j=fx2.
Therefore,Clq,2i+1n′a induces fx2 as desired.The next corollary can be deduced directly from the above lemma.Corollary 1.
Assume the notations as in Lemma6 with i≥β. If fx is induced by Clq,2in′a, then fx2j is irreducible for all j≥β−i.In order to simplify the notations in the following theorem, letα and γ be 2in′th and 2i+1n′th roots of unity, respectively. For each a∈SOq2in′, let(14)fax=∏j∈Clq,2in′ax−αjandgjx=∏j∈Clq,2i+1n′ax−γj.be the irreducible polynomials induced by Clq,2in′a and Clq,2i+1n′a, respectively. Using these notations, a recursive factorization of x2in′+1 is given as follows.Theorem 1.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifi=0, then(15)x2in′+1=xn′+1=∏a∈SOq2n′fax.(ii)
Ifi≥1, then(16)x2in′+1=∏a∈SOq2in′fax2,ifi=1ori≥β,∏a∈SOq2in′gaxga+2in′x,if2≤i≤β−1,where fax and gax are given in (14).
In this case, we have(17)x2β−1+in′+1=∏a∈SOq2βn′fax2i,for all i≥0.Proof.
From (5), we note that(18)x2in′+1=∏a∈SOq2i+1n′fax.
The first statement is the special case wherei=0. From Proposition 1 (i), it can be deduced that(19)SOq2i+1n′=SOq2in′,ifi=1ori≥β,SOq2in′∪SOq2in′+2in′,if2≤i≤β−1,where the union is disjoint. The results therefore follow from Lemma 6.A recursive formula for the number of monic irreducible factors ofx2in′+1 over Fq follows immediately from the theorem.Corollary 2.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let i≥0 be an integer, and let β be the positive integer such that 2β‖q2−1. Then,(20)Nqn′=∑d|n′ϕ2dord2dq,(21)Nq2in′=Nqn′ifi=1,2Nq2i−1n′=2i−1Nqn′if2≤i≤β−1,Nq2β−2n′=2β−2Nqn′ifi≥β.Proof.
Equation (20) is a special case of (6). Equation (21) follows immediately from Theorem 1.


#### 4.1.2.q≡1mod4

Here, we focus onq≡1mod4. First, some useful relations between the q-cyclotomic coset Clq,2i+1n′a and its induced polynomial are established.Lemma 7.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Let i be a positive integer, and let a be an odd integer. Then, one of the following statements holds:
(i)
Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of the same degree for all 1≤i≤β−2(ii)
For eachi≥β−1, if fx is induced by Clq,2in′a, then Clq,2i+1n′a induces fx2Proof.
The proof can be obtained using arguments similar to those in the proof of Lemma6, while Proposition 2 (i) is applied instead of Proposition 1 (i).Corollary 3.
Assume the notations as in Lemma7 with i≥β−1. If fx is induced by Clq,2in′a, then fx2j is irreducible for all j≥β−i−1.The factorization ofx2in′+1 is given in the following theorem.Theorem 2.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifi=0, then(22)x2in′+1=xn′+1=∏a∈SOq2n′fax.(ii)
Ifi≥1, then(23)x2in′+1=∏a∈SOq2in′gaxga+2in′x,if1≤i≤β−2,∏a∈SOq2in′fax2,ifi≥β−1,where fax and gax are given in (14).
In this case, we have(24)x2β−2+in′+1=∏a∈SOq2β−1n′fax2i,for all i≥0.Proof.
The proof can be obtained using arguments similar to those in the proof of Theorem1, while Proposition 2 (i) and Lemma 7 are applied instead of Proposition 1 (i) and Lemma 6.From the theorem, the enumeration of monic irreducible factors ofx2in′−1 over Fq can be concluded in the following corollary.Corollary 4.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let i≥0 be an integer, and let β be the positive integer such that 2β‖q2−1. Then,(25)Nqn′=∑d|n′ϕ2dord2dq,(26)Nq2in′=2Nq2i−1n′=2iNqn′,if1≤i≤β−2,Nq2β−2n′=2β−2Nqn′,ifi≥β−1.Proof.
Equation (25) is given in (6). Equation (26) follows immediately from Theorem 2.


### 4.2. Factorization ofxn+1 over Fq with Even ordn′q

In this section, we focus on the case whereordn′q is even, i.e., 2λ‖ordn′q for some positive integer λ. The results are not strong as the previous section. Precisely, a recursive factorization of x2in′+1 over Fq is given only for all sufficiently large positive integers i.In general, the factorization ofx2in′+1 over Fq is given in (3). For i≥λ+β−1, a simpler recursive method for the factorization is given in the following theorem.Theorem 3.
Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ be the positive integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β‖q2−1. Then,(27)x2λ+β−1+jn′+1=∏a∈SOq2λ+βn′fax2j,for all j≥0.Proof.
The proof can be obtained using arguments similar to those in the proof of Theorem1, while Proposition 2 (ii) and Proposition 1 (ii) are applied instead of Proposition 2 (i) and Proposition 1 (i).Corollary5 follows immediately.Corollary 5.
Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ be the positive integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β‖q2−1. Then,(28)Nq2in′=Nq2λ+β−2n′,for all i≥λ+β−1.


### 4.3. Algorithm and Examples

In this section, the above results are summarized as an algorithm for factorizingx2in′+1 over Fq. Some illustrative examples are given as well. An algorithm for the factorization of x2in′+1 over Fq is given in Algorithm 1.Algorithm 1:Algorithm for the factorization of x2in′+1 over Fq.
Input: odd prime powerq, odd integer n′ with gcdq,n′=1, and integer i≥0.(1)
Compute the positive integerβ such that 2β‖q2−1.(2)
Computeordn′q and the integer λ such that 2λ‖ordn′q.(3)
Consider the following cases:(I)
λ=0.(i)
q≡1mod4.(a)
i=0. Compute x2in′+1=xn′+1=∏a∈SOq2n′fax.(b)
1≤i≤β−2. Computex2in′+1=∏a∈SOq2in′gaxga+2in′x,andSOq2i+1n′=SOq2in′∪SOq2in′+2in′.(c)
i≥β−1. Computex2in′+1=∏a∈SOq2β−1n′fax2i−β+2.(ii)
q≡3mod4.(a)
0≤i≤1. Compute x2in′+1=∏a∈SOq2n′faxi.(b)
2≤i≤β−1. Computex2in′+1=∏a∈SOq2in′gaxga+2in′x,andSOq2i+1n′=SOq2in′∪SOq2in′+2in′.(c)
i≥β. Computex2in′+1=∏a∈SOq2βn′fax2i−β+1.(II)
λ≥1.(i)
0≤i≤λ+β−2. Compute x2in′+1 directly using (3)(ii)
i≥λ+β−1. Computex2in′+1=∏a∈SOq2λ+βn′fax2i−λ−β+1.Note thatfax and gax are given in (14).For the enumeration of monic irreducible factors ofx2in′+1 over Fq, it can be calculated using (6). With more information on n′, i, and q, the formula can be simplified using Corollaries 2, 4, and 5 of the form(29)Nq2in′=2iNqn′,ifλ=0,1≤i≤β−2andq≡1mod4,2β−2Nqn′,ifλ=0,i≥β−1andq≡1mod4,Nqn′,ifλ=0,i=1andq≡3mod4,2i−1Nqn′,ifλ=0,2≤i≤β−1andq≡3mod4,2β−2Nqn′,ifλ=0,i≥βandq≡3mod4,Nq2λ+β−2n′,ifλ≥1andi≥λ+β−1,where λ is the positive integer such that 2λ‖ordn′q, β is the positive integer such that 2β‖q2−1, and(30)Nqn′=∑d|n′ϕ2dord2dq.From (29), the number Nq2in′ of monic irreducible factors of x2in′+1 over Fq becomes a constant independent of i for all i≥λ+β−1 if λ=0 and q≡3mod4 and for all i≥λ+β−2 otherwise. Illustrative examples for the number Nq2in′ of monic irreducible factors of x2in′+1 over Fq with odd ordn′q and even ordn′q are given in Tables 1 and 2, respectively.Table 1
Nq2in′ of monic irreducible factors of x2in′+1 over Fq with odd ordn′q.
qn′ordn′qλβiNq2in′311030111≥223115030313≥263133030515≥2105110301≥1251150303≥1671104011122≥3473104031326≥312793040515210≥320911040112≥24973040316≥2129115040316≥21291330405110≥220Table 2
Nq2in′ of monic irreducible factors of x2in′+1 over Fq with even ordn′q.
qn′ordn′qλβiNq2in′35423021326≥310376130213≥26532130214≥26576130214≥26596130316≥2105134230418214≥32675424021326312≥4207111014021326≥3127131224021326312≥4207154240619218336≥460952140316212≥320In Table1, the results for q∈3,7 and q∈5,9 are obtained from Corollaries 2 and 4, respectively.In Table2, the last row of each n′ is obtained from Corollary 5. Otherwise, it is computed using (6).


## 4.1. Recursive Factorization ofxn+1 over Fq with Odd ordn′q

In this section, we establish a complete recursive factorization ofx2in′+1 over Fq in the case where ordn′q is odd. Subsequently, a formula for the number of monic irreducible factors of x2in′+1 over Fq is given recursively on i.


### 4.1.1.q≡3mod4

We begin with useful relations betweenq-cyclotomic cosets and their induced polynomials for the case q≡3mod4.Lemma 6.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Let i be a positive integer, and let a be an odd integer. Then, one of the following statements holds:(i)
Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of degree Clq,2in′a, for all 2≤i≤β−1.(ii)
For eachi=1 or i≥β, if fx is induced by Clq,2in′a, then Clq,2in′a induces fx2.Proof.
To prove (i), assume that2≤i≤β−1. By Proposition 1 ((a) in (i)), we have Clq,2i+1n′a≠Clq,2i+1n′a+2in′. From Lemma 3, it follows that Clq,2i+1n′a=Clq,2i+1n′a+2in′ which equals to Clq,2in′a by the proof of Proposition 1 ((a) in (i)). Hence, Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of degree Clq,2in′a.
To prove (ii), assume thati=1 or i≥β. Assume that fx is induced by Clq,2in′a. Let α be a 2i+1n′th root of unity. Then, α2 is a 2in′ th root of unity and fx=∏j∈Clq,2in′ax−α2j. From Proposition 1 ((b) in (i)), we have Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′. It follows that(13)∏j∈Clq,2i+1n′ax−αj=∏j∈Clq,2in′a∪Clq,2in′a+2in′x−αj,=∏j∈Clq,2in′ax−αj×∏j∈Clq,2in′a+2in′x−αj=∏j∈Clq,2in′ax−αjx−αj+2in′=∏j∈Clq,2in′ax−αjx+αj=∏j∈Clq,2in′ax−α2j=fx2.
Therefore,Clq,2i+1n′a induces fx2 as desired.The next corollary can be deduced directly from the above lemma.Corollary 1.
Assume the notations as in Lemma6 with i≥β. If fx is induced by Clq,2in′a, then fx2j is irreducible for all j≥β−i.In order to simplify the notations in the following theorem, letα and γ be 2in′th and 2i+1n′th roots of unity, respectively. For each a∈SOq2in′, let(14)fax=∏j∈Clq,2in′ax−αjandgjx=∏j∈Clq,2i+1n′ax−γj.be the irreducible polynomials induced by Clq,2in′a and Clq,2i+1n′a, respectively. Using these notations, a recursive factorization of x2in′+1 is given as follows.Theorem 1.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifi=0, then(15)x2in′+1=xn′+1=∏a∈SOq2n′fax.(ii)
Ifi≥1, then(16)x2in′+1=∏a∈SOq2in′fax2,ifi=1ori≥β,∏a∈SOq2in′gaxga+2in′x,if2≤i≤β−1,where fax and gax are given in (14).
In this case, we have(17)x2β−1+in′+1=∏a∈SOq2βn′fax2i,for all i≥0.Proof.
From (5), we note that(18)x2in′+1=∏a∈SOq2i+1n′fax.
The first statement is the special case wherei=0. From Proposition 1 (i), it can be deduced that(19)SOq2i+1n′=SOq2in′,ifi=1ori≥β,SOq2in′∪SOq2in′+2in′,if2≤i≤β−1,where the union is disjoint. The results therefore follow from Lemma 6.A recursive formula for the number of monic irreducible factors ofx2in′+1 over Fq follows immediately from the theorem.Corollary 2.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let i≥0 be an integer, and let β be the positive integer such that 2β‖q2−1. Then,(20)Nqn′=∑d|n′ϕ2dord2dq,(21)Nq2in′=Nqn′ifi=1,2Nq2i−1n′=2i−1Nqn′if2≤i≤β−1,Nq2β−2n′=2β−2Nqn′ifi≥β.Proof.
Equation (20) is a special case of (6). Equation (21) follows immediately from Theorem 1.


### 4.1.2.q≡1mod4

Here, we focus onq≡1mod4. First, some useful relations between the q-cyclotomic coset Clq,2i+1n′a and its induced polynomial are established.Lemma 7.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Let i be a positive integer, and let a be an odd integer. Then, one of the following statements holds:
(i)
Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of the same degree for all 1≤i≤β−2(ii)
For eachi≥β−1, if fx is induced by Clq,2in′a, then Clq,2i+1n′a induces fx2Proof.
The proof can be obtained using arguments similar to those in the proof of Lemma6, while Proposition 2 (i) is applied instead of Proposition 1 (i).Corollary 3.
Assume the notations as in Lemma7 with i≥β−1. If fx is induced by Clq,2in′a, then fx2j is irreducible for all j≥β−i−1.The factorization ofx2in′+1 is given in the following theorem.Theorem 2.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifi=0, then(22)x2in′+1=xn′+1=∏a∈SOq2n′fax.(ii)
Ifi≥1, then(23)x2in′+1=∏a∈SOq2in′gaxga+2in′x,if1≤i≤β−2,∏a∈SOq2in′fax2,ifi≥β−1,where fax and gax are given in (14).
In this case, we have(24)x2β−2+in′+1=∏a∈SOq2β−1n′fax2i,for all i≥0.Proof.
The proof can be obtained using arguments similar to those in the proof of Theorem1, while Proposition 2 (i) and Lemma 7 are applied instead of Proposition 1 (i) and Lemma 6.From the theorem, the enumeration of monic irreducible factors ofx2in′−1 over Fq can be concluded in the following corollary.Corollary 4.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let i≥0 be an integer, and let β be the positive integer such that 2β‖q2−1. Then,(25)Nqn′=∑d|n′ϕ2dord2dq,(26)Nq2in′=2Nq2i−1n′=2iNqn′,if1≤i≤β−2,Nq2β−2n′=2β−2Nqn′,ifi≥β−1.Proof.
Equation (25) is given in (6). Equation (26) follows immediately from Theorem 2.


## 4.1.1.q≡3mod4

We begin with useful relations betweenq-cyclotomic cosets and their induced polynomials for the case q≡3mod4.Lemma 6.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Let i be a positive integer, and let a be an odd integer. Then, one of the following statements holds:(i)
Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of degree Clq,2in′a, for all 2≤i≤β−1.(ii)
For eachi=1 or i≥β, if fx is induced by Clq,2in′a, then Clq,2in′a induces fx2.Proof.
To prove (i), assume that2≤i≤β−1. By Proposition 1 ((a) in (i)), we have Clq,2i+1n′a≠Clq,2i+1n′a+2in′. From Lemma 3, it follows that Clq,2i+1n′a=Clq,2i+1n′a+2in′ which equals to Clq,2in′a by the proof of Proposition 1 ((a) in (i)). Hence, Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of degree Clq,2in′a.
To prove (ii), assume thati=1 or i≥β. Assume that fx is induced by Clq,2in′a. Let α be a 2i+1n′th root of unity. Then, α2 is a 2in′ th root of unity and fx=∏j∈Clq,2in′ax−α2j. From Proposition 1 ((b) in (i)), we have Clq,2i+1n′a=Clq,2in′a∪Clq,2in′a+2in′. It follows that(13)∏j∈Clq,2i+1n′ax−αj=∏j∈Clq,2in′a∪Clq,2in′a+2in′x−αj,=∏j∈Clq,2in′ax−αj×∏j∈Clq,2in′a+2in′x−αj=∏j∈Clq,2in′ax−αjx−αj+2in′=∏j∈Clq,2in′ax−αjx+αj=∏j∈Clq,2in′ax−α2j=fx2.
Therefore,Clq,2i+1n′a induces fx2 as desired.The next corollary can be deduced directly from the above lemma.Corollary 1.
Assume the notations as in Lemma6 with i≥β. If fx is induced by Clq,2in′a, then fx2j is irreducible for all j≥β−i.In order to simplify the notations in the following theorem, letα and γ be 2in′th and 2i+1n′th roots of unity, respectively. For each a∈SOq2in′, let(14)fax=∏j∈Clq,2in′ax−αjandgjx=∏j∈Clq,2i+1n′ax−γj.be the irreducible polynomials induced by Clq,2in′a and Clq,2i+1n′a, respectively. Using these notations, a recursive factorization of x2in′+1 is given as follows.Theorem 1.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifi=0, then(15)x2in′+1=xn′+1=∏a∈SOq2n′fax.(ii)
Ifi≥1, then(16)x2in′+1=∏a∈SOq2in′fax2,ifi=1ori≥β,∏a∈SOq2in′gaxga+2in′x,if2≤i≤β−1,where fax and gax are given in (14).
In this case, we have(17)x2β−1+in′+1=∏a∈SOq2βn′fax2i,for all i≥0.Proof.
From (5), we note that(18)x2in′+1=∏a∈SOq2i+1n′fax.
The first statement is the special case wherei=0. From Proposition 1 (i), it can be deduced that(19)SOq2i+1n′=SOq2in′,ifi=1ori≥β,SOq2in′∪SOq2in′+2in′,if2≤i≤β−1,where the union is disjoint. The results therefore follow from Lemma 6.A recursive formula for the number of monic irreducible factors ofx2in′+1 over Fq follows immediately from the theorem.Corollary 2.
Letq be a prime power such that q≡3mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let i≥0 be an integer, and let β be the positive integer such that 2β‖q2−1. Then,(20)Nqn′=∑d|n′ϕ2dord2dq,(21)Nq2in′=Nqn′ifi=1,2Nq2i−1n′=2i−1Nqn′if2≤i≤β−1,Nq2β−2n′=2β−2Nqn′ifi≥β.Proof.
Equation (20) is a special case of (6). Equation (21) follows immediately from Theorem 1.


## 4.1.2.q≡1mod4

Here, we focus onq≡1mod4. First, some useful relations between the q-cyclotomic coset Clq,2i+1n′a and its induced polynomial are established.Lemma 7.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Let i be a positive integer, and let a be an odd integer. Then, one of the following statements holds:
(i)
Clq,2i+1n′a and Clq,2i+1n′a+2in′ induce distinct monic irreducible polynomials of the same degree for all 1≤i≤β−2(ii)
For eachi≥β−1, if fx is induced by Clq,2in′a, then Clq,2i+1n′a induces fx2Proof.
The proof can be obtained using arguments similar to those in the proof of Lemma6, while Proposition 2 (i) is applied instead of Proposition 1 (i).Corollary 3.
Assume the notations as in Lemma7 with i≥β−1. If fx is induced by Clq,2in′a, then fx2j is irreducible for all j≥β−i−1.The factorization ofx2in′+1 is given in the following theorem.Theorem 2.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let β be the positive integer such that 2β‖q2−1. Then, the following statements hold:
(i)
Ifi=0, then(22)x2in′+1=xn′+1=∏a∈SOq2n′fax.(ii)
Ifi≥1, then(23)x2in′+1=∏a∈SOq2in′gaxga+2in′x,if1≤i≤β−2,∏a∈SOq2in′fax2,ifi≥β−1,where fax and gax are given in (14).
In this case, we have(24)x2β−2+in′+1=∏a∈SOq2β−1n′fax2i,for all i≥0.Proof.
The proof can be obtained using arguments similar to those in the proof of Theorem1, while Proposition 2 (i) and Lemma 7 are applied instead of Proposition 1 (i) and Lemma 6.From the theorem, the enumeration of monic irreducible factors ofx2in′−1 over Fq can be concluded in the following corollary.Corollary 4.
Letq be a prime power such that q≡1mod4, and let n′ be an odd positive integer such that gcdq,n′=1 and ordn′q is odd. Let i≥0 be an integer, and let β be the positive integer such that 2β‖q2−1. Then,(25)Nqn′=∑d|n′ϕ2dord2dq,(26)Nq2in′=2Nq2i−1n′=2iNqn′,if1≤i≤β−2,Nq2β−2n′=2β−2Nqn′,ifi≥β−1.Proof.
Equation (25) is given in (6). Equation (26) follows immediately from Theorem 2.


## 4.2. Factorization ofxn+1 over Fq with Even ordn′q

In this section, we focus on the case whereordn′q is even, i.e., 2λ‖ordn′q for some positive integer λ. The results are not strong as the previous section. Precisely, a recursive factorization of x2in′+1 over Fq is given only for all sufficiently large positive integers i.In general, the factorization ofx2in′+1 over Fq is given in (3). For i≥λ+β−1, a simpler recursive method for the factorization is given in the following theorem.Theorem 3.
Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ be the positive integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β‖q2−1. Then,(27)x2λ+β−1+jn′+1=∏a∈SOq2λ+βn′fax2j,for all j≥0.Proof.
The proof can be obtained using arguments similar to those in the proof of Theorem1, while Proposition 2 (ii) and Proposition 1 (ii) are applied instead of Proposition 2 (i) and Proposition 1 (i).Corollary5 follows immediately.Corollary 5.
Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ be the positive integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β‖q2−1. Then,(28)Nq2in′=Nq2λ+β−2n′,for all i≥λ+β−1.


## 4.3. Algorithm and Examples

In this section, the above results are summarized as an algorithm for factorizingx2in′+1 over Fq. Some illustrative examples are given as well. An algorithm for the factorization of x2in′+1 over Fq is given in Algorithm 1.Algorithm 1:Algorithm for the factorization of x2in′+1 over Fq.
Input: odd prime powerq, odd integer n′ with gcdq,n′=1, and integer i≥0.(1)
Compute the positive integerβ such that 2β‖q2−1.(2)
Computeordn′q and the integer λ such that 2λ‖ordn′q.(3)
Consider the following cases:(I)
λ=0.(i)
q≡1mod4.(a)
i=0. Compute x2in′+1=xn′+1=∏a∈SOq2n′fax.(b)
1≤i≤β−2. Computex2in′+1=∏a∈SOq2in′gaxga+2in′x,andSOq2i+1n′=SOq2in′∪SOq2in′+2in′.(c)
i≥β−1. Computex2in′+1=∏a∈SOq2β−1n′fax2i−β+2.(ii)
q≡3mod4.(a)
0≤i≤1. Compute x2in′+1=∏a∈SOq2n′faxi.(b)
2≤i≤β−1. Computex2in′+1=∏a∈SOq2in′gaxga+2in′x,andSOq2i+1n′=SOq2in′∪SOq2in′+2in′.(c)
i≥β. Computex2in′+1=∏a∈SOq2βn′fax2i−β+1.(II)
λ≥1.(i)
0≤i≤λ+β−2. Compute x2in′+1 directly using (3)(ii)
i≥λ+β−1. Computex2in′+1=∏a∈SOq2λ+βn′fax2i−λ−β+1.Note thatfax and gax are given in (14).For the enumeration of monic irreducible factors ofx2in′+1 over Fq, it can be calculated using (6). With more information on n′, i, and q, the formula can be simplified using Corollaries 2, 4, and 5 of the form(29)Nq2in′=2iNqn′,ifλ=0,1≤i≤β−2andq≡1mod4,2β−2Nqn′,ifλ=0,i≥β−1andq≡1mod4,Nqn′,ifλ=0,i=1andq≡3mod4,2i−1Nqn′,ifλ=0,2≤i≤β−1andq≡3mod4,2β−2Nqn′,ifλ=0,i≥βandq≡3mod4,Nq2λ+β−2n′,ifλ≥1andi≥λ+β−1,where λ is the positive integer such that 2λ‖ordn′q, β is the positive integer such that 2β‖q2−1, and(30)Nqn′=∑d|n′ϕ2dord2dq.From (29), the number Nq2in′ of monic irreducible factors of x2in′+1 over Fq becomes a constant independent of i for all i≥λ+β−1 if λ=0 and q≡3mod4 and for all i≥λ+β−2 otherwise. Illustrative examples for the number Nq2in′ of monic irreducible factors of x2in′+1 over Fq with odd ordn′q and even ordn′q are given in Tables 1 and 2, respectively.Table 1
Nq2in′ of monic irreducible factors of x2in′+1 over Fq with odd ordn′q.
qn′ordn′qλβiNq2in′311030111≥223115030313≥263133030515≥2105110301≥1251150303≥1671104011122≥3473104031326≥312793040515210≥320911040112≥24973040316≥2129115040316≥21291330405110≥220Table 2
Nq2in′ of monic irreducible factors of x2in′+1 over Fq with even ordn′q.
qn′ordn′qλβiNq2in′35423021326≥310376130213≥26532130214≥26576130214≥26596130316≥2105134230418214≥32675424021326312≥4207111014021326≥3127131224021326312≥4207154240619218336≥460952140316212≥320In Table1, the results for q∈3,7 and q∈5,9 are obtained from Corollaries 2 and 4, respectively.In Table2, the last row of each n′ is obtained from Corollary 5. Otherwise, it is computed using (6).


## 5. Applications

In this section, the factorization ofx2in′+1 over Fq obtained in Section 4 is applied in the study of negacyclic codes. Some known results are revisited in simpler forms.A linear code of lengthn over Fq is defined to be a subspace of the Fq-vector space Fqn. The dual of a linear code C of length n over Fq is defined to be(31)C⊥=v0,v1,…,vn−1∈Fqn|∑i=0n−1civi=0,for allc0,c1,…,cn−1∈C.A linear codeC is said to be self-dual if C=C⊥ and it is said to be complementary dual if C∩C⊥=0.A linear codeC of length n over Fq is said to be negacyclic if it is closed under the negacyclic shift. Precisely, −cn−1,c0,c1,…,cn−2∈C, for every c0,c1,…,cn−2,cn−1∈C. Under the map π:Fqn⟶Fqx/xn+1 defined by(32)c0,c1,…,cn−2,cn−1↦c0+c1x+c2x2+⋯+cn−1xn−1,it is well known (see [4]) that a linear code C of length n over Fq is negacyclic if and only if πC is an ideal in the principal ideal ring Fqx/xn+1. The map π induces a one-to-one correspondence between negacyclic codes of length n over Fq and ideas in Fqx/xn+1. In this case, πC is uniquely generated by the monic divisor of xn+1 of minimal degree in πC. Such polynomial is called the generator polynomial of C.Letq be an odd prime power, and let n′ be an odd positive integer such that gcdq,n′=1. Let λ be the positive integer such that 2λ‖ordn′q, and let β be the positive integer such that 2β‖q2−1. Let(33)k=λ+β−1,ifλ=0andq≡3mod4,λ+β−2,otherwise.In general, negacyclic codes have been studied in [3, 4, 10]. Here, we focus on negacyclic codes of length n=ps2in′ with i≥k, where p is the characteristic of Fq. The construction and enumeration of such negacyclic codes are simplified using the results from Section 4.From (5), we have(34)x2kn′+1=∏j=1Nq2kn′rjx.Based on Theorems1–3, it follows that(35)xps2in′+1=x2in′+1ps=∏j=1Nq2kn′rjx2i−kps,and rjx2i−k is irreducible for all i≥k.The following characterization and enumeration of negacyclic codes of lengthn=ps2in′ with i≥k are straightforward. The proof is committed.Theorem 4.
Assume the notations above. The following statements hold:
(1)
The mapT:Fqx/xps2kn′+1⟶Fqx/xps2in′+1, defined by fx↦fx2i−k, is a ring isomorphism for all integers i≥k(2)
For each integeri≥k, gx is the generator polynomial of a negacyclic code of length ps2kn′ over Fq if and only if gx2i−kis the generator polynomial of a negacyclic code of length ps2in′ over Fq(3)
The number of negacyclic codes of lengthps2in′ over Fq is ps+1Nq2kn′, for all i≥kFrom the theorem, all negacyclic codes of lengthps2in′ over Fq with i≥k can be determined using the negacyclic codes of length ps2kn′ over Fq.



---

*Source: 6626422-2021-01-07.xml*