# Linear Complexity of a New Class of Quaternary Generalized Cyclotomic Sequence with Period2pm

Authors: Pinhui Ke; Yan Zhong; Shengyuan Zhang
Journal: Complexity
 (2020)

---

## Abstract

Sequences with high linear complexity property are of importance in applications. In this paper, based on the theory of generalized cyclotomy, new classes of quaternary generalized cyclotomic sequences with order 4 and period2pm are constructed. In addition, we determine their linear complexities over finite field F4 and over ℤ4, respectively.


---

## Body

## 1. Introduction

Pseudorandom sequence has a wide range of applications in the spread spectrum communication, radar navigation, code division multiple access, stream cipher, and so on [1]. The linear complexity Lsu of a sequence su is defined as the smallest order of linear feedback shift register (LFSR) that can generate the whole sequence. According to Berlekamp–Massey algorithm [2], if the linear complexity of the sequence is l, then 2l consecutive terms of the sequence can be used to restore the whole sequence. Hence, a “high” linear complexity Lsu should be no less than one half of the length (or minimum period) of the sequence [3]. For cryptographic applications, sequences with high linear complexity are required.Sequences with high linear complexity can be constructed based on cyclotomic classes. Generally, sequences based on classical cyclotomic classes and generalized cyclotomic classes are called classical cyclotomic sequences and generalized cyclotomic sequences, respectively. There are lots of works on linear complexity of binary cyclotomic sequences, see [4–7], for instance. Recently, Xiao et al. presented a new class of cyclotomic binary sequences of period p2 and determined the linear complexity of the sequences in the case of f=2r for a positive integer r and showed that the sequences have large linear complexity if p is a non-Wieferich prime [8]. Moreover, Edemskiy et al. examined the linear complexity of sequences and extended the result to more general even integers f [9]. At the same time, the results were also generalized by Ye and Ke in [10] by considering a new construction with a flexible support set, which includes the original construction as a special case. Very recently, in [11], Ouyang and Xie extended the construction to the case of 2pm and showed that the constructed sequences have high linear complexity when m≥2.Compared with the binary case, less attention has been paid to quaternary sequences with high linear complexity. In [12], Kim et al. constructed a class of generalized cyclotomic sequences with period 2p over ℤ4 and analyzed the autocorrelation properties of these sequences. In [13], Chen and Edemskiy determined the linear complexity of these sequences over ℤ4. In [14], Du and Chen defined a family of quaternary sequences over F4 of period 2p using generalized cyclotomic classes over the residue class ring modulo 2p. They determined the linear complexities of the sequences and then showed that the sequences have large linear complexity. The autocorrelation values of the sequences were further studied in [15]. In [16], Ke et al. generalized the construction of [14] to the case of 2pm. They proved that the constructed sequences are balanced and also possess high linear complexity. Recently, in [17], Liu et al. further extended the sequence construction of [16, 18]. A class of quaternary generalized cyclotomic sequences with order 2d period 2pm over F4 are constructed, and their linear complexities are studied. In addition, in [19], Edemskiy and Ivanov constructed another kind of new quaternary generalized cyclotomic sequences with period 2p based on the Chinese Remainder Theorem and studied their autocorrelation properties and linear complexities over F4 as well as ℤ4.Although the sequence they constructed are both quaternary sequences, it can be seen by comparison that [16, 17, 19] have their advantages and disadvantages. On the one hand, by definition in [16, 17], the elements in a fixed support set of the sequence are all even or odd, while the sequence proposed by Edemskiy and Ivanov in [19] takes value more random. On the other hand, in [19], the sequence has period 2p, while in [17], the sequence has a more general period 2pm. In this paper, combining the advantages of the above two constructions, we will define a new class of quaternary generalized cyclotomic sequences of order 4 with period 2pm over F4 as well as ℤ4. Furthermore, we determine the linear complexities of the new defined sequences over F4 and ℤ4, respectively.This paper is organized as follows. In Section2, we introduce some necessary preliminary concepts and present a general construction of quaternary generalized cyclotomic sequences with period 2pm over ℤ4. In addition, based on a mapping from ℤ4 to F4, quaternary sequences over F4 can be derived directly from the quaternary sequences over ℤ4. In Section 3, we compute the linear complexity of sequences we constructed over F4. In Section 4, we compute the linear complexity of sequences that we constructed over ℤ4. In Section 5, we conclude this paper.


## 2. Perliminaries

Letp be an odd prime with p≡1mod4. Let g be a primitive root of ℤp2∗, where ℤn∗ denotes the set of all invertible elements of ℤn. It is well known that g is also a primitive root of ℤpm∗m≥1.Forj=1,2,…,m and l=0,1,2,3, we define(1)D0pj=g4modpj,Dlpj=glg4modpj,D02pj=g4mod2pj,Dl2pj=glg4mod2pj,where Dlpj are called generalized cyclotomic classes of order 4 with respect to pj and Dl2pj are called generalized cyclotomic classes of order 4 with respect to 2pj.It is easy to verify that(2)ℤ2pm=∪j=1mpm−jℤ2pj∗∪2ℤpj∗∪pmℤ2∗∪0=∪j=1mpm−jD02pj∪⋯∪pm−jD32pj∪2pm−jD0pj∪⋯∪2pm−jD3pj∪0,pm.For simplicity, we denote(3)Hlpj=pm−jDlpj,Hl2pj=pm−jDl2pj,l=0,1,2,3.Definition 1.
Let2∈Dkp,0≤k≤3. Then, we define the sequences s1uu≥0 and s2uu≥0 over ℤ4 of length 2pm by(4)s1u=0,ifu∈∪j=1m2H0−kmod4pj∪H12pj∪0;1,ifu∈∪j=1m2H1−kmod4pj∪H22pj;2,ifu∈∪j=1m2H2−kmod4pj∪H32pj∪pm;3,ifu∈∪j=1m2H3−kmod4pj∪H02pj,(5)s2u=0,ifu∈∪j=1m2H0−kmod4pj∪H22pj∪0;1,ifu∈∪j=1m2H2−kmod4pj∪H02pj;2,ifu∈∪j=1m2H1−kmod4pj∪H32pj∪pm;3,ifu∈∪j=1m2H3−kmod4pj∪H12pj,respectively.
The well-known Gray-mappingϕ:ℤ4⟶ℤ2×ℤ2 is defined as(6)ϕ0=0,0,ϕ1=0,1,ϕ2=1,1,ϕ3=1,0.
LetF4=μF2+F2 be a finite field of order 4, where µ satisfies the relation μ2+μ+1=0. Let σ be a map from F2×F2 to F4 which is defined as follows:(7)σ:F2×F2⟶F4,a,b↦aμ+b,where a,b∈F2.
Then, we haveσ∘ϕ:ℤ4⟶F4, i.e.,(8)σ∘ϕ0=0,σ∘ϕ1=1,σ∘ϕ2=μ+1,σ∘ϕ3=μ.
By this way, the sequences overℤ4 defined in (4) and (5) can be modified to be sequences over F4 as follows, i.e.,(9)b1u=0,ifu∈∪j=1m2H0−kmod4pj∪H12pj∪0;1,ifu∈∪j=1m2H1−kmod4pj∪H22pj;μ+1,ifu∈∪j=1m2H2−kmod4pj∪H32pj∪pm;μ,ifu∈∪j=1m2H3−kmod4pj∪H02pj.
Similarly,(10)b2u=0,ifu∈∪j=1m2H0−kmod4pj∪H22pj∪0;1,ifu∈∪j=1m2H2−kmod4pj∪H02pj;μ+1,ifu∈∪j=1m2H1−kmod4pj∪H32pj∪pm;μ,ifu∈∪j=1m2H3−kmod4pj∪H12pj.Remark 1.
Obviously, the support sets of sequences defined in this paper are more random than those in [16, 17], where the support sets all consist of even or odd numbers. In addition, the quaternary sequences constructed in [19] can be considered as a special case of the sequences defined above by taking m=1. In other words, in the case of length 2p, the constructions in [19] and this paper, although they were expressed in different forms, are the same in essence. In detail, the difference between these two constructions is that, in [19], the sequences were constructed by using the Chinese Remainder Theorem, while the sequences in this paper are defined directly. Therefore, this paper can be regarded as a generalization of [19].


## 3. Linear Complexity of the Sequence overF4

In this section, we discuss the linear complexity overF4. Hence, we focus on the quaternary sequences in (9) and (10). Let s∞=s0,⋯,si,⋯ be a sequence over F4, and its linear complexity Ls∞ is the smallest positive integer L for which there exist constants c1,c2,⋯,cL such that(11)sj+c1sj−1+c2sj−2+⋯+cLsj−L=0,j≥L.Lets∞=suu=0N be a periodic sequence of period N over F4. And Sx=∑​u=0N−1suxu is called the generating polynomial of the sequence. Then, the minimal polynomial of suu=0N is given by(12)mx=xN−1gcdxN−1,Sx,and the linear complexity of suu=0N is given by(13)LsN=N−deggcdxN−1,Sx.Letd be the order of 4 modulo pm, that is, d is the smallest integer such that 4d≡1modpm. Let ξ be a primitive element of F4d; then, the order of α=ξ4d−1/pm is pm, and θ=αpm−1 has order p.According to the definition of the linear complexity of the sequence, we should compute the number of common roots of the generating polynomialSx and polynomials xN−1. Notice that gcdxN−1,Sx=gcdx2pm−1,Sx=gcdxpm−12,Sx, so we may check that if αv0≤v≤pm−1 is a root of Sx. Furthermore, if it is a root of Sx, we need to verify if it is a multiple root of Sx [20].To this end, we need some auxiliary polynomials:(14)T4x=∑u∈D0pxu,T2x=∑u∈D0p∪D2pxu,Rljx=∑u∈Hl2pjxu,Sljx=∑u∈2Hlpjxu,where l=0,1,2,3 and j=1,2,⋯,m.Lemma 1.
(see [18]). For l=0,1,2,3, 1≤j≤m, we have(15)∑u∈Hl2pjαu=∑u∈Hlpjαu.Lemma 2.
(see [16]). For l=0,1,2,3, 1≤j≤m, we have(i)
Dlpj=x+py:x∈Dlp,y∈ℤpj−1,(ii)
Dl2pj=x+py+δx,y:x∈Dlp,y∈ℤpj−1,where(16)δx,y=0,ifx+pyis odd,pj,otherwise.Lemma 3.
Letv=tpi,0≤i≤m−1, 1≤j≤m,gcdt,p=1, and 2∈Dkp. For 0≤k,l≤3, we have(17)Rljαv=pj−1p−14,ifj≤i;∑u∈Dlpθtu,ifj=i+1;0,ifj>i+1,Sljαv=pj−1p−14,ifj≤i;∑u∈Dl+kmod4pθtu,ifj=i+1;0,ifj>i+1.Proof.
Since the proof is similar, only the case ofRljαv is considered here. By Lemma 1, we have (18)Rljαv=∑u∈Hl2pjαvu=∑u∈Hl2pjαtpiu=∑u∈tpm+i−jDl2pjαu=∑u∈tpm+i−jDlpjαu.(1)
Ifj≤i, note that αu=1 for any u∈tpm+i−jDlpj. Obviously, Dlpj=φpj/4. Hence,(19)Rljαv=∑u∈tpm+i−jDlpjαu=φpj4=pj−1p−14.(2)
Ifj=i+1, then(20)Rljαv=∑u∈tpm−1Dlpjαu=∑u∈Dlpjθtu=∑u∈Dlpθtu,whereθ=αpm−1.(3)
Ifj>i+1, suppose that αtpm+i−j=η, ηpj=1, and ηp≠1; then, ∑t∈ℤpj−1ηtp=0. So,(21)Rljαv=∑u∈tpm+i−jDlpjαu=∑t1∈Dlpηt1∑t2∈ℤpj−1ηt2=0.
The proof is thus completed.Lemma 4.
(see [4]). For 1≤t≤p−1, let θ be a primitive pth root of unity in the extension of the field F2, and define T2x=∑u∈D0p∪D2pxu. Then, we have(22)T2θt=T2θ,ift∈D0p∪D2p;T2θ+1,ift∈D1p∪D3p.Lemma 5.
(see [4]). With the above notation, then T2θ∈F2 if 2∈D0p∪D2p; otherwise, T2θ∈F4/F2.Lemma 6.
(see [21]). With notations defined as above, if 2∈Dkp, then T42θ=T4θgk.Theorem 1.
Letp≡1mod4 be an odd prime. Let b1uu≥0 be a generalized cyclotomic quaternary sequence of period 2pm defined in (9). Then, the linear complexity of b1uu≥0 over F4 is given by(23)Lb1u=2pm,ifp≡1mod8;3pm+12,ifp≡5mod8.Proof.
By the definition of the sequenceb1uu≥0, the generating polynomial Sx of b1uu≥0 is given by(24)Sx=μ+1xpm+∑j=1mS1−kmod4jx+R2jx+μ+1∑j=1mS2−kmod4jx+R3jx+μ∑j=1mS3−kmod4jx+R0jx.
It is easily seen that ifv=0, then S1=μ+1≠0. Hence, 1 is not root of Sx. We can write(25)Sαv=μ+1+∑j=1mS1−kmod4jαv+R2jαv+μ+1∑j=1mS2−kmod4jαv+R3jαv+μ∑j=1mS3−kmod4jαv+R0jαv.
According to Lemma3, if v=tpi,1≤v≤pm−1, we have(26)Sαv=μ+1+∑j=1i1+μ+1+μ⋅pj−1p−12+S1−kmod4i+1αv+R2i+1αv+μ+1⋅S2−kmod4i+1αv+R3i+1αv+μS3−kmod4i+1αv+R0i+1αv=μ+1+∑u∈D1pθtu+∑u∈D2pθtu+∑u∈D2pθtu+∑u∈D3pθtu+μ∑u∈D2pθtu+∑u∈D3pθtu+∑u∈D3pθtu+∑u∈D0pθtu=μ+1+T2θtg+μT2θt=μ+1+μT2θt,where the last equality follows from the fact that T2θtg=1+T2θt.(1)
Ifp≡1mod8, by Lemmas 4 and 5, we obtain Sαv∈1,μ. In other words, Sαv≠0 when 1≤v≤pm−1.(2)
Ifp≡5mod8, by Lemmas 4 and 5 again, we know that 2∈D1P (if not, then we can simply replace g with g−1). So,(27)T2θt=μ,ift∈D0p∪D2p;μ+1,ift∈D1p∪D3p.
Thus, ift∈D0p∪D2p, then Sαv=μ+1; if t∈D1p∪D3p, then Sαv=0.
To complete the proof, we should verify that ifαv1≤v≤pm−1 is a multiple root of Sx when t∈D1p∪D3p.(28)S′x=μ+1xpm−1+∑j=1m∑u∈H22pjxu−1+∑u∈H32pjxu−1+μ∑u∈H32pjxu−1+∑u∈H02pjxu−1.
According to Lemma3, if v=tpi,1≤v≤pm−1, we have(29)S′αv=α−vμ+1+∑j=1mR2jαv+R3jαv+μR3jαv+R0jαv=α−vμ+1+∑j=1i1+1+μ+μ⋅pj−1p−12+R2i+1αv+R3i+1αv+μR3i+1αv+R0i+1αv=α−vμ+1+T4θtg2+T4θtg3+μT4θtg3+T4θt.
As it was shown in [14], if t∈Dkp, then T4θt=ζ2k or T4θt=ζ24−k, where ζ satisfies the relation ζ8+ζ4+ζ2+ζ=1 and ζ4+ζ=μ over F4.(i)
Whent∈D1p, without loss of generality, suppose that T4θt=ζ2. By Lemma 6, we can write T4θtg2=ζ8,T4θtg3=ζ. Obviously, α−v≠0 for any v=tpi,1≤v≤pm−1. Since(30)μ+1+T4θtg2+T4θtg3+μT4θtg3+T4θt=μ+1+ζ8+ζ+μζ+ζ2=μ+1+1+ζ4+ζ2+μζ+ζ2=μ+1ζ2+ζ,andμ+1≠0, then we get ζ2+ζ=0 if S′αv=0. But, this means that ζ2=ζ, we get a contradiction. Thus, we have S′αv≠0 for any v=tpi,1≤v≤pm−1.(ii)
Whent∈D3p, without loss of generality, suppose that T4θt=ζ8. By Lemma 6, we can write T4θtg2=ζ2,T4θtg3=ζ4. Obviously, α−v≠0 for any v=tpi,1≤v≤pm−1. Similarly, since(31)μ+1+T4θtg2+T4θtg3+μT4θtg3+T4θt=μ+1+ζ2+ζ4+μζ4+ζ8=μ+1+ζ2+μ+ζ+μ1+ζ+ζ2=μ+11+ζ2+ζ,and μ+1≠0, we derive that 1+ζ2+ζ=0 if S′αv=0. But, this means that ζ2+ζ=1. By ζ8+ζ4+ζ2+ζ=1, we get ζ8=ζ4, i.e., ζ2=ζ. It is also a contradiction. Thus, we have S′αv≠0 for any v=tpi,1≤v≤pm−1.
In conclusion, we knowS′αv≠0 for all v=tpi,1≤v≤pm−1. Then, we complete the proof.Theorem 2.
Letp≡1mod4 be an odd prime. Let b2uu≥0 be a generalized cyclotomic quaternary sequence of period 2pm defined in (10). Then, the linear complexity of b2uu≥0 over F4 is given by(32)Lb2u=2pm.Proof.
The proof of this theorem is similar to that of Theorem1. Thus, we omit it here.


## 4. Linear Complexity of the Sequence overℤ4

Letsu=s0,⋯,sT be a quaternary sequence of period T over ℤ4, and its linear complexity Lsu is the smallest order L of a linear feedback shift register (LFSR) in ℤ4, for which there exist constants c1,c2,⋯,cL∈ℤ4 such that(33)sj+c1sj−1+c2sj−2+⋯+cLsj−L=0,j≥L.Also,CX=1+c1X+⋯+cLXL is called that connection polynomial. SX=s0+s1X+⋯+sT−1XT−1∈ℤ4X is called the generating polynomial of the sequence. Then, an LFSR with a connection polynomial CX generates su if and only if [22](34)SXCX≡0modXT−1,where CX∈ℤ4X satisfies C0=1. That is,(35)Lsu=mindegCX:CX∈ℤ4X,C0=1,SXCX≡0modXT−1.LetR=GR4r,4 be a Galois ring of characteristic 4 and cardinality 4r, where r is the order of 2 modulo p [23]. Let R∗=R/2R be the group of units of R, and it contains a cyclic subgroup of order 2r−1 [23]. Then, let β∈R be of order p. We can write γ=3β, and then the order of γ is 2pm and γpm=−1. By [23], we know that 2R is the maximal ideal of ring R. The natural homomorphism R⟶R¯=R/2R will be denoted by “-” and the image r∈R in R¯=R/2R by r¯.Notice that, in the ringR, the number of roots of a polynomial can be greater than its degree. Hence, we need some lemmas.Lemma 7.
(see [13]). Let Px∈ℤ4x be a nonconstant polynomial. If a∈R is a root of polynomial Px, then there exists a polynomial Q1x∈ℤ4x such that(36)Px=x−aQ1x.Moreover, ifb∈R is also the root of Px and a−b∈R∗, then(37)Px=x−ax−bQ2x,where Q1x=x−bQ2x.Lemma 8.
(see [13]). Let Px∈ℤ4x be a nonconstant polynomial. If Pγv=0 for all v=1,3,⋯,2pm−1, then there exists polynomial P1x∈ℤ4x such that(38)Px=P1xxpm+1.IfPγv=0 for all v=0,2,⋯,2pm−2, then there exists polynomial P2x∈ℤ4x such that(39)Px=P2xxpm−1.Theorem 3.
Letp≡1mod4 be an odd prime. Let s1uu≥0 be a generalized cyclotomic quaternary sequence of period 2pm defined in (10). Then, the linear complexity of s1uu≥0 over ℤ4 is given by(40)Ls1u=2pm.Proof.
With notations defined as before, letγ∈R∗ be of order 2pm and γpm=−1. It is easy to know that xpm−1/x−1=∏​i=1pm−11−γ2i. Then, pm=∏​i=1pm−11−γi1+γi. Hence, when j,l=0,⋯,pm−1, we have γj−γl∈R∗.
By the definition of the connection polynomial and linear complexity overℤ4, we have Lsu≤2pm.
Without loss of generality, assume thatLsu<2pm; then, there exists a connection polynomial Cx, and it satisfies(41)SxCx≡0modx2pm−1,where the degree of Cx is less than 2pm.
By the definition of γ, we haveγ¯pm=1 and γ¯≠0,1. Then, in the ring R¯, ∑​j=1pm−1γ¯j=1 holds.
By (4), we get(42)Sx=2xpm+∑j=1mS1−kmod4jx+R2jx+2∑j=1mS2−kmod4jx+R3jx+3∑j=1mS3−kmod4jx+R0jx.
If2∈Dkp,0≤k≤3, and by Lemma 1, we obtain(43)Sγ¯v=∑j=1m∑u∈H1pjγ¯vu+∑u∈H2pjγ¯vu+∑u∈H3pjγ¯vu+∑u∈H0pjγ¯vu=∑l=1pm−1γ¯l=1.
According to (41), we have Cγv=0 for all v=0,1,⋯,2pm−1,v≠p. Then, xpm−1/x−1|Cx, which implies that there exists a polynomial Qx∈ℤ4x,2Qx≠0 such that(44)Cx=Qxxpm−1−1x−1.
Moreover, it is easily seen that(45)Dlpj=Dl2pj=φpj2,where l=0,1,2,3, j=1,2,⋯,m, and φ⋅ is Euler function. Then,(46)S1=2+1+2+3∑j=1mφpj2+φpj2=2+4∑j=1mφpj=2.
Thus,C1∈0,2 and Q1∈0,2; this means that(47)Qx=x−1Fx+q,q∈0,2,Cx=xpm−1Fx+qxpm−1x−1.
Hence, whenv=1,3,⋯,2pm−1, we have(48)Cγv=γvpm−1Fγv+qγvpm−1γv−1=−2Fγv=0.
In other words, whenv=1,3,⋯,2pm−1, we have 2Fγv=0. Then, by Lemma 8, we get xpm+1|2Fx. But, this means that degFx≥pm, which is contrary to our assumption. The proof is thus completed.Theorem 4.
Letp≡1mod4 be an odd prime. Let s2uu≥0 be a generalized cyclotomic quaternary sequence of period 2pm defined in (5). Then, the linear complexity of s2uu≥0 over ℤ4 is given by(49)Ls2u=2pm.Proof.
The proof of this theorem is similar to that of Theorem3. Thus, we omit it here.


## 5. Conclusions

This paper presented new classes of quaternary generalized cyclotomic sequences with order 4 and period2pm, where p is an odd prime and p≡1mod4. We computed their linear complexity over finite field F4 as well as ℤ4. The results indicated that the sequences proposed in this paper possess high linear complexities. Autocorrelation is another important measure of a sequence. For quaternary sequence s with even period over ℤ4, the optimal maximum out-of-phase autocorrelation magnitude, denoted by Rmaxs, has been shown to be 2 [24]. For the new proposed sequence, when the period is 2p, Edemskiy has proved that Rmaxs=22 if p≡5mod8 and Rmaxs=4 if p≡1mod8, respectively. However, for the general case, the autocorrelation properties of the new proposed sequences are not known. Hence, as a further work, it is valuable to analyze the autocorrelation values of the new proposed sequences.



---

*Source: 6538970-2020-03-10.xml*