# Autocorrelation and Linear Complexity of Binary Generalized Cyclotomic Sequences with Periodpq

Authors: Yan Wang; Liantao Yan; Qing Tian; Liping Ding
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Ding constructed a new cyclotomic classV0,V1. Based on it, a construction of generalized cyclotomic binary sequences with period pq is described, and their autocorrelation value, linear complexity, and minimal polynomial are confirmed. The autocorrelation function CSw is 3-level if p≡3mod4, and CSw is 5-level if p≡1mod4. The linear complexity LCS>pq/2 if p≡1mod8, p>q+1, or p≡3mod4 or p≡−3mod8. The results show that these sequences have quite good cryptographic properties in the aspect of autocorrelation and linear complexity.


---

## Body

## 1. Introduction

Pseudorandom sequences with good cryptography properties have wide applications in CDMA, global positing systems, and stream ciphers. The security of stream ciphers depends on the randomness of the key stream, which makes the construction of pseudorandom sequences to be an important research direction. Many researchers focused on cyclotomic sequences, which have good balance property. Linear complexity and autocorrelation are important criteria for measuring unpredictability of cyclotomic sequences.LetFl denote a finite field with l elements, where l is a prime power. A sequence S=si is periodic if there exists a positive integer N such that sj+N=sj for all j≥0.LetS=si be a periodic sequence over Fl with period N. The periodic autocorrelation function of binary sequence S is defined by(1)CSw=∑i=0N−1−1si+w+si,where 0≤w≤N−1.Autocorrelation function measures the amount of similarity between sequenceS and a shift of S by w shifts. Only when the values of CSw distribute flat and low, sequence S is easy to distinguish from each time shifted version of itself. The autocorrelation function with the ideal distribution of values is two-valued, which is given as(2)CSw=Nifw=0,1,otherwise.Sequences with ideal autocorrelation functions have many applications in cryptography, coding, and other communication engineering.Linear complexity ofS, denoted by LCS, is the least integer L of a linear recurrence relation over Fl satisfied by S:(3)−c0si+L=c1si+L−1+⋯+cLsi,i≥0,where c0,c1,…,cL∈Fl. The linear complexity of a sequence is also defined to be the length of the shortest linear feedback shift register which can generate the sequence. It is an important criterion of randomness of sequences in stream ciphers. To resist the attack from Berlekamp–Massey algorithm, the sequences used in cipher systems should have large linear complexity. If LCS≥N/2, where N is the least period of S, then S is considered to be good from the viewpoint of linear complexity.The minimal polynomialmx of S is(4)mx=xN−1gcdxN−1,Sx,and the linear complexity LCS of S is given by N−deggcdxN−1,Sx, where Sx is the generating polynomial of S, that is,(5)Sx=s0+s1x+s2x2+⋯+sN−1xN−1.Sequences from cyclotomic and generalized cyclotomic are important families of pseudorandom sequences.For an integerN≥2, let ZN=0,1,…,N−1 denote the residue class ring of integers modulo N and ZN∗ be the multiplicative group consisting of all invertible elements in ZN. A partition D0N,D1N,…,Dd−1N of ZN∗ is a family of sets satisfying DiN∩DjN=∅ for all i≠j and ZN∗=∪i=0d−1DiN. Suppose D0N is a multiplicative subgroup of ZN∗ and there exist elements g∈ZN∗ such that DiN=giD0N for all i=1,…,d−1; then, DiN are called classical cyclotomic classes of order d with respect to N when N is prime and generalized cyclotomic classes of order d with respect to N when N is composite. The sequences constructed by them are called classical cyclotomic sequences and generalized cyclotomic sequences, respectively. Gauss [1] first proposed the concept of cyclotomic, divided the multiplicative group Zp∗, and then divided the residual class ring Zp to construct Gauss classical cyclotomic. Whiteman [2] divided the multiplicative group Zpq∗ and then divided the residual class ring Zpq to construct Whiteman generalized cyclotomic. Ding and Helleseth [3] divided the multiplicative group Zp1e1p2e2…ptet∗ and then divided the residual class ring Zp1e1p2e2…ptet to construct the Ding generalized cyclotomic. The above three kinds of cyclotomic theories are the most representative and the most widely used cyclotomic theories.Classical cyclotomic sequences include Legendre sequences,d-degree residual sequences, and Hall sextic residue sequences. Damgaard [4] determined the autocorrelation value of Legendre sequences, and then Ding et al. [5] determined their linear complexity. Kim and Song [6] determined the linear complexity of Hall sextic residue sequences.Ding [7] constructed Whiteman generalized cyclotomic sequences of order 2 and confirmed their linear complexity. And Ding [8] determined the autocorrelation value of Whiteman generalized cyclotomic sequences of order 2. Bai [9] constructed Whiteman generalized cyclotomic sequences of order 4 and determined their linear complexity. Yan et al. [10] extended Whiteman generalized cyclotomic sequences to the case of order 2k.Bai [9] determined the autocorrelation value of Ding generalized cyclotomic sequences with period pq of order 2. And Bai et al. [11] confirmed they had high linear complexity. Yan et al. [12] constructed Ding generalized cyclotomic sequences with period pm and confirmed they had high linear complexity. Edemskiy [13] constructed a kind of balanced binary generalized cyclotomic sequences with period pn+1. Zhang et al. [14] determined the linear complexity of generalized cyclotomic sequences with period 2pm. Hu et al. [15] constructed generalized cyclotomic sequences with period pm+1qn+1 and determined their linear complexity. Ke et al. [16] determined the linear complexity and the autocorrelation value of Ding generalized cyclotomic sequences with period 2pm. Chang et al. [17] constructed binary generalized cyclotomic sequences with period pqr and determined their linear complexity and minimal polynomial.Ding [18] constructed a new cyclotomic class V0,V1 and obtained a kind of cyclic code from it. Liu and Chen [19] determined binary generalized cyclotomic sequences with period pq based on the new cyclotomic class V0,V1 and determined their autocorrelation value, linear complexity, and minimal polynomial.In this paper, based on Ding’s new cyclotomic classV0,V1, a simple construction of binary generalized cyclotomic sequences with period pq is constructed, and their autocorrelation value, linear complexity, and minimal polynomial are confirmed. The remainder of this paper is organized as follows. Section 2 proposes a construction of generalized cyclotomic binary sequences. Section 3 calculates the autocorrelation value, linear complexity, and minimal polynomial of the new sequences and compares our results with [19]. Section 4 concludes this paper.


## 2. Preliminaries

Lemma 1 (see [20]).
Letm1>0,m2>0,a1,anda2 be integers. The system of congruences,(6)x≡a1modm1,x≡a2modm2,has solutions if and only if gcdm1,m2|a1−a2.
If the above condition is satisfied, the solution is unique modulolcmm1,m2.LetN=pq, where p and q are two distinct odd primes. Let g be the unique common primitive root of p and q. The existence and uniqueness of g are guaranteed by Lemma 1. Similarly, there exists a unique integer x which satisfies the following system of congruences:(7)x≡gmodp,x≡1modq.Letd=gcdp−1,q−1 and e=gcdp−1q−1/d. According to Whiteman [2], Whiteman generalized cyclotomic class of order d is(8)Di=gsxi:s=0,1,…,e−1,i=0,1,…,d−1.It can be easily seen thatDi∩DjN=∅ for all i≠j and ZN∗=∪i=0d−1Di.Define two sets(9)P=p,2p,…,q−1p,Q=q,2q,…,p−1q.Then,(10)Zpq=∪i=0d−1Di∪P∪Q∪0.Lemma 2 (see [7]).
Let(11)d=gcdp−1,q−1=2,C0=0∪Q∪D0,C1=P∪D1.
And a new binary generalized cyclotomic sequenceS of order 2 is(12)si=0,ifi∈C0,1,ifi∈C1.
Letm=ordpq2 and α be a primitive pqth root of unity in finite field F2m, dix=∏j∈Dix−αi,i=0,1. Then,(1)
Whenp≡1mod8, q≡3mod8 or p≡−3mod8, q≡−1mod8,(13)LCS=pq−1,mx=xpq−1x−1.(2)
Whenp≡−1mod8, q≡3mod8 or p≡3mod8, q≡−1mod8,(14)LCS=p−1q,mx=xpq−1xq−1.(3)
Whenp≡−1mod8, q≡−3mod8 or p≡3mod8, q≡1mod8,(15)LCS=pq−p−q+1,mx=xpq−1x−1xp−1xq−1.(4)
Whenp≡1mod8, q≡−1mod8 or p≡−3mod8, q≡3mod8,(16)LCS=pq+p+q−32,mx=xpq−1x−1d0x.(5)
Whenp≡−1mod8, q≡1mod8 or p≡3mod8, q≡−3mod8,(17)LCS=p−1q−12,mx=d1x.(6)
Whenp≡−1mod8, q≡1mod8 or p≡3mod8, q≡3mod8,(18)LCS=p−1q+12,mx=xp−1d1xx−1.Lemma 3 (see [8]).
Let(19)d=gcdp−1,q−1=2,C0=0∪Q∪D0,C1=P∪D1.
And a binary generalized cyclotomic sequenceS of order 2 is defined by(20)si=0,ifi∈C0,1,ifi∈C1.
Then,(1)
Whenp−1q−1/4 is even,(21)CSw=q−p−3,w∈P,1+p−q,w∈Q,−1,w∈ZN∗.(2)
Whenp−1q−1/4 is odd,(22)CSw=q−p−3,w∈P,1+p−q,w∈Q,−3,w∈D0,1,w∈D1.Lemma 4 (see [9]).
Let(23)d=gcdp−1,q−1=4,C0=0∪Q∪D0∪D2,C1=P∪D1∪D3.
And a binary generalized cyclotomic sequenceS of order 4 is defined by(24)si=0ifi∈C0,1ifi∈C1.(1)
If2∈D0 or 2∈D2, then(25)LCS=p+1q−12.If2∈D1 or 2∈D3, then(26)LCS=pq−1.(2)
Whenp≡−1mod8, q≡3mod8 or p≡3mod8, q≡−1mod8,(27)CSw=pq,w∈0,q−p−3,w∈P,1+p−q,w∈Q,1,w∈D0∪D2,−3,w∈D1∪D3.Lemma 5 (see [10]).
Let(28)d=gcdp−1,q−1=2k,C0=0∪Q∪∪i=02k−1−1Di,C1=P∪∪i=2k−12k−1Di.
And a binary generalized cyclotomic sequenceS of order 2k is defined by(29)si=0,ifi∈C0,1,ifi∈C1.
Letm=ordpq2 and α be a pqth primitive root of unity in finite field F2m,(30)Six=∑j∈P∪∩t=2k−1+i2k−1+iDtxj,i=0,1,…,2k−1,Λ=ij:Sijα=0,j=0,1,…,2k−1−1.
Then,(1)
If for alls, gs≡2modpq is true,(31)LCS=p−1q,mx=xpq−1xq−1.(2)
When there existss such that gs≡2modpq,(32)LCS=p+1q−12,mx=xpq−1xp−1∏i∈Λdix,wheredix=∏j∈Dix−αj.
The following are Ding’s new cyclotomic classV0,V1.
Assumed=gcdp−1,q−1=2; let(33)V0=gsxl:0≤s≤e−1,0≤l≤d−1,2|s+l,V1=gsxl:0≤s≤e−1,0≤l≤d−1,2∤s+l.
With the above preparations, a partition ofZN∗ is(34)ZN∗=V0∪V1,
Then,(35)Zpq=V0∪V1∪P∪Q∪0.
Let(36)C0=0∪Q∪V0,C1=P∪V1.
And a binary generalized cyclotomic sequenceS with period pq constructed in [19] is(37)si=0,ifi∈C0,1,ifi∈C1.Lemma 6.
(see [19]). Let S=si be the binary sequences defined. Then, the autocorrelation of S is(38)CSw=pq−2p−2,w∈P,1+p−q−q−1ηw−1p−1/2+1,w∈Q,−q−q−2ηw−1p−1/2+1,w∈ZN∗.Lemma 7.
(see [19]). Let dix=∏j∈Vix−αi,i=0,1. Then,(1)
Whenp≡1mod8,(39)LCS=pq+q−p−12.(2)
Whenp≡−1mod8,(40)LCS=pq−p−q+12.(3)
Whenp≡3mod8,(41)LCS=pq−p−q+1.(4)
Whenp≡−3mod8,(42)LCS=pq−p.
Now, let(43)C0=0∪P∪V0,C1=Q∪V1.
A new binary cyclotomic sequenceS=si with period pq is defined by(44)si=0ifimodpq∈C0,1ifimodpq∈C1.


## 3. Main Results

### 3.1. Autocorrelation of Our New Sequences

Let(45)ηi=1ifiis the quadratic residue of modulep,−1ifiis not the quadratic residue of modulep.Lemma 8 (see [19]).
LetV0 and V1 be the sets defined above; then,(1)
2∈V0 if and only if p≡±1mod8(2)
2∈V1 if and only if p≡±3mod8Lemma 9 (see [19]).
LetV0 be the sets defined above; then, n∈V0 if and only if 1/21+ηn=1,0≤n≤N−1.Lemma 10.
Let1≤w≤N−1; then,(1)
∑i=0gcdi,pq=1gcdi+w,pq=1N−1ηii+w=q−2p−1,w∈P,1−q,w∈Q,2−q,w∈ZN∗.(2)
∑i=0gcdi,pq=1p|i+wN−1ηi=0,w∈P,q−1η−w,w∉P.(3)
∑i=0p|igcdi+w,pq=1N−1ηi+w=0,w∈P,q−1ηw,w∉P.(4)
∑i=0gcdi,pq=1q|i+w,pq∤i+wN−1ηi=−η−ww∈ZN∗,0w∉ZN∗,(5)
∑i=1q|igcdi+w,pq=1N−1ηi+w=−ηww∈ZN∗,0w∉ZN∗.(6)
∑i=0p|ip|i+wN−11=q,w∈P,0,w∉P.(7)
∑i=1q|ip|i+wN−11=0,w∈P,1,w∉P.(8)
∑i=0p|i,q|i+wpq∤i+wN−11=0,w∈P,1,w∉P.(9)
∑i=1q|i,q|i+wpq∤i+wN−11=p−2,w∈Q,0,w∉Q.Proof.
For the proof of (1) and (6)‒(9), one can refer to in [19]; we just prove (2)‒(5).(46)∑i=0gcdi,pq=1p|i+wN−1ηi=∑i=0gcdi,pq=1p|i+wN−1η−w=η−w∑i=0gcdi,pq=1p|i+wN−11=0,w∈P,q−1η−w,w∉P,∑i=0p|igcdi+w,pq=1N−1ηi+w=∑i=0p|igcdi+w,pq=1N−1ηw=ηw∑i=0p|igcdi+w,pq=1N−11=0,w∈P,q−1ηw,w∉P,∑i=0gcdi,pq=1q|i+w,pq∤i+wN−1ηi=∑i=0gcdi,pq=1q|i+wN−1ηi−∑i=0gcdi,pq=1q|i+w,pq|i+wN−1ηi=0−∑i=0gcdi,pq=1q|i+w,pq|i+wN−1η−w=−η−w∑i=0gcdi,pq=1q|i+w,pq|i+wN−11=−η−ww∈ZN∗,0w∉ZN∗,∑i=1q|igcdi+w,pq=1N−1ηi+w=∑i=0q|igcdi+w,pq=1N−1ηi+w−∑i=0q|igcdi+w,pq=1N−1ηi+w=0−∑i=0q|igcdi+w,pq=1N−1ηw=−ηw∑i=0q|igcdi+w,pq=1N−11=−ηww∈ZN∗,0w∉ZN∗.Theorem 1.
LetS=si be the new binary sequences defined in (44); then, the autocorrelation of S is(47)CSw=pq−2p+2,w∈P,p−q−3+q−1ηw−1p−1/2+1,w∈Q,−q+qηw−1p−1/2+1,w∈ZN∗.Proof.
By the definition ofS,(48)−1Sn=ηn,gcdn,pq=1,1,p|n,−1,q|n,n>0.
Let1≤w≤N−1; then,(49)CSw=∑i=0N−1−1si+w+si=∑i=0gcdi,pq=1gcdi+w,pq=1N−1ηii+w+∑i=0gcdi,pq=1p|i+wN−1ηi−∑i=0gcdi,pq=1q|i+w,pq∤i+wN−1ηi−∑i=1q|igcdi+w,pq=1N−1ηi+w−∑i=1q|ip|i+wN−11+∑i=1q|i,q|i+wpq∤i+wN−11+∑i=0p|igcdi+w,pq=1N−1ηi+w+∑i=0p|ip|i+wN−11−∑i=0p|i,q|i+wpq∤i+wN−11=pq−2p+2ifw∈P,p−q−3+q−1ηw−1p−1/2+1ifw∈Q,−q+qηw−1p−1/2+1ifw∈ZN∗.
The autocorrelation function of the new sequencesCSw is 5-level if p≡1mod4. CSw is 3-level.


### 3.2. Linear Complexity and Minimal Polynomial of Our New Sequences

Lemma 11.
(see [19]). Let V0 and V1 be the sets defined above; then,(50)tV0∈V0,tV1∈V1,ift∈V0,tV0∈V1,tV1∈V0,ift∈V1.
Denote(51)Sx=s0+s1x+s2x2+⋯+sN−1xN−1=∑i∈C1xi=∑i∈Qxi+∑i∈V1xi.Assumem=ordpq2 and α is a pqth primitive root of unity in finite field F2m. According to the Blahut theorem, the linear complexity of sequence S=si is(52)LCS=pq−t:Sαt=0,0≤t≤pq−1.Lemma 12.
Let1≤t≤N−1; then,(53)Sαt=Sα,t∈V0,1+Sα,t∈V1,p−12mod2,t∈P,1,t∈Q,0,t∈0.Proof.
Lett∈V0; then, by Lemma 11,(54)Sαt=∑i∈Qαti+∑i∈V1αti=∑i∈tQαi+∑i∈tV1αi=∑i∈Qαi+∑i∈V1αi=Sα.
Lett∈V1,(55)0=αpq−1=α−11+α+⋯+αpq−1=α−11+∑i∈V0αi+∑i∈V1αi+∑i∈Pαi+∑i∈Qαi.
Then, by Lemma11,(56)Sαt=∑i∈Qαti+∑i∈V1αti=∑i∈tQαi+∑i∈tV1αi=∑i∈Qαi+∑i∈V0αi=∑i∈Qαi−∑i∈V1αi+1≡Sα+1mod2.
Lett∈P; then,(57)V1modq=gsxlmodq:0≤s≤e−1,0≤l≤1,2∤s+l=g2sxmodq:0≤s≤e2−1∪g2s+1modq:0≤s≤e2−1=g2smodq:0≤s≤e2−1∪g2s+1modq:0≤s≤e2−1=1,2,…,q−1.
Whens runs through 0,1,…,e−1,l runs through 0,1, and 2∤s+l, the set V1modq takes on each element in 1,2,…,q−1 exactly p−1/2 times. Therefore,(58)Sαt=∑i∈Qαti+∑i∈V1αti=p−1mod2+p−12mod2∑i∈Pαi=p−12mod2.
Lett∈Q; then,(59)V1modp=gsxlmodp:0≤s≤e−1,0≤l≤1,2∤s+l=g2sxmodp:0≤s≤e2−1∪g2s+1modp:0≤s≤e2−1=g2s+1modp:0≤s≤e2−1=g1,g3,…,gp−2.
Whens runs through 0,1,…,e−1,l runs through 0,1, and 2∤s+l, the set V1modp takes on each element in g1,g3,…,gp−2 exactly q−1 times. Therefore,(60)Sαt=∑i∈Qαti+∑i∈V1αti=∑i∈Qαi+q−1mod2∑i∈g1,g3,…,gp−2αi=−1≡1mod2.
Lett∈0; then,(61)Sαt=S1=p−1+p−1q−12=p−1q+12mod2=0.Lemma 13.
LetV0 and V1 be the sets defined above; then, 2∈V0 if and only if Sα∈0,1.Proof.
Since the characteristic of finite fieldF2m is 2, Sα2=Sα2.
Let2∈V0; then, 2Vi=Vi,i=0,1.(62)Sα2=Sα2=∑i∈Qα2i+∑i∈V1α2i=∑i∈Qαi+∑i∈V1αi=Sα.
Therefore,Sα∈0,1.
Let2∈V1; then, 2Vi=Vi+1mod2,i=0,1.(63)Sα2=Sα2=∑i∈Qα2i+∑i∈V1α2i=∑i∈Qαi+∑i∈V0αi=Sα+1.
Therefore,Sα∉0,1.
Since2∉P∪Q, 2∈V0 if and only if Sα∈0,1.Theorem 2.
Letdix=∏j∈Vix−αi,i=0,1. Then,(1)
Whenp≡1mod8,(64)LCS=pq+p−q−12,mx=xpq−1xq−1dix.(2)
Whenp≡−1mod8,(65)LCS=pq+p+q−32,mx=xpq−1xq−1dix.(3)
Whenp≡3mod8,(66)LCS=pq−1,mx=xpq−1x−1.(4)
Whenp≡−3mod8,(67)LCS=pq−q,mx=xpq−1xq−1.Proof.
Letα be a pqth primitive root of unity in finite field F2m. Then,(68)xp−1=∏i∈0∪Qx−αi,xq−1=∏i∈0∪Px−αi.
Definedix=∏j∈Vix−αj,i=0,1. It can be easily seen that(69)xN−1=x−1x−α…x−αN−1=xp−1xq−1d0xd1xx−1.Case 1.
p≡1mod8: choose α such that Sα=0. Then,(70)Sαt=1,t∈Q∪V1,0,t∈0∪P∪V0.LCS=pq−q−p−1q−12=pq+p−q−12,mx=xpq−1xq−1d0x.Case 2.
p≡−1mod8: choose α such that Sα=0. Then,(71)Sαt=1,t∈P∪Q∪V1,0,t∈0∪V0,LCS=pq−1−p−1q−12=pq+p+q−32,mx=xpq−1x−1d0x.Case 3.
p≡3mod8. Then,(72)Sαt≠0,t∈P∪Q∪V0∪V1,=0,t∈0,LCS=pq−1,mx=xpq−1x−1.Case 4.
p≡−3mod8. Then,(73)Sαt≠0,t∈Q∪V0∪V1,=0,t∈0∪P,LCS=pq−q,mx=xpq−1xq−1.
The linear complexity of the new sequences isLCS>pq/2 if p≡1mod8, p>q+1, or p≡−1mod8; LCS=pq−q or pq−1 if p≡±3mod8, which is very close to period pq.
The following are some examples.Example 1.
Letp=7 and q=3. Then,(74)P=7,14,Q=3,6,9,12,15,18,V0=1,2,4,8,11,16,V1=5,10,13,17,19,20.
Our corresponding new binary sequence of period 21 is as follows: 000101100110110101111.
By using Magma, the autocorrelation value of the above sequence is 3-level, which is consistent with the casep≡3mod4 in Theorem 1. And the linear complexity of the above sequence is equal to 14, which is consistent with the case p≡−1mod8 in Theorem 2.Example 2.
Letp=11 and q=3. Then,(75)P=11,22,Q=3,6,9,12,15,18,21,24,27,30,V0=1,4,5,14,16,20,23,25,26,31,V1=2,7,8,10,13,17,19,28,29,32.
Our corresponding new binary sequence of period 33 is as follows: 001100111110110101110100100111101.
By using Magma, the autocorrelation value of the above sequence is 3-level, which is consistent with the casep≡3mod4 in Theorem 1. And the linear complexity of the above sequence is equal to 32, which is consistent with the case p≡3mod8 in Theorem 2.Example 3.
Letp=13 and q=3. Then,(76)P=13,26,Q=3,6,9,12,15,18,21,24,27,30,33,36,V0=1,4,10,14,16,17,22,23,25,29,35,38,V1=2,5,7,8,11,19,20,28,31,32,34,37.
Our corresponding new binary sequence of period 39 is as follows: 001101111101100100111100100110111110110.
By using Magma, the autocorrelation value of the above sequence is 5-level, which is consistent with the casep≡1mod4 in Theorem 1. And the linear complexity of the above sequence is equal to 36, which is consistent with the case p≡−3mod8 in Theorem 2.Example 4.
Letp=17 and q=3. Then,(77)P=17,34,Q=3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,V0=1,2,4,8,13,16,19,25,26,32,35,38,43,47,49,50,V1=5,7,10,11,14,20,22,23,28,29,31,37,40,41,44,46.
Our corresponding new binary sequence of period 51 is as follows: 000101110111101100101111100111110100110111101110100.
By using Magma, the linear complexity of the above sequence is equal to 32, which is consistent with the casep≡1mod8 in Theorem 1, but the autocorrelation value of the above sequence is 4-level, which is consistent with the case p≡1mod4 in Theorem 2.


### 3.3. Comparisons of Results

The comparisons of our results with [19] are listed in Tables 1 and 2.Table 1
Comparison of autocorrelationCSw.
CSwSequences of Liu and ChenNew sequencesw∈Ppq−2p−2pq−2p+2w∈Q1+p−q−q−1ηw−1p−1/2+1p−q−3+q−1ηw−1p−1/2+1w∈ZN∗−q−q−2ηw−1p−1/2+1−q+qηw−1p−1/2+1Table 2
Comparison of linear complexityLCS.
LCSSequences of Liu and ChenNew sequencesp≡1mod8pq−p+q−1/2pq+p−q−1/2p≡−1mod8p−1q−1/2pq+p+q−3/2p≡3mod8pq−p−q+1pq−1p≡−3mod8pq−ppq−qThe comparisons show the following:(i)
Whenp≡3mod4, the autocorrelation CSw of the two sequences is unequal, but they are 3-level. When p≡1mod4, the autocorrelation of the two sequences is unequal, but both of them are 5-level.(ii)
Whenp≡1mod4, p>q, or p≡3mod4, the linear complexity of our new sequences is larger.


## 3.1. Autocorrelation of Our New Sequences

Let(45)ηi=1ifiis the quadratic residue of modulep,−1ifiis not the quadratic residue of modulep.Lemma 8 (see [19]).
LetV0 and V1 be the sets defined above; then,(1)
2∈V0 if and only if p≡±1mod8(2)
2∈V1 if and only if p≡±3mod8Lemma 9 (see [19]).
LetV0 be the sets defined above; then, n∈V0 if and only if 1/21+ηn=1,0≤n≤N−1.Lemma 10.
Let1≤w≤N−1; then,(1)
∑i=0gcdi,pq=1gcdi+w,pq=1N−1ηii+w=q−2p−1,w∈P,1−q,w∈Q,2−q,w∈ZN∗.(2)
∑i=0gcdi,pq=1p|i+wN−1ηi=0,w∈P,q−1η−w,w∉P.(3)
∑i=0p|igcdi+w,pq=1N−1ηi+w=0,w∈P,q−1ηw,w∉P.(4)
∑i=0gcdi,pq=1q|i+w,pq∤i+wN−1ηi=−η−ww∈ZN∗,0w∉ZN∗,(5)
∑i=1q|igcdi+w,pq=1N−1ηi+w=−ηww∈ZN∗,0w∉ZN∗.(6)
∑i=0p|ip|i+wN−11=q,w∈P,0,w∉P.(7)
∑i=1q|ip|i+wN−11=0,w∈P,1,w∉P.(8)
∑i=0p|i,q|i+wpq∤i+wN−11=0,w∈P,1,w∉P.(9)
∑i=1q|i,q|i+wpq∤i+wN−11=p−2,w∈Q,0,w∉Q.Proof.
For the proof of (1) and (6)‒(9), one can refer to in [19]; we just prove (2)‒(5).(46)∑i=0gcdi,pq=1p|i+wN−1ηi=∑i=0gcdi,pq=1p|i+wN−1η−w=η−w∑i=0gcdi,pq=1p|i+wN−11=0,w∈P,q−1η−w,w∉P,∑i=0p|igcdi+w,pq=1N−1ηi+w=∑i=0p|igcdi+w,pq=1N−1ηw=ηw∑i=0p|igcdi+w,pq=1N−11=0,w∈P,q−1ηw,w∉P,∑i=0gcdi,pq=1q|i+w,pq∤i+wN−1ηi=∑i=0gcdi,pq=1q|i+wN−1ηi−∑i=0gcdi,pq=1q|i+w,pq|i+wN−1ηi=0−∑i=0gcdi,pq=1q|i+w,pq|i+wN−1η−w=−η−w∑i=0gcdi,pq=1q|i+w,pq|i+wN−11=−η−ww∈ZN∗,0w∉ZN∗,∑i=1q|igcdi+w,pq=1N−1ηi+w=∑i=0q|igcdi+w,pq=1N−1ηi+w−∑i=0q|igcdi+w,pq=1N−1ηi+w=0−∑i=0q|igcdi+w,pq=1N−1ηw=−ηw∑i=0q|igcdi+w,pq=1N−11=−ηww∈ZN∗,0w∉ZN∗.Theorem 1.
LetS=si be the new binary sequences defined in (44); then, the autocorrelation of S is(47)CSw=pq−2p+2,w∈P,p−q−3+q−1ηw−1p−1/2+1,w∈Q,−q+qηw−1p−1/2+1,w∈ZN∗.Proof.
By the definition ofS,(48)−1Sn=ηn,gcdn,pq=1,1,p|n,−1,q|n,n>0.
Let1≤w≤N−1; then,(49)CSw=∑i=0N−1−1si+w+si=∑i=0gcdi,pq=1gcdi+w,pq=1N−1ηii+w+∑i=0gcdi,pq=1p|i+wN−1ηi−∑i=0gcdi,pq=1q|i+w,pq∤i+wN−1ηi−∑i=1q|igcdi+w,pq=1N−1ηi+w−∑i=1q|ip|i+wN−11+∑i=1q|i,q|i+wpq∤i+wN−11+∑i=0p|igcdi+w,pq=1N−1ηi+w+∑i=0p|ip|i+wN−11−∑i=0p|i,q|i+wpq∤i+wN−11=pq−2p+2ifw∈P,p−q−3+q−1ηw−1p−1/2+1ifw∈Q,−q+qηw−1p−1/2+1ifw∈ZN∗.
The autocorrelation function of the new sequencesCSw is 5-level if p≡1mod4. CSw is 3-level.


## 3.2. Linear Complexity and Minimal Polynomial of Our New Sequences

Lemma 11.
(see [19]). Let V0 and V1 be the sets defined above; then,(50)tV0∈V0,tV1∈V1,ift∈V0,tV0∈V1,tV1∈V0,ift∈V1.
Denote(51)Sx=s0+s1x+s2x2+⋯+sN−1xN−1=∑i∈C1xi=∑i∈Qxi+∑i∈V1xi.Assumem=ordpq2 and α is a pqth primitive root of unity in finite field F2m. According to the Blahut theorem, the linear complexity of sequence S=si is(52)LCS=pq−t:Sαt=0,0≤t≤pq−1.Lemma 12.
Let1≤t≤N−1; then,(53)Sαt=Sα,t∈V0,1+Sα,t∈V1,p−12mod2,t∈P,1,t∈Q,0,t∈0.Proof.
Lett∈V0; then, by Lemma 11,(54)Sαt=∑i∈Qαti+∑i∈V1αti=∑i∈tQαi+∑i∈tV1αi=∑i∈Qαi+∑i∈V1αi=Sα.
Lett∈V1,(55)0=αpq−1=α−11+α+⋯+αpq−1=α−11+∑i∈V0αi+∑i∈V1αi+∑i∈Pαi+∑i∈Qαi.
Then, by Lemma11,(56)Sαt=∑i∈Qαti+∑i∈V1αti=∑i∈tQαi+∑i∈tV1αi=∑i∈Qαi+∑i∈V0αi=∑i∈Qαi−∑i∈V1αi+1≡Sα+1mod2.
Lett∈P; then,(57)V1modq=gsxlmodq:0≤s≤e−1,0≤l≤1,2∤s+l=g2sxmodq:0≤s≤e2−1∪g2s+1modq:0≤s≤e2−1=g2smodq:0≤s≤e2−1∪g2s+1modq:0≤s≤e2−1=1,2,…,q−1.
Whens runs through 0,1,…,e−1,l runs through 0,1, and 2∤s+l, the set V1modq takes on each element in 1,2,…,q−1 exactly p−1/2 times. Therefore,(58)Sαt=∑i∈Qαti+∑i∈V1αti=p−1mod2+p−12mod2∑i∈Pαi=p−12mod2.
Lett∈Q; then,(59)V1modp=gsxlmodp:0≤s≤e−1,0≤l≤1,2∤s+l=g2sxmodp:0≤s≤e2−1∪g2s+1modp:0≤s≤e2−1=g2s+1modp:0≤s≤e2−1=g1,g3,…,gp−2.
Whens runs through 0,1,…,e−1,l runs through 0,1, and 2∤s+l, the set V1modp takes on each element in g1,g3,…,gp−2 exactly q−1 times. Therefore,(60)Sαt=∑i∈Qαti+∑i∈V1αti=∑i∈Qαi+q−1mod2∑i∈g1,g3,…,gp−2αi=−1≡1mod2.
Lett∈0; then,(61)Sαt=S1=p−1+p−1q−12=p−1q+12mod2=0.Lemma 13.
LetV0 and V1 be the sets defined above; then, 2∈V0 if and only if Sα∈0,1.Proof.
Since the characteristic of finite fieldF2m is 2, Sα2=Sα2.
Let2∈V0; then, 2Vi=Vi,i=0,1.(62)Sα2=Sα2=∑i∈Qα2i+∑i∈V1α2i=∑i∈Qαi+∑i∈V1αi=Sα.
Therefore,Sα∈0,1.
Let2∈V1; then, 2Vi=Vi+1mod2,i=0,1.(63)Sα2=Sα2=∑i∈Qα2i+∑i∈V1α2i=∑i∈Qαi+∑i∈V0αi=Sα+1.
Therefore,Sα∉0,1.
Since2∉P∪Q, 2∈V0 if and only if Sα∈0,1.Theorem 2.
Letdix=∏j∈Vix−αi,i=0,1. Then,(1)
Whenp≡1mod8,(64)LCS=pq+p−q−12,mx=xpq−1xq−1dix.(2)
Whenp≡−1mod8,(65)LCS=pq+p+q−32,mx=xpq−1xq−1dix.(3)
Whenp≡3mod8,(66)LCS=pq−1,mx=xpq−1x−1.(4)
Whenp≡−3mod8,(67)LCS=pq−q,mx=xpq−1xq−1.Proof.
Letα be a pqth primitive root of unity in finite field F2m. Then,(68)xp−1=∏i∈0∪Qx−αi,xq−1=∏i∈0∪Px−αi.
Definedix=∏j∈Vix−αj,i=0,1. It can be easily seen that(69)xN−1=x−1x−α…x−αN−1=xp−1xq−1d0xd1xx−1.Case 1.
p≡1mod8: choose α such that Sα=0. Then,(70)Sαt=1,t∈Q∪V1,0,t∈0∪P∪V0.LCS=pq−q−p−1q−12=pq+p−q−12,mx=xpq−1xq−1d0x.Case 2.
p≡−1mod8: choose α such that Sα=0. Then,(71)Sαt=1,t∈P∪Q∪V1,0,t∈0∪V0,LCS=pq−1−p−1q−12=pq+p+q−32,mx=xpq−1x−1d0x.Case 3.
p≡3mod8. Then,(72)Sαt≠0,t∈P∪Q∪V0∪V1,=0,t∈0,LCS=pq−1,mx=xpq−1x−1.Case 4.
p≡−3mod8. Then,(73)Sαt≠0,t∈Q∪V0∪V1,=0,t∈0∪P,LCS=pq−q,mx=xpq−1xq−1.
The linear complexity of the new sequences isLCS>pq/2 if p≡1mod8, p>q+1, or p≡−1mod8; LCS=pq−q or pq−1 if p≡±3mod8, which is very close to period pq.
The following are some examples.Example 1.
Letp=7 and q=3. Then,(74)P=7,14,Q=3,6,9,12,15,18,V0=1,2,4,8,11,16,V1=5,10,13,17,19,20.
Our corresponding new binary sequence of period 21 is as follows: 000101100110110101111.
By using Magma, the autocorrelation value of the above sequence is 3-level, which is consistent with the casep≡3mod4 in Theorem 1. And the linear complexity of the above sequence is equal to 14, which is consistent with the case p≡−1mod8 in Theorem 2.Example 2.
Letp=11 and q=3. Then,(75)P=11,22,Q=3,6,9,12,15,18,21,24,27,30,V0=1,4,5,14,16,20,23,25,26,31,V1=2,7,8,10,13,17,19,28,29,32.
Our corresponding new binary sequence of period 33 is as follows: 001100111110110101110100100111101.
By using Magma, the autocorrelation value of the above sequence is 3-level, which is consistent with the casep≡3mod4 in Theorem 1. And the linear complexity of the above sequence is equal to 32, which is consistent with the case p≡3mod8 in Theorem 2.Example 3.
Letp=13 and q=3. Then,(76)P=13,26,Q=3,6,9,12,15,18,21,24,27,30,33,36,V0=1,4,10,14,16,17,22,23,25,29,35,38,V1=2,5,7,8,11,19,20,28,31,32,34,37.
Our corresponding new binary sequence of period 39 is as follows: 001101111101100100111100100110111110110.
By using Magma, the autocorrelation value of the above sequence is 5-level, which is consistent with the casep≡1mod4 in Theorem 1. And the linear complexity of the above sequence is equal to 36, which is consistent with the case p≡−3mod8 in Theorem 2.Example 4.
Letp=17 and q=3. Then,(77)P=17,34,Q=3,6,9,12,15,18,21,24,27,30,33,36,39,42,45,48,V0=1,2,4,8,13,16,19,25,26,32,35,38,43,47,49,50,V1=5,7,10,11,14,20,22,23,28,29,31,37,40,41,44,46.
Our corresponding new binary sequence of period 51 is as follows: 000101110111101100101111100111110100110111101110100.
By using Magma, the linear complexity of the above sequence is equal to 32, which is consistent with the casep≡1mod8 in Theorem 1, but the autocorrelation value of the above sequence is 4-level, which is consistent with the case p≡1mod4 in Theorem 2.


## 3.3. Comparisons of Results

The comparisons of our results with [19] are listed in Tables 1 and 2.Table 1
Comparison of autocorrelationCSw.
CSwSequences of Liu and ChenNew sequencesw∈Ppq−2p−2pq−2p+2w∈Q1+p−q−q−1ηw−1p−1/2+1p−q−3+q−1ηw−1p−1/2+1w∈ZN∗−q−q−2ηw−1p−1/2+1−q+qηw−1p−1/2+1Table 2
Comparison of linear complexityLCS.
LCSSequences of Liu and ChenNew sequencesp≡1mod8pq−p+q−1/2pq+p−q−1/2p≡−1mod8p−1q−1/2pq+p+q−3/2p≡3mod8pq−p−q+1pq−1p≡−3mod8pq−ppq−qThe comparisons show the following:(i)
Whenp≡3mod4, the autocorrelation CSw of the two sequences is unequal, but they are 3-level. When p≡1mod4, the autocorrelation of the two sequences is unequal, but both of them are 5-level.(ii)
Whenp≡1mod4, p>q, or p≡3mod4, the linear complexity of our new sequences is larger.


## 4. Conclusion

This paper presents a construction of generalized cyclotomic binary sequences with periodpq based on Ding’s new cyclotomic class V0,V1. And the autocorrelation value, linear complexity, and minimal polynomial of our new sequences are determined. The autocorrelation function CSw is 5-level if p≡1mod4. CSw is 3-level, and S has almost optimal autocorrelation if p≡3mod4. The linear complexity LCS>pq/2 if p≡1mod8, p>q+1, or p≡−1mod8; LCS=pq−q or pq−1 if p≡±3mod8, which is very close to the period. The results show that our new sequences have quite good cryptographic properties in the aspect of autocorrelation and linear complexity.



---

*Source: 5535887-2021-04-26.xml*