# A Kind of Quaternary Sequences of Period2pmqn and Their Linear Complexity

Authors: Qiuyan Wang; Chenhuang Wu; Minghui Yang; Yang Yan
Journal: Complexity
 (2020)

---

## Abstract

Sequences with high linear complexity have wide applications in cryptography. In this paper, a new class of quaternary sequences overF4 with period 2pmqn is constructed using generalized cyclotomic classes. Results show that the linear complexity of these sequences attains the maximum.


---

## Body

## 1. Introduction

Stream ciphers divide the plain text into characters and encipher each character with a time-varying function. It is known that the stream cipher plays a dominant role in cryptographic practice and remains a crucial role in military and commercial secrecy systems. The security of stream ciphers now depends on the “randomness” of the key stream [1]. For the system to be secure, the key stream must have a series of properties: balance, long period, low correlation, and so on.A necessary requirement for unpredictability is a large linear complexity of the key stream, which is defined to be the length of the shortest linear-feedback shift register able to produce the key stream. 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 T such that sj+T=sj for all j≥0. Let S=si be a periodic sequence over Fl. The linear complexity of S, denoted by LCS, is the least integer L of a linear recurrence relation over Fl satisfied by S:(1)−c0si+L=c1si+L−1+⋯+cLsi,fori≥0,where c0≠0 and c0,c1,…,cL−1,cL∈Fl. By B-M algorithm [2], if LCS≥N/2 (N is the least period of S), then S is considered to be good from the viewpoint of linear complexity.Periodic sequences have been intensively studied in the past few years since they are widely used in CDMA (code-division multiple access), global position systems, and stream ciphers. As special cases, cyclotomic and generalized cyclotomic sequences of different periods and orders have attracted many researchers to deeply explore due to their good pseudorandom cryptographic properties [3–5]. In particular, the linear complexity of Legendre sequences and cyclotomic sequences of order r was studied in [6, 7], respectively. Generalized cyclotomy, as a natural generalization of cyclotomy, was presented by Whiteman [8] and Ding and Helleseth [9]. It should be noted that Whiteman’s generalized cyclotomy is not in accordance with the classic cyclotomy. Ding–Helleseth cyclotomy includes the classic cyclotomy as a special case. Whereafter, the linear complexity of generalized cyclotomic sequences has been determined [10–15].Quaternary sequences are also important from the point of many practical applications; please refer to [16]. Owing to the nice algebraic structure, quaternary sequences also have received a lot of attention. For instance, a kind of almost quaternary cyclotomic sequences was defined in [17] and was proved to have an ideal autocorrelation property [17]. A new class of quaternary sequences of length pq, constructed by the inverse Gray mapping, was studied in [18]. A family of quaternary sequences of period 2p over F4 was presented and showed to possess high linear complexity [19].Motivated by the idea in [20, 21], we constructed a new class of quaternary sequences over F4 with period 2pmqn by using the generalized cyclotomic classes in this paper. From the definition of S in (11), we can easily see that the newly proposed sequences have longer period contrast to those in [21]. The linear complexity of these sequences is computed, and the results show that the proposed sequences have high linear complexity.This paper is organized as follows. In Section2, the periodic sequence S with period 2pmqn is given. Section 3 determines the linear complexity of the constructed sequence. Finally, we give some remarks on this paper.


## 2. Preliminaries

For a positive integera≥2, use ℤa to denote the ring ℤa=0,1,2,…,a−1 with integer addition modulo a and integer multiplication modulo a. Usually, we use ℤa∗ to denote all invertible elements of ℤa, i.e., all elements b in ℤa satisfying gcda,b=1. Obviously, the group ℤa∗ has cardinality ϕa, where ϕ⋅ denotes the Euler function.For a subsetA⊂ℤa and an element b∈ℤa, define(2)b+A=A+b=a+b:a∈A,bA=ab:a∈A,where addition and multiplication refer to those in ℤa.Letp and q be two distinct odd primes. Let m and n denote two positive integers. Suppose that g1 is a primitive element of ℤp2∗. Then, g1 is a primitive root of ℤpm∗ for m≥1 [22]. Without loss of generality, assume g1 is an odd integer. It is known that g1 is also a primitive root of ℤ2pm∗ [22]. Obviously, g1 is a common primitive root of ℤpi and ℤ2pi for all 1≤i≤m. By the same argument, there exists an integer g2 such that g2 is a common primitive root of ℤqj and ℤ2qj for any 1≤j≤n.Lemma 1 (see [23]).
Letm1,…,mt be positive integers. For a set of integers a1,…,at, the system of congruences(3)x≡aimodmi,i=1,…,t,has solutions if and only if(4)ai≡ajmod gcdmi,mj,i≠j,1≤i,j≤t.
If (4) is satisfied, the solution is unique modulo lcmm1,…,mt.Letg be the unique solution of the following congruence equations:(5)g≡g1mod2pm,g≡g2mod2qn.Lemma1 guaranteed the existence and uniqueness of the common primitive root g of pi, 2pi, pj, and 2pj. Similarly, there exists a unique integer y satisfying the following system of congruences:(6)y≡gmod2pm,y≡1mod2qn.Assume thatei,j=gcdpi−1p−1,qj−1q−1 and di,j=p−1pi−1q−1qj−1/ei,j. Then, di,j is the least positive integer that satisfies gdi,j≡1modpiqj ([9], Lemma 2), i.e., ordpiqjg=di,j. In the sequel, let i and j be two integers with 1≤i≤m and 1≤j≤n. The generalized cyclotomic classes with respect to piqj, similar to Ding–Helleseth’s generalized cyclotomic classes ([9]), are defined as follows:(7)D0piqj=g2tykmodpiqj:t=0,1,…,di,j2−1;k=0,1,…,ei,j−1,(8)D1piqj=gD0piqjmodpiqj.By Lemma 7 in [8], we get ℤpiqj∗=D0piqj∪D1piqj. Let(9)D02piqj=g2tykmod2piqj:t=0,1,…,di,j2−1;k=0,1,…,ei,j−1,D12piqj=gD02piqjmod2piqj.Similarly, we haveℤ2piqj∗=D02piqj∪D12piqj. For abbreviation, denote Hh2piqj=pm−iqn−jDh2piqj and Hhpiqj=pm−iqn−jDhpiqj for h=0,1. With the above preparations, we get a partition of ℤ2pmqn as follows:(10)ℤ2pmqn=∪i=1m∪j=1n∪h=01pm−iqn−jDh2piqj∪2Dhpiqj∪j=1n∪h=01pmqn−jDh2qj∪2Dhqj∪i=1m∪h=01pm−iqnDh2pi∪2Dhpi∪0,pmqn.LetF4=0,1,α,α2 be the finite field with 4 elements, where α satisfies α2=α+1. A class of quaternary sequence can be given by allocating each elements of F4 to each generalized cyclotomic class with respect to 2pmqn. To ensure the constructed sequence has high linear complexity, we should technologically do with it.Leta,b,c,d be a set of four tuples over F4, and the elements in these tuples are pairwise distinct. A quaternary generalized cyclotomic sequence S=si of period 2pmqn is defined as(11)si=0,ifi=0,e,ifi=pmqn,a,ifi∈∪i=1m∪j=1nH02piqj∪i=1mH02pi∪j=1nH02qj,b,ifi∈∪i=1m∪j=1nH12piqj∪i=1mH12pi∪j=1nH12qj,c,ifi∈∪i=1m∪j=1n2H0piqj∪i=1m2H0pi∪j=1n2H0qj,d,ifi∈∪i=1m∪j=1n2H1piqj∪i=1m2H1pi∪j=1n2H1qj,where e≠b+d and e∈F4∗ if p≡±1mod8 and e∉b,b+c and e∈F4∗ if p≡±3mod8. It is easily seen that the sequence S=si is balanced.


## 3. Linear Complexity of the Constructed Sequences

In generating running keys, the linear feedback shift register (LFSR) is one of the most useful devices. Also, it is shown that every periodic sequence can be generated by using LFSR. For researchers, what they most concern is the shortest length of LFSR that could produce a given sequenceS, which is referred to the linear complexity of S.LetS=si be a periodic sequence over the finite field Fl of period N. We first recall the definition of linear complexity of periodic sequences that is given in Section 1. The linear complexity of S over Fl, denoted by LCS, is the smallest positive integer L satisfying the following linear recurrence relation:(12)−c0si+L=c1si+L−1+⋯+cLsi,fori≥0,where c0≠0 and c0,c1,…,cL−1,cL∈Fl. The polynomial(13)cx=cLxL+cL−1xL−1+⋯+c1x+c0∈Flx,associated with the linear recurrence relation (12) is called the characteristic polynomial of S. A characteristic polynomial with the smallest degree is called a minimal polynomial of S [2]. For the periodic sequence S, let Sx=s0+s1x+⋯+sN−1xN−1∈Flx, which is called the generating polynomial of S. The following lemma gives a method to compute the linear complexity of S by using the generating polynomial Sx.Lemma 2 (see [24]).
Let S be a sequence overFl of period N. Then, the minimal polynomial mx of S is(14)mx=xN−1gcdxN−1,Sx,and the linear complexity LCS of S is given by(15)N−deggcdxN−1,Sx,where Sx is the generating polynomial of S.Lemma 3 (Lemma2, [10] and Lemma 1, [20]).
Let notations be defined as above. Then, for1≤i≤m and h=0,1, we have(16)Dhpi=x+py:x∈Dhp,y∈ℤpi−1,Dh2pi=x+py+δx,y:x∈Dhp,y∈ℤpi−1,where(17)δx,y=0,ifx+pyisodd,pi,otherwise.For the generalized cyclotomic classesDhpiqj and Dh2piqj corresponding to piqj and 2piqj, we have the following lemma.Lemma 4 (Lemma1, [25]).
For1≤i≤m and 1≤j≤n, we have(18)Dhpiqj=a+pqb:a∈Dhpq,b∈ℤpi−1qj−1,Dh2piqj=a+pqb+δa,b:a∈Dhpq,b∈ℤpi−1qj−1,where(19)δa,b=0,ifa+bpqisodd,piqj,otherwise.Lemma 5 (see [9]).
2
∈
D
h
p if and only if 2∈Dhpi for 1≤i≤m and h=0,1.Lemma 6 (see [22]).
Let symbols be the same as before. Then, we have(20)2∈D0pifandonlyifp≡±1mod8,2∈D1pifandonlyifp≡±3mod8.Lemma 7.
Let symbols be the same as before. Then, we have(21)2∈D0pqifandonlyifq≡±1mod8,2∈D1pqifandonlyifq≡±3mod8.Proof.
We only prove the first part of this lemma.Sufficiency.
Sincegcd2,pq=1, then 2∈ℤpq∗. If q≡±1mod8, by Lemma 6, 2∈D0q. Since D0q⊆D0pq, we get 2∈D0pq.Necessity.
If2∈D0pq, by the definitions of y in (6) and D0pq in (7), we know 2modq∈D0q. It follows from Lemma 6 that q≡±1mod8.
By the method analogous to that used above, we can get the second conclusion of this lemma.
Letd=ordpmqn (8). Assume that β is a primitive pmqnth root of unity in F4d. It can be easily checked that(22)xpmqn−1=x−1x−β…x−βpmqn−1.
By Lemma2, in order to determine the linear complexity of S, we need to determine gcdx2pmqn−1,Sx=gcdxpmqn−12,Sx over F4x. By (22), we should check whether βi, 0≤i≤pmqn−1, is a root of Sx. If it is a root of Sx, we need to verify whether it is a multiple root of Sx.
Recall thatHh2piqj=pm−iqn−jDh2piqj and Hhpiqj=pm−iqn−jDhpiqj for h=0,1. Define(23)Shi,jx=∑t∈Hh2piqjxt,Shi,0x=∑t∈Hh2pixt,Sh0,jx=∑t∈Hh2qjxt,for 1≤i≤m, 1≤j≤n, and 0≤h≤1. Let a and b be two integers with 0≤a≤m−1 and 0≤b≤n−1. For 1≤k≤pmqn−1, suppose k=paqbl with gcdl,pq=1. It follows from Lemma 4 that(24)Shi,jβk=∑t∈pm−iqn−jDh2piqjβkt=∑t∈pm+a−iqn+b−jlDh2piqjβt=∑t∈pm+a−iqn+b−jlDhpiqjβt=∑t∈Hhpiqjβkt.
Similarly, we have(25)Shi,0βk=∑t∈Hhpiβkt,(26)Sh0,jβk=∑t∈Hhqjβkt.
Combining (24)–(26), we have(27)Sβk=∑i=0pmqn−1sixi=eβpmqn+a∑i=1m∑j=1nS0i,jβk+∑i=1mS0i,0βk+∑j=1nS00,jβk+b∑i=1m∑j=1nS1i,jβk+∑i=1mS1i,0βk+∑j=1nS10,jβk+c∑i=1m∑j=1nS0i,jβk+∑i=1mS0i,0βk+∑j=1nS00,jβk2+d∑i=1m∑j=1nS1i,jβk+∑i=1mS1i,0βk+∑j=1nS10,jβk2.
Let(28)Aβk=∑i=1m∑j=1nS0i,jβk+∑i=1mS0i,0βk+∑j=1nS00,jβk.
Then,(29)Aβk=∑i=1m∑j=1n∑t∈pm−iqn−jD0piqjβkt+∑i=1m∑t∈qnpm−iD0piβkt+∑j=1n∑t∈pmqn−jD0qjβkt=∑i=1m∑j=1n∑t∈pm+a−iqn+b−jlD0piqjβt+∑i=1m∑t∈pm−i+aqn+blD0piβt+∑j=1n∑t∈pm+aqn+b−jlD0qjβt.
We first compute(30)S0i,jβk=∑t∈pm+a−iqn+b−jlD0piqjβt,where k=paqbl and gcdpq,l=1. The computation is divided into the following cases.Case 1:i≤a and j≤b. With simple derivation, we have(31)S0i,jβk=D0piqj=p−1q−1pi−1qj−12.Case 2:i=a+1andj=b+1. Then,(32)S0i,jβk=∑t∈D0pqζpqlt,whereζpq=βpm−1qn−1 is a pqth primitive root of unity.Case 3:i>a+1 or j>b+1. Let η=βpm+a−iqn+b−j, then ηpq≠1. It follows from Lemma 4 that(33)S0i,jβk=∑t∈D0piqjηt=∑t1∈D0pqηt1∑t2∈ℤpi−1qj−1ηpqt2=0.Case 4:i≤a and j=b+1. Let ζq=βpm+a−iqn−1, then ζq is a qth primitive root of unity. Hence, we obtain(34)S0i,jβk=∑t∈pm+a−iqn+b−jlD0piqjβt=∑t∈pm+a−iqn−1lD0piqb+1βt=∑t∈lD0piqb+1ζqt=p−1pi−1qb∑t∈lD0qζqt=0.Case 5:i=a+1andj≤b. By Lemma 4, we get(35)S0i,jβk=∑t∈pm+a−iqn+b−jlD0piqjβt=∑t∈pm−1qn+b−jlD0piqjβt=∑t∈lD0pa+1qbζpt=q−1paqj−12∑t∈ℤp∗ζpt=q−1paqj−12,whereζp=βpm−1qn+b−j.
From the above discussions, we have proved the first part of the following lemma.Lemma 8.
Fork=paqbl with gcdl,pq=1,0≤a≤m−1,and0≤b≤n−1, we have(36)S0i,jβk=p−1q−1pi−1qj−12,ifi≤aandj≤b,∑t∈D0pqζpqlt,ifi=a+1andj=b+1,0,ifi>a+1orj>b+1,0,ifi≤aandj=b+1,q−12,ifi=a+1andj≤b,(37)S1i,jβk=p−1q−1pi−1qj−12,ifi≤aandj≤b,∑t∈D1pqζpqlt,ifi=a+1andj=b+1,0,ifi>a+1orj>b+1,0,ifi≤aandj=b+1,q−12,ifi=a+1andj≤b,where ζpq=βpm−1qn−1 is a pqth primitive root of unity and β is a pmqnth primitive root of unity.Proof.
The proof of the second conclusion of this lemma is similar to the first part and we omit it.Lemma 9.
Fork=paqbl with gcdpq,l=1, we obtain(38)S0i,0βk=pi−1p−12,ifi≤a,∑t∈D0pζplt,ifi=a+1,0,ifi>a+1,(39)S1i,0βk=p−1pi−12,ifi≤a,∑t∈D1pζplt,ifi=a+1,0,ifi>a+1,(40)S00,jβk=q−1qj−12,ifj≤b,∑t∈D0qζqlt,ifj=b+1,0,ifj>b+1,(41)S10,jβk=q−1qj−12,ifj≤b,∑t∈D1qζqlt,ifj=b+1,0,ifj>b+1,where ζp=βpm−1qn+b and ζq=βpm+aqn−1.Proof.
Because (38)–(41) can be proved in a similar way, here we only prove (38). By notations and (25), we get(42)S0i,0βk=∑t∈pm−iqnD02piβkt=∑t∈pm+a−iqn+blD0piβt,where k=paqbl with gcdpq,l=1.
Ifi≤a, for each t∈pm+a−iqn+blD0pi, it can be easily seen that βt=1. Thus,(43)S0i,0βk=D0pi=pi−1p−12.
Ifi=a+1, then βpm−1qn+b is a pth primitive root of unity and(44)S0i,0βk=∑t∈D0pζplt,where ζp=βpm−1qn+b.
Ifi>a+1, we have βpm+a−iqn+bp≠1 and βpm+a−iqn+bpi=1. By Lemma 3, we know(45)D0pi=x+py:x∈D0p,y∈ℤpi−1.
Therefore,(46)S0i,0βk=∑t∈D0piηt=∑t1∈D0pηt1∑t2∈ℤpi−1ηt2p=∑t1∈D0pηt1⋅0=0,where η=βpm+a−iqn+bl and ηp≠1.
In the following, we will determine the terms witha,b,c,d as coefficients in (27), respectively.
First, we compute the terms witha as coefficient.
It follows from Lemmas8 and 9 that(47)a∑i=1m∑j=1nS0i,jβk+∑i=1mS0i,0βk+∑j=1nS00,jβka∑i=1m∑j=1bS0i,jβk+∑i=1m∑j=b+1S0i,b+1βk+∑i=1m∑j>b+1S0i,jβk+∑i=1aS0i,0βk+∑i=a+1S0a+1,0βk+0+qj−1q−12+∑t∈D0qζqltaq−12+q−1qj−12+pi−1p−12+∑t∈D0pqζpqlt+∑t∈D0pζplt+∑t∈D0qζqltap−12+∑t∈D0pqζpqlt+∑t∈D0pζplt+∑t∈D0qζqlt.
Similarly, we compute the terms withb as coefficients:(48)b∑i=1m∑j=1bS1i,jβk+∑i=1m∑j=b+1S1i,b+1βk+0+pi−1p−12+∑t∈D1pζplt+0+qj−1q−12+∑t∈D1qζqlt+0=bp−12+∑t∈D1pqζpqlt+∑t∈D1pζplt+∑t∈D1qζqlt.
The terms withc as coefficient are(49)cp−122+∑t∈D0pqζpq2lt+∑t∈D0pζp2lt+∑t∈D0qζq2lt.
The terms withd as coefficient are(50)dp−122+∑t∈D1pqζpq2lt+∑t∈D1pζp2lt+∑t∈D1qζq2lt.
It can be easily checked that(51)S1=e+a+b+c+dp−1q−1pi−1qj−1+p−1pi−1+q−1qj−12.=e≠0.
Next, we determineSβk according to the values of p and q, where k=paqbl with gcdpq,l=1.(1)
Ifp≡±1mod8 and q≡±1mod8, by Lemmas 6 and 7 we know 2∈D0pq, 2∈D0p, and 2∈D0q. Hence,(52)Sβk=e+p−12a+b+c+d+a+c∑t∈D0pqζpqlt+b+d∑t∈D1pqζpqlt+a+c∑t∈D0pζplt+b+d∑t∈D1pζplt+a+c∑t∈D0qζqlt+b+d∑t∈D1qζqlt=e+b+d.(2)
Ifp≡±3mod8 and q≡±1mod8, then 2∈D0pq, 2∈D0q, and 2∈D1p. Hence,(53)Sβk=e+a+c∑t∈D0pqζpqlt+b+d∑t∈D1pqζpqlt+a+c∑t∈D0qζqlt+b+d∑t∈D1qζqlt+a+c+d∑t∈D1pζplt+b1+∑t∈D1pζplt=e+b.(3)
Ifp≡±1mod8 and q≡±3mod8, then 2∈D1pq, 2∈D1q, and 2∈D0p. Hence,(54)Sβk=e+a+d∑t∈D0pqζpqlt+b+c∑t∈D1pqζpqlt+a+c∑t∈D0pζplt+b+d∑t∈D1pζplt+a+d∑t∈D0qζqlt+b+c∑t∈D1qζqlt=e+b+d.(4)
Ifp≡±3mod8 and q≡±3mod8, then 2∈D1pq, 2∈D1q, and 2∈D1p. Hence,(55)Sβk=e+a+d∑t∈D0pqζpqlt+b+c∑t∈D1pqζpqlt+a+d∑t∈D0pζplt+b+c∑t∈D1pζplt+a+d∑t∈D0qζqlt+b+c∑t∈D1qζqlt+a+d=e+b+c.
From the choice ofe, we know e≠b+d if p≡±1mod8 and e∉b,b+c if p≡±3mod8. By Lemma 2 and the above discussions, we obtain LCS=2pmqn.Theorem 1.
LetS=si be the quaternary sequence defined by (11). Then, the linear complexity of S is 2pmqn.Example 1.
Letp,q,m,n=3,5,1,1 and a,b,c,d,e=α,1+α,1,0,1. Then,(56)D02pq∪qD02p∪D02q=1,3,5,11,19,27,29,D12pq∪qD12p∪pD12q=7,9,13,17,21,23,25,2D0pq∪2qD0p∪2pD0q=2,6,8,10,22,24,28,2D12pq∪2qD0p∪2pD0q=4,12,14,16,18,20,26.
It can be checked by Magma thatgcdx15−1,Sx=1 and LCS=30.Example 2.
Letp,q,m,n=3,7,1,1 and a,b,c,d,e=α,1+α,1,0,1. Then,(57)D02pq∪qD02p∪D02q=1,3,7,11,23,25,27,29,33,37.D12pq∪qD12p∪pD12q=5,9,13,15,17,19,31,35,39,41.2D0pq∪2qD0p∪2pD0q=2,4,6,8,12,14,16,22,24,32.2D12pq∪2qD0p∪2pD0q=10,18,20,26,28,30,34,36,38,40.
It can be checked by Magma thatgcdx21−1,Sx=1 and LCS=42.Remark 1.
For1≤k≤pmqn−1, let k=paqbl with gcdl,ab=1. In the case that e=b+d∈F4∗ if p≡±1mod8 and the case that e∈b,b+c if p≡±3mod8, we know Sβk=0 for 1≤k≤pmqn−1. Hence, we need to check if βk is a multiple root of Sx. This means we should check if βk is a root of the derivation polynomial S′x of the generating polynomial Sx of S. By definitions, we have(58)βkS′βk=e+b+a+b∑t∈D0pqζpqlt+a+b∑t∈D0pζplt+a+b∑t∈D0qζqlt,and(59)βkS′βk=e+a+b∑t∈D0pqζpqlt+a+b∑t∈D0pζplt+a+b∑t∈D0qζqlt,respectively.
For the fixeda and b with 0≤a≤m−1 and 0≤b≤n−1, by the following equations,(60)∑t∈D0pqζpqt+∑t∈D1pqζpqt=1,∑t∈D0pζpt+∑t∈D1pζpt=1,∑t∈D0qζqt+∑t∈D1qζqt=1,we know there are at least 1/2ϕ2pm−aqn−b=p−1q−1/2pm−a−1qn−b−1 many k′s satisfying S′βk≠0. Hence, Sβk will have at most(61)pmqn−1+∑a=0m∑b=0np−1q−1pm−a−1qn−b−12=3pmqn−pm−qn−12,roots for 0≤k≤pmqn−1. By Lemma 2, we obtain(62)LCS≥2pmqn−3pmqn−pm−qn−12=pm+1qn+12.



---

*Source: 5129450-2020-03-17.xml*