# Cyclic Codes via the General Two-Prime Generalized Cyclotomic Sequence of Order Two

Authors: Xia Zhou
Journal: Journal of Mathematics
 (2020)

---

## Abstract

Suppose thatp and q are two distinct odd prime numbers with n=pq. In this paper, the uniform representation of general two-prime generalized cyclotomy with order two over ℤn was demonstrated. Based on this general generalized cyclotomy, a type of binary sequences defined over Fl was presented and their minimal polynomials and linear complexities were derived, where l=rs with a prime number r and gcdl,n=1. The results have indicated that the linear complexities of these sequences are high without any special requirements on the prime numbers. Furthermore, we employed these sequences to obtain a few cyclic codes over Fl with length n and developed the lower bounds of the minimum distances of many cyclic codes. It is important to stress that some cyclic codes in this paper are optimal.


---

## Body

## 1. Introduction

Throughout this paper, assume thatl is a power of a prime number r. A linear [n,k,d] code C over Fl is defined as a k-dimensional subspace of Fln with minimum distance d, where Fl is a finite field with order l and Fln denotes the n-dimensional linear space over Fl. If each c0,c1,…,cn−1∈C if and only if cn−1,c0,…,cn−2∈C, then C is named as a cyclic code. Let gcdl,n=1 and the ring R=Flx/xn−1. Hence, there is a one-to-one correspondence between a linear code over Fl with length n and a real subset of R. If an ideal C is not trivial, there is a monic polynomial gx over Fl, satisfying C=gx, where gx is unique and gx|xn−1. Then, gx and hx=xn−1/gx are called to be the generator polynomial and parity-check polynomial of C, respectively. Please refer to [1] for more details on cyclic codes.Letsn=sii=0n−1 be a sequence with period n over Fl and Sx=∑i=0n−1sixi∈Flx. At present, the methods of constructing cyclic codes are substantial. One of the important methods is to employ(1)hx=xn−1gcdxn−1,Sx,where hx is named as the generator polynomial of sn.As is known to all, there are a good deal of results on cyclic codes in a series of papers [2–11]. Let p and q be two distinct prime numbers. In order to search for more residue difference sets, Whiteman [12] introduced a generalized cyclotomy regarding pq. In 1997, Ding [13] introduced the Whiteman’s generalized cyclotomic sequence (WGCS) and studied its coding properties in [6, 7, 9, 11]. To be more specific, Ding [6] constructed three families of cyclic codes, some of which are optimal with regard to the minimum distance. In addition, Ding [7] presented many cyclic codes and their lower bounds about the minimum weight. Furthermore, based on a number of WGCSs of order 4 and order 6, some classes of cyclic codes were produced by Sun et al. [9] and Kewat and Kumari [11], respectively, whose lower bounds on the nonzero minimum weight were also provided.As an important measure of the quality of a sequence, its linear complexity is defined as the length of the shortest linear feedback shift register which can produce this sequence. Nowadays, pseudorandom sequences with higher linear complexity are widely used in communication systems and cryptography.The main contributions of this article are as follows: firstly, we proved that there are only three classes of generalized cyclotomies with order two overℤpq, see Lemmas 4 and 5. Specifically, the generalized cyclotomies with order two in [12] and in [14, 15] are special cases of the first class and the second class, respectively. In essence, the generalized cyclotomies with order two over ℤpq in [7, 16] are exactly the first type and the second type, respectively. Secondly, by means of this general generalized cyclotomy, we constructed a class of the general two-prime GCSs of order two (see Definition 2) with period n over Fl, where n=pq and gcdl,n=1, and computed their minimal polynomials and linear complexities. The result shows that their linear complexities are high. Compared with the previous constructions of sequences with high linear complexity, our construction not only includes the aforementioned constructions in [14, 15] as special cases but also gives more parameters with high linear complexity due to the free choice of p and q, see Remark 4. Particularly, if gcdp−1,q−1≠2, these sequences are new. Thirdly, we employed these sequences to produce some families of cyclic codes. The idea of constructing cyclic codes employing special sequences in this paper is enlightened by [7]. Let us say it again, more optimal cyclic codes with new parameters can be generated by our construction compared to the cyclic codes obtained by [7], see Remark 3 for details.


## 2. Preliminaries

### 2.1. Minimal Polynomial and Linear Complexity

Suppose that the sequencesn=s0s1,…,sn−1, where si∈Fl and gcdl,n=1. The sequence sn is called to be linear feedback sequence, if there are L+1 constants c0=1,c1,…,cL∈Fl, satisfying(2)−c0si=c1si−1+c2si−2+⋯+cLsi−L,L≤i≤n−1.It is widely known that such a positive integerL for any finite sequence always exists. Here, the linear complexity of the sequence sn is defined as the minimal positive integer L and the feedback polynomial (or characteristic polynomial) of sn is defined as the polynomial cx=c0+c1x+⋯+cLxL. Furthermore, the minimal polynomial of sn is defined as the characteristic polynomial with the minimal length. It is demonstrated that the degree of its minimal polynomial of a periodic sequence is equal to its linear complexity. So far, there are many ways to calculate the minimal polynomial and linear complexity of a periodic sequence, one of which is stated as follows.Lemma 1 (see [1]).
Define(3)Sx=s0+s1x+⋯+sn−1xn−1∈Flx.For the sequencesn, its minimal polynomial mx is given by(4)mx=xn−1gcdxn−1,Sx,and its linear complexity Ls is determined by(5)Ls=n−deggcdxn−1,Sx.


### 2.2. Classical Cyclotomy with Order Two

Suppose thatf is an integer and q=2f+1 is an odd prime number. Then, there exists a finite field G=Fq with order q. Furthermore, one can always find an element g∈G such that G∗=g, where G∗=G\0 is the set of nonzero elements of G. Define the cyclotomic classes Diq with order two in G:(6)Diq=g2s+i:s=0,1,…,f−1,i=0,1.For given integersi and j, 0≤i,j≤1, the cyclotomic number i,j2q with order two regarding q is defined as(7)i,j2q=Diq+1∩Djq.Now, we will recall the properties of the classical cyclotomy with order two in [17] as follows.Lemma 2.
Suppose thatq=2f+1 is an odd prime number. Then,(8)0,02q=q−−1f4−1,0,12q=q−−1f4,1,02q=1,12q=q−2+−1f4.Letgcdq,l=1 and Ωl denote an algebraic closure of a finite field Fl. Define η0 and η1 as(9)η0=∑i∈D0qζqi,η1=∑i∈D1qζqi,where ζq∈Ωl is a q-th primitive root of unity; D0q and D1q are the cyclotomic classes with order two regarding q.When2∤l, ηii=0,1 over Ωl are identified by the following lemma.Lemma 3 (see [18]).
Let the symbols be the same as before. Then,(10)η0,η1=12−1±−1qq,where ÷ is the Legendre symbol.


### 2.3. The General Two-Prime Generalized Cyclotomic Sequence of Order Two

Suppose thatℤn is the residue class ring module n and ℤn∗=x:gcdx,n=1,1≤x≤n−1, where n is a positive integer. Let ϕn denote the Euler function. For gcda,n=1, if the multiplicative order of a modulo n is ϕn, then a is named as a primitive root modulo n.Definition 1.
A partitionW0,W1,…,Wh−1 of ℤn∗ is a family of sets, satisfying(11)Wi∩Wj=∅,for alli≠j,∪i=0h−1Wi=ℤn∗.
If there exist a subgroupW0 of ℤn∗ and g1,g2,…,gh−1 of ℤn∗, satisfying Wi=giW0, 1≤i≤h−1, then the Wi are called to be classical cyclotomic classes with order h if n is a prime number, and generalized cyclotomic classes with order h if n is a composite number. The (generalized) cyclotomic numbers with order h are defined as(12)i,j=Wi+1∩Wj,0≤i,j≤h−1.Lemma 4.
There are only three classes of generalized cyclotomies with order two regardingpq.Proof.
LetD0 be a fixed multiplicative subgroup of ℤn∗ with order ϕn/2. So, there exists α∈ℤn∗ such that ℤn∗=D0∪αD0. Obviously, α∉D0 and α2∈D0. Let(13)H=ℤn∗2=u2:u∈ℤn∗.
We next show thatH is a multiplicative subgroup of D0. It is straightforward to prove that H is a multiplicative subgroup of ℤn∗. We only need to show that H⊆D0. For any h∈H, there exists u∈ℤn∗ such that u2=h. If u∈D0, then h∈D0. If u∈αD0, then there exists v∈D0 such that u=αv and h=u2=α2v2∈D0. Hence, H is a multiplicative subgroup of D0 with order ϕn/4 and there exists β∈ℤn∗ such that D0=H∪βH. Finally, ℤn∗=H∪βH∪αH∪αβH. Therefore, W0=H∪βHorH∪αHorH∪αβH and the corresponding W1=αH∪αβHorβH∪αβHorαH∪βH. This finishes the proof of Lemma 4.
Suppose thatg is a common primitive root modulo p and q. Let x be a positive integer satisfying(14)x≡1modq,x≡gmodp.
Assume thate=p−1q−1/d, where d=gcdp−1,q−1. Therefore, the multiplicative group of ℤn is as follows [12]:(15)ℤn∗=gsxt:0≤s≤e−1;0≤t≤d−1.
According to Lemma4, we easily verify the assertion as the following.Lemma 5.
There are only three classes of generalized cyclotomies with order two overℤpq as follows. The first generalized cyclotomic classes Hin0≤i≤1 with order two are defined as(16)Hin=gsx2t+i:s=0,1,…,e−1;t=0,1,…,d2−1.The second generalized cyclotomic classesDin0≤i≤1 with order two are defined as(17)Din=g2s+ixt:s=0,1,…,e2−1;t=0,1,…,d−1,and the third generalized cyclotomic classes Win0≤i≤1 with order two are defined as(18)Win=g2s+igxt:s=0,1,…,e2−1;t=0,1,…,d−1,where the multiplications are operated modulo n.Remark 1.
By definition, whengcdp−1,q−1=2, the first generalized cyclotomy with order two over ℤpq is exactly Whiteman’s generalized cyclotomy [12]. In essence, it is in accord with the one introduced by Ding [7]. When gcdp−1,q−1=2, the second generalized cyclotomy with order two over ℤpq is identical to Ding-Helleseth’s generalized cyclotomy [2] in the case of v=pq. Furthermore, this cyclotomy is the same as the extended generalized cyclotomy with order two presented by Wang and Lin [16]. For fixed p, q, and x defined by (14), the third generalized cyclotomy is new. In [7], the linear complexity and minimal polynomial of generalized cyclotomic sequence with period n over Fl based on the first generalized cyclotomy of order two have been determined. In addition, cyclic codes defined by this sequence were analyzed. Here, we only study the second generalized cyclotomy with order two in this paper.
The generalized cyclotomic numbers with order two are defined by(19)i,j2n=Din+1∩Djn,0≤i,j≤1.
Define(20)P=p,2p,…,q−1p,Q=q,2q,…,p−1q,C1n=P∪D1n,C0n=0∪Q∪D0n.
Then,(21)ℤn=C0n∪C1n,C0n∩C1n=∅.Definition 2.
The two-prime general generalized cyclotomic sequences (GGCS) of order two are defined by(22)si=0,ifimodn∈C0n,1,ifimodn∈C1n,where 0 and 1 are the zero element and identity element, respectively, in Fl.Remark 2.
In [16], 0 and 1 in equation (22) are both in F2. Hence, our sequence and the sequence defined by Wang and Lin are totally different.


## 2.1. Minimal Polynomial and Linear Complexity

Suppose that the sequencesn=s0s1,…,sn−1, where si∈Fl and gcdl,n=1. The sequence sn is called to be linear feedback sequence, if there are L+1 constants c0=1,c1,…,cL∈Fl, satisfying(2)−c0si=c1si−1+c2si−2+⋯+cLsi−L,L≤i≤n−1.It is widely known that such a positive integerL for any finite sequence always exists. Here, the linear complexity of the sequence sn is defined as the minimal positive integer L and the feedback polynomial (or characteristic polynomial) of sn is defined as the polynomial cx=c0+c1x+⋯+cLxL. Furthermore, the minimal polynomial of sn is defined as the characteristic polynomial with the minimal length. It is demonstrated that the degree of its minimal polynomial of a periodic sequence is equal to its linear complexity. So far, there are many ways to calculate the minimal polynomial and linear complexity of a periodic sequence, one of which is stated as follows.Lemma 1 (see [1]).
Define(3)Sx=s0+s1x+⋯+sn−1xn−1∈Flx.For the sequencesn, its minimal polynomial mx is given by(4)mx=xn−1gcdxn−1,Sx,and its linear complexity Ls is determined by(5)Ls=n−deggcdxn−1,Sx.


## 2.2. Classical Cyclotomy with Order Two

Suppose thatf is an integer and q=2f+1 is an odd prime number. Then, there exists a finite field G=Fq with order q. Furthermore, one can always find an element g∈G such that G∗=g, where G∗=G\0 is the set of nonzero elements of G. Define the cyclotomic classes Diq with order two in G:(6)Diq=g2s+i:s=0,1,…,f−1,i=0,1.For given integersi and j, 0≤i,j≤1, the cyclotomic number i,j2q with order two regarding q is defined as(7)i,j2q=Diq+1∩Djq.Now, we will recall the properties of the classical cyclotomy with order two in [17] as follows.Lemma 2.
Suppose thatq=2f+1 is an odd prime number. Then,(8)0,02q=q−−1f4−1,0,12q=q−−1f4,1,02q=1,12q=q−2+−1f4.Letgcdq,l=1 and Ωl denote an algebraic closure of a finite field Fl. Define η0 and η1 as(9)η0=∑i∈D0qζqi,η1=∑i∈D1qζqi,where ζq∈Ωl is a q-th primitive root of unity; D0q and D1q are the cyclotomic classes with order two regarding q.When2∤l, ηii=0,1 over Ωl are identified by the following lemma.Lemma 3 (see [18]).
Let the symbols be the same as before. Then,(10)η0,η1=12−1±−1qq,where ÷ is the Legendre symbol.


## 2.3. The General Two-Prime Generalized Cyclotomic Sequence of Order Two

Suppose thatℤn is the residue class ring module n and ℤn∗=x:gcdx,n=1,1≤x≤n−1, where n is a positive integer. Let ϕn denote the Euler function. For gcda,n=1, if the multiplicative order of a modulo n is ϕn, then a is named as a primitive root modulo n.Definition 1.
A partitionW0,W1,…,Wh−1 of ℤn∗ is a family of sets, satisfying(11)Wi∩Wj=∅,for alli≠j,∪i=0h−1Wi=ℤn∗.
If there exist a subgroupW0 of ℤn∗ and g1,g2,…,gh−1 of ℤn∗, satisfying Wi=giW0, 1≤i≤h−1, then the Wi are called to be classical cyclotomic classes with order h if n is a prime number, and generalized cyclotomic classes with order h if n is a composite number. The (generalized) cyclotomic numbers with order h are defined as(12)i,j=Wi+1∩Wj,0≤i,j≤h−1.Lemma 4.
There are only three classes of generalized cyclotomies with order two regardingpq.Proof.
LetD0 be a fixed multiplicative subgroup of ℤn∗ with order ϕn/2. So, there exists α∈ℤn∗ such that ℤn∗=D0∪αD0. Obviously, α∉D0 and α2∈D0. Let(13)H=ℤn∗2=u2:u∈ℤn∗.
We next show thatH is a multiplicative subgroup of D0. It is straightforward to prove that H is a multiplicative subgroup of ℤn∗. We only need to show that H⊆D0. For any h∈H, there exists u∈ℤn∗ such that u2=h. If u∈D0, then h∈D0. If u∈αD0, then there exists v∈D0 such that u=αv and h=u2=α2v2∈D0. Hence, H is a multiplicative subgroup of D0 with order ϕn/4 and there exists β∈ℤn∗ such that D0=H∪βH. Finally, ℤn∗=H∪βH∪αH∪αβH. Therefore, W0=H∪βHorH∪αHorH∪αβH and the corresponding W1=αH∪αβHorβH∪αβHorαH∪βH. This finishes the proof of Lemma 4.
Suppose thatg is a common primitive root modulo p and q. Let x be a positive integer satisfying(14)x≡1modq,x≡gmodp.
Assume thate=p−1q−1/d, where d=gcdp−1,q−1. Therefore, the multiplicative group of ℤn is as follows [12]:(15)ℤn∗=gsxt:0≤s≤e−1;0≤t≤d−1.
According to Lemma4, we easily verify the assertion as the following.Lemma 5.
There are only three classes of generalized cyclotomies with order two overℤpq as follows. The first generalized cyclotomic classes Hin0≤i≤1 with order two are defined as(16)Hin=gsx2t+i:s=0,1,…,e−1;t=0,1,…,d2−1.The second generalized cyclotomic classesDin0≤i≤1 with order two are defined as(17)Din=g2s+ixt:s=0,1,…,e2−1;t=0,1,…,d−1,and the third generalized cyclotomic classes Win0≤i≤1 with order two are defined as(18)Win=g2s+igxt:s=0,1,…,e2−1;t=0,1,…,d−1,where the multiplications are operated modulo n.Remark 1.
By definition, whengcdp−1,q−1=2, the first generalized cyclotomy with order two over ℤpq is exactly Whiteman’s generalized cyclotomy [12]. In essence, it is in accord with the one introduced by Ding [7]. When gcdp−1,q−1=2, the second generalized cyclotomy with order two over ℤpq is identical to Ding-Helleseth’s generalized cyclotomy [2] in the case of v=pq. Furthermore, this cyclotomy is the same as the extended generalized cyclotomy with order two presented by Wang and Lin [16]. For fixed p, q, and x defined by (14), the third generalized cyclotomy is new. In [7], the linear complexity and minimal polynomial of generalized cyclotomic sequence with period n over Fl based on the first generalized cyclotomy of order two have been determined. In addition, cyclic codes defined by this sequence were analyzed. Here, we only study the second generalized cyclotomy with order two in this paper.
The generalized cyclotomic numbers with order two are defined by(19)i,j2n=Din+1∩Djn,0≤i,j≤1.
Define(20)P=p,2p,…,q−1p,Q=q,2q,…,p−1q,C1n=P∪D1n,C0n=0∪Q∪D0n.
Then,(21)ℤn=C0n∪C1n,C0n∩C1n=∅.Definition 2.
The two-prime general generalized cyclotomic sequences (GGCS) of order two are defined by(22)si=0,ifimodn∈C0n,1,ifimodn∈C1n,where 0 and 1 are the zero element and identity element, respectively, in Fl.Remark 2.
In [16], 0 and 1 in equation (22) are both in F2. Hence, our sequence and the sequence defined by Wang and Lin are totally different.


## 3. A Family of New Cyclic Codes Defined by Our Sequences

### 3.1. The Properties on the Generalized Cyclotomy with Order Two Overℤn

In this subsection, the following lemmas follow from [16].Lemma 6.
Whenq≡1mod4, −1∈D0n. When q≡3mod4, −1∈D1n.Lemma 7.
Ifq≡1mod4, then(23)0,02n=p−2q−54,0,12n=1,02n=1,12n=p−2q−14.
Ifq≡3mod4, then(24)0,12n=p−2q+14,0,02n=1,02n=1,12n=p−2q−34.Lemma 8.
(25)D0n+ω∩D1n=0,12n,ifω∈D0n,1,02n,ifω∈D1n,D1n+ω∩D1n=1,12n,ifω∈D0n,0,02n,ifω∈D1n.Lemma 9.
Whenω∈P,(26)Din+ω∩Djn=p−1i,j2q,ifωq=1,p−1i+1,j+12q,ifωq=−1.
Whenω∈Q,(27)Din+ω∩Djn=p−2q−12,ifi=j,0,ifi≠j.


### 3.2. The Parameters of the CodeCs, Minimal Polynomial, and Linear Complexity of the Sequence sn

Letp and q be two difference odd prime numbers with n=pq and l be a power of a prime number r. We always assume that gcdn,l=1 and m is the order of l modulo n. Define(28)Sx=∑i∈C1nxi=∑i∈D1n+∑i∈Pxi∈Flx.Our main objective in this section is to compute the generator polynomial(29)gx=xn−1gcdxn−1,Sxof the cyclic code Cs defined by the sequence sn, where Sx is defined as equation (28). With this purpose, we need to seek out the a0≤a≤n−1, satisfying Sζna=0, where ζn is a fixed n-th primitive root of unity of the finite field Flm. The following auxiliary results are important for our calculation. Obviously, we have(30)∑i∈Pζni=∑i∈Qζni=−1,∑i∈ℤn∗ζni=1.Lemma 10.
(31)∑i∈D1nζnai=−q−12modr,ifa∈Q,p−1η1,ifa∈Panda/pq=1,p−1η0,ifa∈Panda/pq=−1.Proof.
Obviously,D1nmodp=1,2,…,p−1, since g is a common primitive root modulo p and q, and x≡gmodp. Furthermore, one has(32)D1nmodp=g2s+1xtmodp:s=0,1,…,e2−1;t=0,1,…,d−1=g2s+t+1modp:s=0,1,…,e2−1;t=0,1,…,d−1=q−12∗1,2,…,p−1.
Hence,g2s+1xtmodp takes on every element of 1,2,…,p−1 exactly q−1/2 times, when t ranges among 0,1,…,d−1 and s ranges among 0,1,…,e/2−1. If a∈Q, it follows from equations (30) and (32) that(33)∑i∈D1nζnai=q−12∑j∈Qζnj=−q−12modr.
Similarly, we have(34)D1nmodq=g2s+1xtmodq:0≤s≤e2−1;0≤t≤d−1=d∗g2s+1modq:0≤s≤e2−1=p−1∗D1q.
Ifa∈P, it follows that(35)∑i∈D1nζnai=p−1∑j∈D1qζnaj.
Hence, we get the conclusions that, fora∈P and a/p/q=1,(36)∑j∈D1qζnaj=∑j∈D1qζqa/pj=∑i∈D1qζqi=η1,and for a∈P and a/p/q=−1,(37)∑j∈D1qζnaj=∑j∈D1qζqa/pj=∑i∈D0qζqi=η0.Lemma 11.
(38)Sζna=p+1q−12modr,ifa=0,−Sζn−1,ifa∈D1n,Sζn,ifa∈D0n,q−12modr,ifa∈Q,−1+p−1η0,ifa∈Panda/pq=−1,−1+p−1η1,ifa∈Panda/pq=1.Proof.
Ifa=0, then the conclusion is straightforward.
Ifa∈D1n, then aD1n=D0n and aPmodn=P. By equation (30), we get(39)Sζna=∑i∈P+∑i∈D1nζnai=∑j∈Pζnj+∑j∈D0nζnj=∑j∈Pζnj+1−∑j∈D1nζnj=−Sζn−1.
Ifa∈D0n, we have aD1n=D1n and aPmodn=P, since gcda,q=1. So, we have(40)Sζna=∑i∈P+∑i∈D1nζnai=∑j∈Pζnj+∑j∈D1nζnj=Sζn.
Ifa∈Q, then aPmodn=0. So by Lemma 10,(41)Sζna=∑i∈P+∑i∈D1nζnai=q−1+∑i∈D1nζnai=q−12modr.
Ifa∈P, then aPmodn=P. By equation (30) and Lemma 10, one has(42)Sζna=∑j∈Pζnj+∑i∈D1nζnai=−1+p−1η1,ifa∈Panda/pq=1,−1+p−1η0,ifa∈Panda/pq=−1.Lemma 12.
(1) Iflmodn∈D0n, then Sζn∈Fl and thus Sζn+1∈Fl; (2) if lmodn∈D1n, then Sζnl=−Sζn−1.Proof.
(1)
Iflmodn∈D0n, then by Lemma 11, we have(43)Sζnl=Sζnl=Sζn.Hence,Sζn∈Fl.(2)
Iflmodn∈D1n, then by Lemma 11, we have similarly(44)Sζnl=Sζnl=−Sζn−1.
Under this assumption,Sζn∉Fl if l is even, and Sζn may be in Fl if l is odd.Lemma 13.
Whenq≡1mod4, we have(45)SζnSζn+1=q−14modr.
Whenq≡3mod4, we have(46)SζnSζn+1=−q+14modr.Proof.
According to equation (30) and the definition of Sx, one has(47)Sζn=−1+∑i∈D1nζni=−∑i∈D0nζni.
Then, we get(48)SζnSζn+1=−∑i∈D0n∑j∈D1nζni+j.
Suppose thatq≡1mod4. According to Lemma 6, −1∈D0n and −D1n=D1n. It follows from Lemmas 2, 7, 8, and 9 that(49)∑i∈D0n∑j∈D1nζni+j=∑i∈D0n∑j∈D1nζni−j=p−10,12q∑i∈Pi/q=−1ζni+p−11,02q∑i∈Pi/q=1ζni+0,12n∑i∈D1nζni+1,02n∑i∈D0nζni=−q−14modr.
Combining equations (48) and (49), one can get the first conclusion of this lemma.
Suppose thatq≡3mod4 now. According to Lemma 6, −1∈D1n and −D1n=D0n. We have similarly(50)∑i∈D0n∑j∈D1nζni+j=∑i∈D0n∑j∈D0nζni−j=p−11,12q∑i∈Pi/q=−1ζni+p−10,02q∑i∈Pi/q=1ζni+p−1q−12+0,02n∑i∈D0nζni+1,12n∑i∈D1nζni+p−2q−12∑i∈Qζni=q+14modr.
Combining equations (48) and (50), we can arrive at the second conclusion of this lemma.Lemma 14.
(1)lmodn∈D0n and r∈D0n, if q≡1mod4r with q≡1mod4; (2) lmodn∈D0n and r∈D0n, if q≡−1mod4r with q≡3mod4.Proof.
Obviously,lmodn∈D0n if r∈D0n. Now, we only give the proof of the first conclusion since the proof of the second part is similar to it. Let q≡1mod4r with q≡1mod4.
Firstly, we consider the case thatr=2. Therefore, q≡1mod8 and 2/q=1. Suppose that 2∈D1n on the contrary. Then, 2 can be written as 2=g2s+1xt for 0≤s≤e/2−1 and 0≤t≤d−1. According to the definition of g and x, it follows that 2≡g2s+1modq. Therefore, 2 is not a quadratic residue modulo q. The contradiction proves the conclusion for the case r=2.
Secondly, whenr is an odd prime number, we prove this lemma. Since q≡1mod4r, q≡1modr. Hence, q/r=1. Now, one has(51)rq=−1r−1/2q−1/2qr=1.
Suppose thatr∈D1n on the contrary. By definition of D1n, r=g2s+1xt for 0≤s≤e/2−1 and 0≤t≤d−1. Then, we have r≡g2s+1modq. Therefore, r is not a quadratic residue modulo q. This is contrary to equation (69). So, we arrive at the conclusion.
In order to calculate the minimal polynomial and linear complexity ofsn, we need to study the factorization of xn−1 over Fl. It can be checked that the ζnii∈P∪0 are q-th roots of unity and ζnii∈Q∪0 are p-th roots of unity. Therefore,(52)xq−1=∏i∈0∪Px−ζni,xp−1=∏i∈0∪Qx−ζni.
For anyi∈0,1, define(53)dix=∏j∈Dinx−ζnj,where Din denotes the general generalized cyclotomic classes with order two. If lmodn∈D0n, then it is obvious that dix∈Flx for any i.
Letdx=d0xd1x∈Flx. After the above preparations, one has(54)xn−1=∏i=0n−1x−ζni=dxxp−1xq−1x−1.Theorem 1.
Assume thatr=2. We have the assertions as follows:(1)
Whenq≡5mod8, the linear complexity of sn is Ls=n−p, and the cyclic code Cs defined by sn has the parameters n,p,q, whose generator polynomial is mx=xn−1/xp−1.(2)
Whenq≡3mod8, the linear complexity of sn is Ls=n−1, and the cyclic code Cs defined by sn has the parameters n,1,n, whose generator polynomial is mx=xn−1/x−1.(3)
Whenq≡1mod8, the linear complexity of sn is Ls=p+1q−1/2, and the cyclic code Cs defined by sn has the parameters n,p−1q+1/2+1,d, whose generator polynomial is(55)mx=xq−1x−1d1x,ifSζn=0,xq−1x−1d0x,ifSζn=1.(4)
Whenq≡7mod8, the linear complexity of sn is Ls=p+1q+1/2−2, and the cyclic code Cs defined by sn has the parameters n,p−1q−1/2+1,d, whose generator polynomial is(56)mx=xn−1d0xx−1,ifSζn=0,xn−1d1xx−1,ifSζn=1.Proof.
Fromr=2, we get p≡1modr. According to Lemma 11, one has(57)a∈P:Sζna=0=∅,Sζn0=0.
Now, we only prove Case 1, since the others are similar.
For Case 1, by Lemma11,(58)Sζna=0,ifa=0,≠0,ifa∈ℤn∗by Lemma13,=0,ifa∈Q,≠0,ifa∈P.
Therefore,gcdxn−1,Sx=xp−1 and mx=xn−1/xp−1. Then, the linear complexity of the sequence sn is Ls=degmx=n−p. Furthermore, the definition of the code can lead to the parameters of the code Cs.Example 1.
Assume thatl,p,q=2,3,5. Then, n=15, q≡5mod8, the minimal polynomial is x12+x9+x6+x3+1, and the linear complexity of sn is 12. The cycle code Cs defined by sn is a 15,3,5 cyclic code over F2. According to the database [19], the best binary linear code known with the parameters 15,3,d has minimum distance 8.Example 2.
Assume thatl,p,q=2,3,7. In this case, n=21, q≡7mod8, the minimal polynomial is x14+x13+x9+x8+x7+x5+x4+x3+1, and the linear complexity of sn is 14. The cycle code Cs defined by sn is a 21,7,8 cyclic code over F2, which is an optimal linear code according to the database [19].Remark 3.
In [7], example 3.20 presents a 21,7,3 cyclic code over F2, whose generator polynomial is x14+x7+1. This is bad because of its poor minimum distance. Obviously, our cyclic code is more optimal.Example 3.
Assume thatl,p,q=2,5,13. Then, n=65, q≡5mod8, the minimal polynomial is x60+x55+x50+x45+x40+x35+x30+x25+x20+x15+x10+x5+1, and the linear complexity of sn is 60. The cycle code Cs defined by sn is a 65,5,13 cyclic code over F2.Theorem 2.
Assume thatp≡1modr and r≠2.(1)
Whenq≡±1modr and q≡3mod4, or q≡1modr and q≡1mod4, the linear complexity of sn is Ls=n, and sn has the minimal polynomial mx=xn−1.(2)
Whenq≡1modr and q≡3mod4, the linear complexity of sn is Ls=n−p, and sn has the minimal polynomial mx=xn−1/xp−1. The cyclic code Cs defined by sn has the parameters n,p,q.(3)
Whenq≡1modr and q≡1mod4, lmodn∈D0n and dix∈Flx for i=0,1 by Lemma 14. Hence, Sζn∈0,−1. The linear complexity of sn is Ls=p+1q−1/2, and sn has the minimal polynomial(59)mx=xq−1x−1d1x,ifSζn=0,xq−1x−1d0x,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,p−1q+1/2+1,d.(4)
Whenq≡−1modr and q≡3mod4, lmodn∈D0n and dix∈Flx for i=0,1 by Lemma 14. Hence, Sζn∈0,−1. The linear complexity of sn is Ls=p+1q+1/2−1, and sn has the minimal polynomial(60)mx=xn−1d0x,ifSζn=0,xn−1d1x,ifSζn=−1.
The cyclic codeCs defined by sn has the parameters n,p−1q−1/2,d.Proof.
According to Lemma11 and p≡1modr, one has a∈P:Sζna=0=∅. Now, we only prove Case 3, since the others are similar.
For Case 3, ifSζn=0, by Lemma 11,(61)Sζna=0,ifa=0,≠0,ifa∈D1n,=0,ifa∈D0n,≠0,ifa∈P,=0,ifa∈Q.
Therefore,mx=xn−1/d0xxp−1=xq−1/x−1d1x. If Sζn=−1, by Lemma 11,(62)Sζna=0,ifa=0,=0,ifa∈D1n,≠0,ifa∈D0n,≠0,ifa∈P,=0,ifa∈Q.
Therefore,mx=xn−1/d1xxp−1=xq−1/x−1d0x. Then, the linear complexity of sn is Ls=degmx. Moreover, the definition of the cyclic code can lead to the parameters of Cs.Example 4.
Assume thatl,p,q=3,7,11. Then, n=77, q≡−1mod3 and q≡3mod4, the minimal polynomial is x47+2x45+x44+2x43+2x42+2x40+x38+2x37+x36+x35+2x33+x31+2x30+x29+x28+2x26+x24+2x23+x22+x21+x19+2x17+x16+2x15+2x14+x5+2x3+x2+2x+2, and the linear complexity of sn is 47. The cycle code Cs defined by sn is a 77,30,12 cyclic code over F3.Lemma 15 (see [15].
LetA=−1/qq−p+1/p−12. If A=0 and p≡1modr, then lmodq∈D0q.
Define(63)d0′x=∏i∈Pi/p/q=1x−ζni,d1′x=∏i∈Pi/p/q=−1x−ζni.
Iflmodq∈D0q, then it is straightforward to prove that di′x∈Flx for i=0,1. Therefore, when A=0 and p≡1modr, one has d0′x,d1′x∈Flx by Lemma 15.Theorem 3.
Assume thatp≡1modr.(1)
Whenq≡1modr, q≡1mod4, and p≡−1modr or q≡±1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is Ls=n−1, and sn has the minimal polynomial mx=xn−1/x−1. The parameters of Cs defined by sn are n,1,n.(2)
Whenq≡1modr, q≡1mod4, and p≡−1modr or q≡±1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is(64)Ls=n,ifA≠0,n−q−12,ifA=0,andsn has the minimal polynomial(65)mx=xn−1,ifA≠0,xn−1d1′x,ifη0=1p−1,xn−1d0′x,ifη1=1p−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.(3)
Whenq≡1modr and q≡3mod4, the linear complexity of sn is(66)Ls=n−p,ifA≠0,n−p−q−12,ifA=0,andsn has the minimal polynomial(67)mx=xn−1xp−1,ifA≠0,xn−1d1′xxp−1,ifη0=1p−1,xn−1d0′xxp−1,ifη1=1p−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.(4)
Whenq≡1modr and q≡1mod4, the linear complexity of sn is Ls=p+1q−1/2, and sn has the minimal polynomial(68)mx=xq−1x−1d1x,ifSζn=0,xq−1x−1d0x,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,p−1q+1/2+1,d, where the minimum weight d follows from Theorem 5.(5)
Whenq≡−1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is Ls=p+1q+1/2−2, and sn has the minimal polynomial(69)mx=xn−1d0xx−1,ifSζn=0,xn−1d1xx−1,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.(6)
Whenq≡−1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is Ls=p+1q+1/2−1, and sn has the minimal polynomial(70)mx=xn−1d0x,ifSζn=0,xn−1d1x,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.Proof.
Fromp≡1modr, we get that r is an odd prime. Define(71)Δ=q−12modr,Δ′=p+1q−12modr.
We will use the following property, which is easily seen to hold.Property 1.
q≡1modr if and only if Δ=0; p≡−1modr or q≡1modr if and only if Δ′=0. If Δ=0, then Δ′=0.Property 2.
p−1η0=1 and p−1η1=1 cannot exist simultaneously, since gcdn,l=1 and p≡1modr.Property 3.
p−1η0=1 or p−1η1=1 if and only if A=0.Property 4.
Δ′≠0, if A=0 and q≡1modr.Property 5.
A≠0, if q≡1modr and q≡1mod4, or q≡−1modr and q≡3mod4.
Now, we only prove Case 3, since the others are similar. One hasq+1/4modr≠0 and Δ=Δ′=0, since q≡3mod4 and q≡1modr. Hence, a∈Q∪0:Sζna=0=Q∪0 and a∈ℤn∗:Sζna=0=∅. According to Properties 1–5, if A≠0, by Lemma 11,(72)Sζna=0,ifa=0,≠0,ifa∈ℤn∗,=0,ifa∈Q,≠0,ifa∈P.
Therefore,mx=xn−1/xp−1. If η0=1/p−1, by Lemma 11,(73)Sζna=0,ifa=0,≠0,ifa∈ℤn∗,=0,ifa∈Q,≠0,ifa∈Panda/pq=1,=0,ifa∈Panda/pq=−1.
Hence,mx=xn−1/d1′xxp−1. If η1=1/p−1, by Lemma 11,(74)Sζna=0,ifa=0,≠0,ifa∈ℤn∗,=0,ifa∈Q,=0,ifa∈Panda/pq=1,≠0,ifa∈Panda/pq=−1.
Therefore,mx=xn−1/d0′xxp−1. Then, Ls=degmx and the definition of the cyclic code can lead to the parameters of Cs.Example 5.
Assume thatl,p,q=3,5,7. Then, n=35, q≡1mod3, p≡2mod3, q≡3mod4, A≠0, the minimal polynomial is x30+x25+x20+x15+x10+x5+1, and the linear complexity of sn is 30. The cycle code Cs defined by sn is a 35,5,7 cyclic code over F3.Remark 4.
Theorems1, 2, and 3 show that the linear complexity of the two-prime GGCSs defined by equation (22) is very high. Without the limit of gcdp−1,q−1=2, this paper can obtain some binary sequences with new parameters and higher linear complexity. Furthermore, when gcdp−1,q−1=2, Theorem 1 in our paper is the same with Theorem 1 in [14]. When gcdp−1,q−1=2, Theorem 2 in our paper is in accord with Theorems 13 and 16 in [15], and Theorem 3 in our paper is exactly identical with Theorems 14 and 18 in [15]. However, if gcdp−1,q−1 is not equal to 2, the conclusions in Theorems 1, 2, and 3 of our paper are new, which can be seen from Example 3. Therefore, the sequences defined by equation (22) will be more attractive than those in [14, 15] in some cryptographic applications.


## 3.1. The Properties on the Generalized Cyclotomy with Order Two Overℤn

In this subsection, the following lemmas follow from [16].Lemma 6.
Whenq≡1mod4, −1∈D0n. When q≡3mod4, −1∈D1n.Lemma 7.
Ifq≡1mod4, then(23)0,02n=p−2q−54,0,12n=1,02n=1,12n=p−2q−14.
Ifq≡3mod4, then(24)0,12n=p−2q+14,0,02n=1,02n=1,12n=p−2q−34.Lemma 8.
(25)D0n+ω∩D1n=0,12n,ifω∈D0n,1,02n,ifω∈D1n,D1n+ω∩D1n=1,12n,ifω∈D0n,0,02n,ifω∈D1n.Lemma 9.
Whenω∈P,(26)Din+ω∩Djn=p−1i,j2q,ifωq=1,p−1i+1,j+12q,ifωq=−1.
Whenω∈Q,(27)Din+ω∩Djn=p−2q−12,ifi=j,0,ifi≠j.


## 3.2. The Parameters of the CodeCs, Minimal Polynomial, and Linear Complexity of the Sequence sn

Letp and q be two difference odd prime numbers with n=pq and l be a power of a prime number r. We always assume that gcdn,l=1 and m is the order of l modulo n. Define(28)Sx=∑i∈C1nxi=∑i∈D1n+∑i∈Pxi∈Flx.Our main objective in this section is to compute the generator polynomial(29)gx=xn−1gcdxn−1,Sxof the cyclic code Cs defined by the sequence sn, where Sx is defined as equation (28). With this purpose, we need to seek out the a0≤a≤n−1, satisfying Sζna=0, where ζn is a fixed n-th primitive root of unity of the finite field Flm. The following auxiliary results are important for our calculation. Obviously, we have(30)∑i∈Pζni=∑i∈Qζni=−1,∑i∈ℤn∗ζni=1.Lemma 10.
(31)∑i∈D1nζnai=−q−12modr,ifa∈Q,p−1η1,ifa∈Panda/pq=1,p−1η0,ifa∈Panda/pq=−1.Proof.
Obviously,D1nmodp=1,2,…,p−1, since g is a common primitive root modulo p and q, and x≡gmodp. Furthermore, one has(32)D1nmodp=g2s+1xtmodp:s=0,1,…,e2−1;t=0,1,…,d−1=g2s+t+1modp:s=0,1,…,e2−1;t=0,1,…,d−1=q−12∗1,2,…,p−1.
Hence,g2s+1xtmodp takes on every element of 1,2,…,p−1 exactly q−1/2 times, when t ranges among 0,1,…,d−1 and s ranges among 0,1,…,e/2−1. If a∈Q, it follows from equations (30) and (32) that(33)∑i∈D1nζnai=q−12∑j∈Qζnj=−q−12modr.
Similarly, we have(34)D1nmodq=g2s+1xtmodq:0≤s≤e2−1;0≤t≤d−1=d∗g2s+1modq:0≤s≤e2−1=p−1∗D1q.
Ifa∈P, it follows that(35)∑i∈D1nζnai=p−1∑j∈D1qζnaj.
Hence, we get the conclusions that, fora∈P and a/p/q=1,(36)∑j∈D1qζnaj=∑j∈D1qζqa/pj=∑i∈D1qζqi=η1,and for a∈P and a/p/q=−1,(37)∑j∈D1qζnaj=∑j∈D1qζqa/pj=∑i∈D0qζqi=η0.Lemma 11.
(38)Sζna=p+1q−12modr,ifa=0,−Sζn−1,ifa∈D1n,Sζn,ifa∈D0n,q−12modr,ifa∈Q,−1+p−1η0,ifa∈Panda/pq=−1,−1+p−1η1,ifa∈Panda/pq=1.Proof.
Ifa=0, then the conclusion is straightforward.
Ifa∈D1n, then aD1n=D0n and aPmodn=P. By equation (30), we get(39)Sζna=∑i∈P+∑i∈D1nζnai=∑j∈Pζnj+∑j∈D0nζnj=∑j∈Pζnj+1−∑j∈D1nζnj=−Sζn−1.
Ifa∈D0n, we have aD1n=D1n and aPmodn=P, since gcda,q=1. So, we have(40)Sζna=∑i∈P+∑i∈D1nζnai=∑j∈Pζnj+∑j∈D1nζnj=Sζn.
Ifa∈Q, then aPmodn=0. So by Lemma 10,(41)Sζna=∑i∈P+∑i∈D1nζnai=q−1+∑i∈D1nζnai=q−12modr.
Ifa∈P, then aPmodn=P. By equation (30) and Lemma 10, one has(42)Sζna=∑j∈Pζnj+∑i∈D1nζnai=−1+p−1η1,ifa∈Panda/pq=1,−1+p−1η0,ifa∈Panda/pq=−1.Lemma 12.
(1) Iflmodn∈D0n, then Sζn∈Fl and thus Sζn+1∈Fl; (2) if lmodn∈D1n, then Sζnl=−Sζn−1.Proof.
(1)
Iflmodn∈D0n, then by Lemma 11, we have(43)Sζnl=Sζnl=Sζn.Hence,Sζn∈Fl.(2)
Iflmodn∈D1n, then by Lemma 11, we have similarly(44)Sζnl=Sζnl=−Sζn−1.
Under this assumption,Sζn∉Fl if l is even, and Sζn may be in Fl if l is odd.Lemma 13.
Whenq≡1mod4, we have(45)SζnSζn+1=q−14modr.
Whenq≡3mod4, we have(46)SζnSζn+1=−q+14modr.Proof.
According to equation (30) and the definition of Sx, one has(47)Sζn=−1+∑i∈D1nζni=−∑i∈D0nζni.
Then, we get(48)SζnSζn+1=−∑i∈D0n∑j∈D1nζni+j.
Suppose thatq≡1mod4. According to Lemma 6, −1∈D0n and −D1n=D1n. It follows from Lemmas 2, 7, 8, and 9 that(49)∑i∈D0n∑j∈D1nζni+j=∑i∈D0n∑j∈D1nζni−j=p−10,12q∑i∈Pi/q=−1ζni+p−11,02q∑i∈Pi/q=1ζni+0,12n∑i∈D1nζni+1,02n∑i∈D0nζni=−q−14modr.
Combining equations (48) and (49), one can get the first conclusion of this lemma.
Suppose thatq≡3mod4 now. According to Lemma 6, −1∈D1n and −D1n=D0n. We have similarly(50)∑i∈D0n∑j∈D1nζni+j=∑i∈D0n∑j∈D0nζni−j=p−11,12q∑i∈Pi/q=−1ζni+p−10,02q∑i∈Pi/q=1ζni+p−1q−12+0,02n∑i∈D0nζni+1,12n∑i∈D1nζni+p−2q−12∑i∈Qζni=q+14modr.
Combining equations (48) and (50), we can arrive at the second conclusion of this lemma.Lemma 14.
(1)lmodn∈D0n and r∈D0n, if q≡1mod4r with q≡1mod4; (2) lmodn∈D0n and r∈D0n, if q≡−1mod4r with q≡3mod4.Proof.
Obviously,lmodn∈D0n if r∈D0n. Now, we only give the proof of the first conclusion since the proof of the second part is similar to it. Let q≡1mod4r with q≡1mod4.
Firstly, we consider the case thatr=2. Therefore, q≡1mod8 and 2/q=1. Suppose that 2∈D1n on the contrary. Then, 2 can be written as 2=g2s+1xt for 0≤s≤e/2−1 and 0≤t≤d−1. According to the definition of g and x, it follows that 2≡g2s+1modq. Therefore, 2 is not a quadratic residue modulo q. The contradiction proves the conclusion for the case r=2.
Secondly, whenr is an odd prime number, we prove this lemma. Since q≡1mod4r, q≡1modr. Hence, q/r=1. Now, one has(51)rq=−1r−1/2q−1/2qr=1.
Suppose thatr∈D1n on the contrary. By definition of D1n, r=g2s+1xt for 0≤s≤e/2−1 and 0≤t≤d−1. Then, we have r≡g2s+1modq. Therefore, r is not a quadratic residue modulo q. This is contrary to equation (69). So, we arrive at the conclusion.
In order to calculate the minimal polynomial and linear complexity ofsn, we need to study the factorization of xn−1 over Fl. It can be checked that the ζnii∈P∪0 are q-th roots of unity and ζnii∈Q∪0 are p-th roots of unity. Therefore,(52)xq−1=∏i∈0∪Px−ζni,xp−1=∏i∈0∪Qx−ζni.
For anyi∈0,1, define(53)dix=∏j∈Dinx−ζnj,where Din denotes the general generalized cyclotomic classes with order two. If lmodn∈D0n, then it is obvious that dix∈Flx for any i.
Letdx=d0xd1x∈Flx. After the above preparations, one has(54)xn−1=∏i=0n−1x−ζni=dxxp−1xq−1x−1.Theorem 1.
Assume thatr=2. We have the assertions as follows:(1)
Whenq≡5mod8, the linear complexity of sn is Ls=n−p, and the cyclic code Cs defined by sn has the parameters n,p,q, whose generator polynomial is mx=xn−1/xp−1.(2)
Whenq≡3mod8, the linear complexity of sn is Ls=n−1, and the cyclic code Cs defined by sn has the parameters n,1,n, whose generator polynomial is mx=xn−1/x−1.(3)
Whenq≡1mod8, the linear complexity of sn is Ls=p+1q−1/2, and the cyclic code Cs defined by sn has the parameters n,p−1q+1/2+1,d, whose generator polynomial is(55)mx=xq−1x−1d1x,ifSζn=0,xq−1x−1d0x,ifSζn=1.(4)
Whenq≡7mod8, the linear complexity of sn is Ls=p+1q+1/2−2, and the cyclic code Cs defined by sn has the parameters n,p−1q−1/2+1,d, whose generator polynomial is(56)mx=xn−1d0xx−1,ifSζn=0,xn−1d1xx−1,ifSζn=1.Proof.
Fromr=2, we get p≡1modr. According to Lemma 11, one has(57)a∈P:Sζna=0=∅,Sζn0=0.
Now, we only prove Case 1, since the others are similar.
For Case 1, by Lemma11,(58)Sζna=0,ifa=0,≠0,ifa∈ℤn∗by Lemma13,=0,ifa∈Q,≠0,ifa∈P.
Therefore,gcdxn−1,Sx=xp−1 and mx=xn−1/xp−1. Then, the linear complexity of the sequence sn is Ls=degmx=n−p. Furthermore, the definition of the code can lead to the parameters of the code Cs.Example 1.
Assume thatl,p,q=2,3,5. Then, n=15, q≡5mod8, the minimal polynomial is x12+x9+x6+x3+1, and the linear complexity of sn is 12. The cycle code Cs defined by sn is a 15,3,5 cyclic code over F2. According to the database [19], the best binary linear code known with the parameters 15,3,d has minimum distance 8.Example 2.
Assume thatl,p,q=2,3,7. In this case, n=21, q≡7mod8, the minimal polynomial is x14+x13+x9+x8+x7+x5+x4+x3+1, and the linear complexity of sn is 14. The cycle code Cs defined by sn is a 21,7,8 cyclic code over F2, which is an optimal linear code according to the database [19].Remark 3.
In [7], example 3.20 presents a 21,7,3 cyclic code over F2, whose generator polynomial is x14+x7+1. This is bad because of its poor minimum distance. Obviously, our cyclic code is more optimal.Example 3.
Assume thatl,p,q=2,5,13. Then, n=65, q≡5mod8, the minimal polynomial is x60+x55+x50+x45+x40+x35+x30+x25+x20+x15+x10+x5+1, and the linear complexity of sn is 60. The cycle code Cs defined by sn is a 65,5,13 cyclic code over F2.Theorem 2.
Assume thatp≡1modr and r≠2.(1)
Whenq≡±1modr and q≡3mod4, or q≡1modr and q≡1mod4, the linear complexity of sn is Ls=n, and sn has the minimal polynomial mx=xn−1.(2)
Whenq≡1modr and q≡3mod4, the linear complexity of sn is Ls=n−p, and sn has the minimal polynomial mx=xn−1/xp−1. The cyclic code Cs defined by sn has the parameters n,p,q.(3)
Whenq≡1modr and q≡1mod4, lmodn∈D0n and dix∈Flx for i=0,1 by Lemma 14. Hence, Sζn∈0,−1. The linear complexity of sn is Ls=p+1q−1/2, and sn has the minimal polynomial(59)mx=xq−1x−1d1x,ifSζn=0,xq−1x−1d0x,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,p−1q+1/2+1,d.(4)
Whenq≡−1modr and q≡3mod4, lmodn∈D0n and dix∈Flx for i=0,1 by Lemma 14. Hence, Sζn∈0,−1. The linear complexity of sn is Ls=p+1q+1/2−1, and sn has the minimal polynomial(60)mx=xn−1d0x,ifSζn=0,xn−1d1x,ifSζn=−1.
The cyclic codeCs defined by sn has the parameters n,p−1q−1/2,d.Proof.
According to Lemma11 and p≡1modr, one has a∈P:Sζna=0=∅. Now, we only prove Case 3, since the others are similar.
For Case 3, ifSζn=0, by Lemma 11,(61)Sζna=0,ifa=0,≠0,ifa∈D1n,=0,ifa∈D0n,≠0,ifa∈P,=0,ifa∈Q.
Therefore,mx=xn−1/d0xxp−1=xq−1/x−1d1x. If Sζn=−1, by Lemma 11,(62)Sζna=0,ifa=0,=0,ifa∈D1n,≠0,ifa∈D0n,≠0,ifa∈P,=0,ifa∈Q.
Therefore,mx=xn−1/d1xxp−1=xq−1/x−1d0x. Then, the linear complexity of sn is Ls=degmx. Moreover, the definition of the cyclic code can lead to the parameters of Cs.Example 4.
Assume thatl,p,q=3,7,11. Then, n=77, q≡−1mod3 and q≡3mod4, the minimal polynomial is x47+2x45+x44+2x43+2x42+2x40+x38+2x37+x36+x35+2x33+x31+2x30+x29+x28+2x26+x24+2x23+x22+x21+x19+2x17+x16+2x15+2x14+x5+2x3+x2+2x+2, and the linear complexity of sn is 47. The cycle code Cs defined by sn is a 77,30,12 cyclic code over F3.Lemma 15 (see [15].
LetA=−1/qq−p+1/p−12. If A=0 and p≡1modr, then lmodq∈D0q.
Define(63)d0′x=∏i∈Pi/p/q=1x−ζni,d1′x=∏i∈Pi/p/q=−1x−ζni.
Iflmodq∈D0q, then it is straightforward to prove that di′x∈Flx for i=0,1. Therefore, when A=0 and p≡1modr, one has d0′x,d1′x∈Flx by Lemma 15.Theorem 3.
Assume thatp≡1modr.(1)
Whenq≡1modr, q≡1mod4, and p≡−1modr or q≡±1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is Ls=n−1, and sn has the minimal polynomial mx=xn−1/x−1. The parameters of Cs defined by sn are n,1,n.(2)
Whenq≡1modr, q≡1mod4, and p≡−1modr or q≡±1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is(64)Ls=n,ifA≠0,n−q−12,ifA=0,andsn has the minimal polynomial(65)mx=xn−1,ifA≠0,xn−1d1′x,ifη0=1p−1,xn−1d0′x,ifη1=1p−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.(3)
Whenq≡1modr and q≡3mod4, the linear complexity of sn is(66)Ls=n−p,ifA≠0,n−p−q−12,ifA=0,andsn has the minimal polynomial(67)mx=xn−1xp−1,ifA≠0,xn−1d1′xxp−1,ifη0=1p−1,xn−1d0′xxp−1,ifη1=1p−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.(4)
Whenq≡1modr and q≡1mod4, the linear complexity of sn is Ls=p+1q−1/2, and sn has the minimal polynomial(68)mx=xq−1x−1d1x,ifSζn=0,xq−1x−1d0x,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,p−1q+1/2+1,d, where the minimum weight d follows from Theorem 5.(5)
Whenq≡−1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is Ls=p+1q+1/2−2, and sn has the minimal polynomial(69)mx=xn−1d0xx−1,ifSζn=0,xn−1d1xx−1,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.(6)
Whenq≡−1modr, q≡3mod4, and p≡−1modr, the linear complexity of sn is Ls=p+1q+1/2−1, and sn has the minimal polynomial(70)mx=xn−1d0x,ifSζn=0,xn−1d1x,ifSζn=−1.The cyclic codeCs defined by sn has the parameters n,n−degmx,d.Proof.
Fromp≡1modr, we get that r is an odd prime. Define(71)Δ=q−12modr,Δ′=p+1q−12modr.
We will use the following property, which is easily seen to hold.Property 1.
q≡1modr if and only if Δ=0; p≡−1modr or q≡1modr if and only if Δ′=0. If Δ=0, then Δ′=0.Property 2.
p−1η0=1 and p−1η1=1 cannot exist simultaneously, since gcdn,l=1 and p≡1modr.Property 3.
p−1η0=1 or p−1η1=1 if and only if A=0.Property 4.
Δ′≠0, if A=0 and q≡1modr.Property 5.
A≠0, if q≡1modr and q≡1mod4, or q≡−1modr and q≡3mod4.
Now, we only prove Case 3, since the others are similar. One hasq+1/4modr≠0 and Δ=Δ′=0, since q≡3mod4 and q≡1modr. Hence, a∈Q∪0:Sζna=0=Q∪0 and a∈ℤn∗:Sζna=0=∅. According to Properties 1–5, if A≠0, by Lemma 11,(72)Sζna=0,ifa=0,≠0,ifa∈ℤn∗,=0,ifa∈Q,≠0,ifa∈P.
Therefore,mx=xn−1/xp−1. If η0=1/p−1, by Lemma 11,(73)Sζna=0,ifa=0,≠0,ifa∈ℤn∗,=0,ifa∈Q,≠0,ifa∈Panda/pq=1,=0,ifa∈Panda/pq=−1.
Hence,mx=xn−1/d1′xxp−1. If η1=1/p−1, by Lemma 11,(74)Sζna=0,ifa=0,≠0,ifa∈ℤn∗,=0,ifa∈Q,=0,ifa∈Panda/pq=1,≠0,ifa∈Panda/pq=−1.
Therefore,mx=xn−1/d0′xxp−1. Then, Ls=degmx and the definition of the cyclic code can lead to the parameters of Cs.Example 5.
Assume thatl,p,q=3,5,7. Then, n=35, q≡1mod3, p≡2mod3, q≡3mod4, A≠0, the minimal polynomial is x30+x25+x20+x15+x10+x5+1, and the linear complexity of sn is 30. The cycle code Cs defined by sn is a 35,5,7 cyclic code over F3.Remark 4.
Theorems1, 2, and 3 show that the linear complexity of the two-prime GGCSs defined by equation (22) is very high. Without the limit of gcdp−1,q−1=2, this paper can obtain some binary sequences with new parameters and higher linear complexity. Furthermore, when gcdp−1,q−1=2, Theorem 1 in our paper is the same with Theorem 1 in [14]. When gcdp−1,q−1=2, Theorem 2 in our paper is in accord with Theorems 13 and 16 in [15], and Theorem 3 in our paper is exactly identical with Theorems 14 and 18 in [15]. However, if gcdp−1,q−1 is not equal to 2, the conclusions in Theorems 1, 2, and 3 of our paper are new, which can be seen from Example 3. Therefore, the sequences defined by equation (22) will be more attractive than those in [14, 15] in some cryptographic applications.


## 4. The Minimum Distance of the Cycle Codes Obtained in This Paper

Theorem 4 (see [7]).
If the generator polynomial ofCs over Fl is gx=xn−1/xp−1, then Cs has parameters n,p,q. Also, if the generator polynomial of Cs over Fl is gx=xn−1/xq−1, then Cs has parameters n,q,p.Theorem 5.
Letlmodn∈D0n. Let Cp,q,li be the cyclic code over Fl generated by the polynomial(75)gix=dixxq−1x−1.Assume thatdp,q,lii=0,1 is the minimum distance of this code. The parameters of the cycle code Cp,q,li are(76)n,p−1q+12+1,dp,q,li,where(77)dp,q,li≥q.If−1∈D1n, we have(78)dp,q,li2−dp,q,li+1≥q.Proof.
Assume thatcx∈Cp,q,li, whose Hamming weight is ω. Take any k∈D1n. Then, cxk is a code word in Cp,q,li+1mod2, whose Hamming weight is also ω. Therefore, we have dp,q,li=dp,q,li+1mod2.
Suppose thatcx∈Cp,q,li, whose Hamming weight is minimum. Then, cxk is a code word in Cp,q,li+1mod2, whose Hamming weight is also minimum. Furthermore, for any k∈D1n, cxcxk is a code word in the cyclic code(79)Cp,q,li∩Cp,q,li+1mod2,whose generator polynomial is xn−1/xp−1 and minimum distance is q (see Theorem 4). Hence, we have that(80)dp,q,li≥q,dp,q,li2−dp,q,li+1≥q,if −1∈D1n.Example 6.
Assume thatl,p,q=2,3,17. In this case, 2∈D0n, the cyclic code Cs generated by the polynomial gx=xq−1/x−1d1x has parameters 51,19,10. The actual minimum distance is 10, but the lower bound of (77) is 2.


## 5. Conclusion

In this paper, we studied the uniform representation of general generalized cyclotomy with order two overℤpq. Based on the general generalized cyclotomy, the general two-prime generalized cyclotomic sequences were proposed. The sequences in our paper have high linear complexity. Notably, our construction can generate more sequences with new parameters and high linear complexity. Furthermore, inspired by the idea of [7], we constructed some cyclic codes by virtue of special classes of sequences. Our results show that several cyclic codes are optimal, such as Example 2.



---

*Source: 6625652-2020-12-23.xml*