# Linear Complexity of Generalized Cyclotomic Sequences of Order 4 overFl

Authors: Yuhua Sun; Qiuyan Wang; Yang Yan; Tongjiang Yan; Hui Li
Journal: Complexity
 (2020)

---

## Abstract

Generalized cyclotomic sequences of periodpq have several desirable randomness properties if the two primes p and q are chosen properly. In particular, Ding deduced the exact formulas for the autocorrelation and the linear complexity of these sequences of order 2. In this paper, we consider the generalized sequences of order 4. Under certain conditions, the linear complexity of these sequences is developed over a finite field Fl. The results show that, in many cases, they have high linear complexity.


---

## Body

## 1. Introduction

Letl be a prime number and Fl denote a finite field with l elements. A sequence λ∞=λ0λ1⋯λn−1⋯ is called to be n-periodic if λi=λi+n for all i≥0. Periodic sequences with certain properties are widely used in software testing, radar systems, stream ciphers, and so on. For cryptography applications, the linear complexity is an important factor. It is defined to be the length of the shortest linear feedback shift register which generates this sequence. For cyclotomic sequences, many researchers are devoted to studying their random properties [1–8]. The generalized cyclotomic sequences have been described and studied [9–11, 12, 13] for the past decades. A number of periodic sequences with attractive random properties have been constructed [6, 14–20].Letp and q be two distinct odd primes with gcdp−1,q−1=d. Define n=pq and e=p−1q−1/d. The Chinese reminder theorem guarantees that there exists a common primitive root g of both p and q. Let x be an integer satisfying(1)x≡gmodp,x≡1modq.Whiteman proved that [21](2)ℤn∗=gixj:i=0,1,…,e−1;j=0,1,…,d−1,where ℤn∗ denotes the set of all invertible elements of the residue class ring ℤn.The generalized cyclotomic classesDj 0≤j≤d−1 of order d with respect to n are defined by [21](3)Dj=gixj:i=0,1,…,e−1,0≤j≤d−1,where the multiplication is that of ℤn. Clearly, the cosets Dj depend on the choice of the common primitive root g if d≥3. It is not hard to prove that [21](4)ℤn∗=∪j=0d−1Dj,Di∩Dj=∅,fori≢j,where ∅ denotes the empty set. Define(5)P=p,2p,…,q−1p=pℤq∗,Q=q,2q,…,p−1q=qℤp∗.Then,(6)ℤn=∪i=0d−1Di∪0∪P∪Q.LetS be a nonempty subset of 0,1,…,d−1 and(7)∑S=∪i∈SDi.We define the binary sequenceλ∞=λ0λ1⋯λn−1⋯ of period n as follows:(8)λi=1,ifimodn∈P∪ΣS,ρ,ifimodn∈0,0,otherwise,where i≥0 and ρ∈0,1. For ρ=0 and S=0, the linear complexity of these sequences over F2 has been calculated by Ding [16] with d=2 and Hu et al. [20] with d=4. Furthermore, for S=0,2,…,d−2 and ρ=0, Ding [9] determined the linear complexity of the two-prime sequences over a finite field Fl and used these sequences to construct several classes of cyclic codes over Fl with optimal or almost optimal property, where gcdl,n=1. In this paper, we only consider the case ρ=1, d=4, and S=0,1. Under the assumption that n−1/4≡0modl or l∉D0, we calculate the linear complexity of these sequences over the finite field Fl. The results show that, in many cases, these sequences have high linear complexity.This paper is organized as follows. Section2 presents basic notations and results of periodic sequences and the generalized cyclotomy [21]. In Section 3, we give an expression for the linear complexity of the generalized cyclotomic sequences over Fl. In the last section, we present concluding remarks of this paper.


## 2. Preliminaries

Firstly, we give the definition and formula of linear complexity of periodic sequences over a finite field. See [22] or [23] for more details.Letl be a prime number and λ∞=λ0λ1⋯λn−1⋯ be a periodic sequence over Fl with period n, where λi∈Fl for i≥0. The sequence λ∞ can be viewed as a power series(9)Λ∞x=∑i=0∞λixi=Λx1−xn,Λx=λ0+λ1x+⋯+λn−1xn−1∈Flx,in the power series ring Flx.Lethx=gcdΛx,1−xn, then(10)Λ∞x=wxvx,vx=1−xnhx,wx=Λxhx,where wx,vx,hx∈Flx.Definition 1.
The polynomialvx is called the minimal polynomial of the periodic sequence λ∞ over Fl. The degvx=n−deghx is called the linear complexity of the sequence λ∞ over Fl, which is denoted by Llλ.
Indeed,Llλ is the length of the shortest linear feedback shift register which generates the sequence λ∞.
Ifgcdn,l=1, then 1−xn has n distinct roots ζni0≤i≤n−1 in the algebraic closure Ωl of Fl, where ζn denotes the n-th primitive root of unity. It is easy to see that(11)Llλ=n−i:0≤i≤n−1,Λζni=0.
In order to determine the linear complexity of generalized cyclotomic sequences, we introduce generalized cyclotomy.
Let symbols be the same as in the introduction andd=gcdp−1,q−1=4. The generalized cyclotomic numbers of order 4 with respect to n is defined by(12)i,j=Di+1∩Dj,for0≤i,j≤3.
By the well-known theorem ([24], P. 128), there are exactly two representations of n in the form n=a2+4b2 with a≡1mod4 and the sign of b indeterminate.
Letg1 and g2 be a fixed primitive root of p and q, respectively. For i=1,2, let xi and yi be the integers given uniquely by(13)p=x12+4y12,q=x22+4y22,x1≡x2≡1mod4,2y1≡−−g1p−1/4x1modp,2y2≡−−g2q−1/4x2modq.
Definea and b to be integers satisfying(14)a=x1x2+42p2qy1y2,b=x2y1−2p2qx1y2,where ÷ denotes the Legendre symbol.
It is clear thata≡1mod4 and n=a2+4b2 is one of the two representations of n. The following lemma shows that the generalized cyclotomic numbers of order 4 with respect to n depend uniquely on this representation.Lemma 1 (see [19], Theorem IV.1.).
Letp≡q≡1mod4 be two distinct primes with the fixed primitive roots g1 and g2, respectively. M=p−2q−2−1/4, and a and b are the integers defined in (14).
Ifp≢qmod8, then in Table 1, 8A=−a+2M+3, 8B=−a−4b+2M−1, 8C=3a+2M−1, 8D=−a+4b+2M−1, and 8E=a+2M+1.
Ifp≡qmod8, then in Table 2, 8A=3a+2M+5, 8B=−a+4b+2M+1, 8C=−a+2M+1, 8D=−a−4b+2M+1, and 8E=a+2M−1.Table 1
p
≢
q
mod
8.
i
,
j
0
1
2
3
0
A
B
C
D
1
E
E
D
B
2
A
E
A
E
3
E
D
B
ETable 2
p
≡
q
mod
8.
i
,
j
0
1
2
3
0
A
B
C
D
1
B
D
E
E
2
C
E
C
E
3
D
E
E
B


## 3. Generalized Cyclotomic Sequences of Order 4

Throughout this section, letp and q be two distinct odd primes with gcdp−1,q−1=4. Define n=pq and e=p−1q−1/4. Let l be a prime and satisfy gcdl,n=1.The generalized cyclotomic sequenceλ∞ of order 4 of period n is defined by(15)λi=1,ifimodn∈0∪P∪D0∪D1,0,otherwise,where D0 and D1 are defined by (3) and P=pℤq∗. Here, in this paper, we treat it as a sequence over a finite field Fl, where gcdl,n=1.Denoteordnl the multiplicative order of l modulo n. Let ζn be an n-th primitive root of unity over Flordnl. For the sequence λ∞ defined by (15), we know(16)Λx=∑i=0n−1λixi=1+∑i∈Pxi+∑i∈D0xi+∑i∈D1xi,(17)Λ1=1+p+1q−12modl.Defineδ as follows:(18)δ=1,ifl1+p+1q−12,0,otherwise.Note that the generalized cyclotomic classes of order 2 are given by(19)C0=D0∪D2,C1=D1∪D3.Defineη0=∑i∈C0ζni. The following lemma has been proven in [9].Lemma 2 (see [9], Lemma 3.13).
Ifn≡1mod4, then we have(20)η01−η0=−n−14.
Hence,η0∈0,1 if and only if n−1/4≡0modl.
To compute the linear complexity ofλ∞, we need to compute gcdxn−1,Λx. For this purpose, we require a number of auxiliary results.Lemma 3 (see [16], Lemma 5).
Letm be the least common multiple of two positive integers m1 and m2. The system of congruences(21)x≡a1modm1,x≡a2modm2,has solutions if and only if(22)gcdm1,m2a1−a2,where ab means that a divides b. When condition (22) holds, the system of the congruences of (21) has only one solution modulo m.Lemma 4.
Fora∈Dj, then aDi=Di+jmod4.Proof.
To prove this lemma, we need to provex4∈D0 for the integer x defined by (1).
By the generalized Chinese reminder theorem, there exists an integers with 0≤s≤e−1 such that(23)s≡4modp−1,s≡0modq−1.That is, the integer s satisfies(24)x4≡gsmodp,x4≡gsmodq.
Thiss is unique. Hence, x4≡gsmodpq and x4∈D0.
Becauseζn is an n-th primitive root of unity over Flordnl, we have(25)∑i∈Pζni=−1,∑i∈Qζni=−1.
By the definition ofζn, we have(26)ζnn−1=ζn−11+∑i∈Pζni+∑i∈Qζni+∑j=03∑i∈Djζni=0.
Together with (25), we obtain(27)∑j=03∑i∈Djζni=1.
Definetx=∑i∈D1xi+∑i∈D2xi.Lemma 5.
Let symbols be the same as before. Then,(28)Λζna=Λζn,a∈D0,tζn,a∈D1,−Λζn−1,a∈D2,−tζn−1,a∈D3,−p−12,a∈P,q+12,a∈Q.Proof.
By Lemma4, aD0=D0 and aD1=D1 if a∈D0. If a∈D0, then aP=P since gcda,q=1. Hence, we obtain(29)Λζna=1+∑i∈Pζnai+∑i∈D0∪D1ζnai=1+∑i∈Pζni+∑i∈D0∪D1ζni=Λζn.
Ifa∈D1, by Lemma 4, aD0=D1 and aD1=D2. By (25), we have(30)Λζna=1+∑i∈Pζnai+∑i∈D0∪D1ζnai=∑i∈D1ζni+∑D2ζni=tζn.
Ifa∈D2, by Lemma 4, aD0=D2 and aD1=D3. By (25) and (27), we obtain(31)Λζna=1+∑i∈Pζnai+∑i∈D0∪D1ζnai=∑i∈D2ζni+∑i∈D3ζni=1−∑i∈D0∪D1ζni=1−Λζn.
Ifa∈D3, by Lemma 4, aD0=D3 and aD1=D0. By (27), we have(32)Λζna=1+∑i∈Pζnai+∑i∈D0∪D1ζnai=∑i∈D3ζni+∑D0ζni=1−tζn.
Ifa∈P, then aP=P. Then, by (25), we know(33)Λζna=1+∑i∈Pζnai+∑i∈D0∪D1ζnai=∑i∈D0∪D1ζnai.
Whens ranges over 0,1,…,e−1, it can be checked that D0∪D1modq takes on each element of 1,2,…,q−1 exactly p−1/2 times. It follows from (25) that(34)∑i∈D0∪D1ζnai=p−12modl∑i∈Pζni=−p−12modl.
Ifa∈Q, then aP=0. Then,(35)Λζna=1+∑i∈Pζnai+∑i∈D0∪D1ζnai=1+q−1+∑i∈D0∪D1ζnai.
Whens ranges over 0,1,…,e−1, D0∪D1 modp takes on each element of 1,2,…,p−1 exactly q−1/2 times. It follows from (25) that(36)Λζna=1+q−1+∑i∈D0∪D1ζnai=1+q−1+q−12∑i∈Qζni=q+12modl.Lemma 6 (see [20], Lemma 3.3).
Let notations be the same as before. Then,(1)
−1∈D0 if and only if p≢qmod8(2)
−1∈D2 if and only if p≡qmod8Lemma 7 (see [21], Lemmas 2 and 4).
For eachw∈P∪Q,(37)Di∩Dj+w=p−1q−116,ifi≠j,p−1q−516,ifi=jandpw,p−5q−116,ifi=andqw.Define(38)Δ1=p−12modl,Δ2=q+12modl.Theorem 1.
Letn−1/4≡0modl. Then, the linear complexity of the sequence λ∞ defined by (15) is given as follows:(1)
Whenp≡qmod8 and b/2≡0modl, we have(39)Llλ=pq+p+q−12−δ,ifΔ1≠0,Δ2≠0,pq−p+q+12−δ,ifΔ1≠0,Δ2=0,pq+p−q+12−δ,ifΔ1=0,Δ2≠0,pq−p−q+12,ifΔ1=0,Δ2=0.(2)
Whenq≢pmod8 and a2+3/4≡0modl, we have(40)Llλ=3pq+p+q−14−δ,ifΔ1≠0,Δ2≠0,3pq−3p+q+34−δ,ifΔ1≠0,Δ2=0,3pq+p−3q+34−δ,ifΔ1=0,Δ2≠0,3pq−3p−3q+54,ifΔ1=0,Δ2=0.(3)
Whenp≡qmod8 and b/2≢0modl or q≢pmod8 and a2+3/4≢0modl, we have(41)Llλ=n−δ,ifΔ1≠0,Δ2≠0,n+1−p−δ,ifΔ1≠0,Δ2=0,n+1−q−δ,ifΔ1=0,Δ2≠0,n+2−p−q,ifΔ1=0,Δ2=0,where a and b are the integers defined in (14) and δ is defined in (18).Proof.
By definition, we have(42)Λζn2=∑i∈D0,j∈D0+∑i∈D0,j∈D0+∑i∈D0,j∈D0+∑i∈D0,j∈D0ζni+j.
We first prove the conclusions for the case thatq≡pmod8. In this case, by Lemma 6, −1∈D0 and b must be even. By Table 2, in Lemma 1 and Lemma 7, we have(43)Λζn2=∑i∈D0,j∈D0+∑i∈D0,j∈D1+∑i∈D1,j∈D0+∑i∈D1,j∈D1ζni−j=0,0+3,3+0,1+3,0∑i∈D0ζni+01,0+0,3+1,1+0,0∑i∈D1ζni+2,0+1,3+2,1+1,0∑i∈D2ζni+3,0+2,3+3,1+2,0∑i∈D3ζni+2p−1q−116∑i∈Pζni+2p−1q−116∑i∈Pζni+2p−1q−516∑i∈Pζni+2p−5q−116∑i∈Qζni+D0+D1=Λζn+b∑i∈D0∪D2ζni−b2+M+p+q−22.
Fromn−1/4≡0modl, we know M+p+q−2/2≡0modl. Hence,(44)Λζn2=Λζn+b∑i∈D0∪D2ζni−b2.
Whence,(45)ΛζnΛζn−1=b22∑i∈D0∪D2ζni−1.
Note thatn−1/4≡0modl. By Lemma 2, we have ∑i∈D0∪D2ζni∈1,0. It follows that(46)2∑i∈D0∪D2ζni−1∈1,−1.
Similarly, we have(47)tζntζn−1=−b22∑i∈D0∪D2ζni−1.
By Lemma5, (45), and (47), we know when b/2≡0modl, there are exactly half of a′s with a∈ℤn∗ such that sζna=0. When b/2≢0modl, sζna≢0 for all a∈ℤn∗. Then, the desirable results on the linear complexity of the sequence s follow from (11), (17), and Lemma 5.
Now, we prove the conclusions for the case thatq≢pmod8. In this case, by Lemma 6, −1∈D2. It follows from Table 1 in Lemmas 1 and 7 that(48)Λζn2=∑i∈D0,j∈D2+∑i∈D0,j∈D3+∑i∈D1,j∈D2+∑i∈D1,j∈D3ζni−j=2,2+1,1+2,3+1,2∑i∈D0ζni+3,2+2,1+3,3+2,2∑i∈D1ζni+0,2+3,1+0,3+3,2∑i∈D1ζni+1,2+0,1+1,3+0,2∑i∈D1ζni+4p−1q−116∑i∈Pζni+4p−1q−116∑i∈Qζni=Λζn+b2∑i∈D0∪D2ζni−1−12+M−p−1q−12.
Fromn−1/4≡0modl, we have M−p−1q−1/2≡0modl. Hence,(49)Λζn2=Λζn+b2∑i∈D0∪D2ζni−1−12.
Whence,(50)ΛζnΛζn−1=b2∑i∈D0∪D2ζni−1−12.
Similarly, we get(51)tζntζn−1=−b2∑i∈D0∪D2ζni−1+12.
Sincegcdp−1,q−1=4 and p≡q+4mod8, we get p≡1 or 5mod8. Hence, n=pq≡5mod8. Together with n−1/4≡0modl, we obtain l which is an odd prime. By the representation n=a2+4b2 with a≡1mod4, we have(52)n−14=a2+34+b−1b+1.
Therefore,a2+3/4≡0modl if and only if b−1b+1≡0modl. Since l is odd, we obtain b−1b+1≡0modl if and only if l divides one of b−1 and b+1. By Lemma 5, if a2+3/4≡0modl, there are exactly p−1q−1/4 a’s such that sζna=0 for a∈ℤn∗. If a2+3/4≡0modl, sζna≢0 for all a∈ℤn∗. Then, the desirable conclusions on the linear complexity of the sequence λ∞ follow from (11), (17), (46), and Lemma 5.
For the casel∉D0, the linear complexity of the sequence λ∞ defined by (15) can also be determined in the following theorem.Theorem 2.
Ifl∉D0, then for the sequence λ∞ defined in (15), we have(53)Llλ=n−δ,ifΔ1≢0,Δ2≢0,n+1−p−δ,ifΔ1≢0,Δ2=0,n+1−q−δ,ifΔ1=0,Δ2≢0,n+2−p−q,ifΔ1=0,Δ2=0.Proof.
Ifl∉D0, then there exists i∈1,2,3 such that i∈Di. No matter what i is, there exists j∈1,2,3 satisfying the congruence equation ij≡2mod4. Then, lj∈D2 and(54)Λljζn=Λζnlj=1−Λζn.
This impliesΛζn∉0,1.
Similarly,tljζn=tζnlj=1−tζn and tζn∉0,1. Hence, sζn≢0 for all a∈ℤn∗. Combining (11) and Lemma 5, we have the desirable results.
Forj∈0,1,2,3, define(55)djx=∏i∈Djx−ζni.
Ifl∈D0, it can be easily proved that djx∈Flx for all j.
Letdx=∏j=03djx, then dx∈Flx. We have(56)xn−1=∏i=0n−1x−ζni=xq−1xp−1dxx−1.Lemma 8 (see [20], Lemma 3.3).
Let notations be the same as before. Then,(1)
2∈D0∪D2 if and only if p≡qmod8(2)
2∈D1∪D3 if and only if p≡qmod8Lemma 9 (see [20], Lemma 3.5).
Letp≡qmod8. Then, there are exactly two representations over the integer ring ℤ:(57)pq=a2+4b2=a′2+4b′2,a≡a′≡1mod4,where one of b and b′ is divided by 4 and another is exactly divided by 2.Lemma 10 (see [20], Corollary 3.9).
Letp≡qmod8. Fix a common primitive root g of p and q. Then, 2∈D0 if and only if the generalized cyclotomic numbers in Lemma 1 depend on the decomposition n=a2+4b2 with 4b; 2∈D2 if and only if the generalized cyclotomic numbers depend on the decomposition n=a2+4b2 with 2b, where 2b means that 2b and 22∤b.
After the preparations above, we are ready to compute the linear complexity and minimal polynomials of the sequence defined in (15) over F2.Corollary 1.
Letl=2 and n=a2+4b2≡1mod8. Then, p≡qmod8 and the linear complexity and minimal polynomials of the sequence λ∞ defined by (15) are given as follows:(1)
When4b, then(58)L2λ=pq−q+p+12,mx=xn−1x−1xq−1d2xd1x,ifΛζn=1andtζn=0,xn−1x−1xq−1d0xd3x,ifΛζn=0andtζn=1,xn−1x−1xq−1d0xd1x,ifΛζn=0andtζn=0,xn−1x−1xq−1d2xd3x,ifΛζn=1andtζn=1.(2)
When2b, then(59)L2λ=n+1−q,mx=xn−1x−1xq−1.Proof.
Ifp≡qmod8, then p≡q+4mod8 and n=pq≡5mod8. This contradicts with n≡1mod8. Hence, p≡qmod8. Also, in this case, by Lemma 8, 2∈D0∪D2.
By (45), (47), and Lemma 10, if 4b, i.e., 2∈D0, we have(60)Λζn∈0,1,tζn∈0,1,and if 2b, i.e., 2∈D2, we obtain(61)Λζn∉0,1,tζn∉0,1.
Then, the desired conclusions on the linear complexity and the minimal polynomial of the sequenceλ∞ follow from (11) and Lemma 5.
Ifp≢qmod8, then n=pq≡5mod8, and by Lemma 8, 2∈D1∪D3. Hence, by Theorem 2, we have the following corollary.Corollary 2.
Letl=2 and n≡5mod8. Then, for the sequence λ∞ defined by (15), we have(62)L2λ=n+1−q,mx=xn−1x−1xq−1.Example 1.
Letp,q=5,13 and g1,g2=2,2. Then, a=1 and b=4. If l=2, Magma program shows that 2∈D0 and L2λ=29. If l=3, then b/2≢0modl and L3λ=65.Example 2.
Letp,q=5,17 and g1,g2=2,3. Then, a=−7 and b=3. If l=2, it can be easily checked that 2∈D3 and L2λ=69. If l=7, then a2+3/4≢0modl and L7λ=85.



---

*Source: 6963487-2020-03-11.xml*