LINEAR COMPLEXITY OF GENERALIZED CYCLOTOMIC BINARY SEQUENCES OF PERIOD pq

YANG Bo DU Tian-qi XIAO Zi-bi

(1.Hubei Province Key Laboratory of Systems Science in Metallurgical Process,Wuhan University of Science and Technology, Wuhan 430081, China)

(2.College of Science, Wuhan University of Science and Technology, Wuhan 430081, China)

Abstract: In this paper, a class of generalized cyclotomic binary sequences of period pq is proposed, where p and q are two distinct odd primes.By using Whiteman’s generalized cyclotomy of order 4 and classic cyclotomy of order 2, the sequences are almost balanced and the exact value of their linear complexity is calculated, which shows that the proposed sequences are quite good in terms of the linear complexity.

Keywords: binary sequence; linear complexity;cyclotomy;generalized cyclotomic sequence

1 Introduction

Pseudo-random sequences were widely used in communication and cryptographic systems.For the application of stream cipher, the keystream sequences had unpredictability and randomness [1].One of the important indexes for measuring these properties is linear complexity of sequence,which is defined to be the length of the shortest linear feedback shift register that can generate the given sequence.Generally speaking, a sequence with large linear complexity(at least a half of its period)is considered to be favorable for cryptography to resist the well-known Berlekamp-Massey algorithm.

For an integer N ≥ 2, let ZN= {0,1,··· ,N ? 1} denote the ring of integers modulo N anddenote the set of all invertible elements of ZN.Let {D0,D1,··· ,Dd?1} be a partition of.If D0is a multiplicative subgroup ofand there exist elements gi∈such that Di=giD0for all i ∈ {1,2,··· ,d ? 1}, then for prime (composite) N, these Diare called classical (generalized) cyclotomic classes of order d with respect to N.

Using classical cyclotomy or generalized cyclotomy to construct sequences is an effective method to obtain sequences with large linear complexity.The linear complexity and autocorrelation property of generalized cyclotomic sequences with various period were extensively studied in the literature (see [2–7]).In this paper, we focus on the generalized cyclotomic binary sequences of period pq.

The generalized cyclotomic binary sequences of period pq are by far constructed on the basis of Whiteman’s generalized cyclotomic classes or Ding-Helleseth generalized cyclotomic classes which are proposed in [8]and [9], respectively.Most of these sequences have large linear complexity.A brief review of these sequences are provided in Section 2.In this paper,a class of new generalized cyclotomic binary sequences of period pq based on Whiteman’s generalized cyclotomy of order 4 and classic cyclotomy of order 2 is proposed.By using the classic method for calculating the linear complexity described in [10], we determine the exact value of the linear complexity of such sequences.Our results show that the proposed sequences have large linear complexity.

2 Preliminary

In this section, we first recall the two types of generalized cyclotomy with respect to pq and the known generalized cyclotomic sequences of period pq, and then define a class of new generalized cyclotomic sequences of period pq.

Let N =pq, where p and q are distinct odd primes with gcd(p ? 1, q ? 1)=d.DefineLet g be a fixed primitive root of both p and q.Then ordN(g) = lcm(p ?1,q ? 1)=e.Let x be an integer satisfying x ≡ g(mod p), x ≡ 1(mod q). Whiteman proved in [8]that

Whiteman’s generalized cyclotomic classes of order d with respect to pq are defined by [8]

Ding-Helleseth generalized cyclotomic classes of order d with respect to pq are defined by[9]

On the basis of these two generalized cyclotomies of even order d, many generalized cyclotomic sequences of period pq were constructed.

It is easily seen that the difference between the numbers of ones and zeros is q ? p ? 1 in all the above sequences, i.e., they are not balanced unless q = p+2 (note that in the case where the difference is equal to ±1 the sequences are called almost balanced).In [9]Ding and Helleseth introduced a new method to construct almost balanced sequences, that is, using the classic cyclotomy to divide the sets P and Q.Let d1be a divisor of d, and p ? 1=d1f1, q ? 1=d1f2.For i=0,1,··· ,d1? 1, define

In the following,we define a family of generalized cyclotomic binary sequences of period N = pq, where p and q are distinct odd primes with gcd(p ? 1, q ? 1) = 4.Let Diwith i ∈ {0,1,2,3} be Whiteman’s generalized cyclotomic classes of order 4 defined in (2.1),with i ∈{0,1} be the classical cyclotomic classes of order 2 defined in (2.2).LetR={0}.Then

Define two sets

where a is an arbitrary integer with 0 ≤ a ≤ 3, and the subscripts i in Diare assumed to be taken modulo 4.For simplicity, the modulo operation is omitted in this paper.It is easy to see that {C0,C1} forms a partition of ZNand |C0|?|C1| = 1.Now we define a family of almost balanced binary sequences of period pq which admits C1as the characteristic set,i.e., the sequences s∞=(s0,s1,s2,···) are given by

3 Linear Complexity

Let s∞= (s0,s1,s2,···) be a periodic infinite sequence over a field F.The linear complexity of s∞is defined to be the least positive integer L such that there are constants c0= 1, c1,··· ,cL∈ F satisfying ?si= c1si?1+c2si?2+ ···+cLsi?Lfor all i ≥ L. The polynomial c(x)=c0+c1x+ ···cLxLis called the minimal polynomial of s∞.Let N be the period of s∞.It is well known that

where s(x) = s0+s1x+ ···+sN?1xN?1is the generating polynomial of the sequence s∞.The linear complexity of {si} is given by

In this section, we use (3.1) to determine the linear complexity of the new generalized cyclotomic binary sequences of period pq defined by (2.3).

For a with 0 ≤ a ≤ 3, denote

Then the generating polynomial of a sequence defined by (2.3) for a given integer a is sa(x).Let m be the order of 2 modulo N.Then there exists a primitive Nth root of unity α over the splitting field GF(2m) of xN?1.Thus the linear complexity of the sequence is given by

That is to say, the problem of determining the linear complexity of the sequence defined by(2.3)is reduced to that of counting the number of roots in the set{αj: j =0,1,··· ,pq ?1}of the generating polynomial given in (3.2).

To determine the linear complexity of the sequences defined by (2.3), we need the following lemmas.

Lemma 2.1(see [23]) Let the symbols be the same as before.Then

(i) if a ∈ Di, then aDj=D(i+j)(mod4), where i,j ∈ {0,1,2,3};

(ii) for any odd prime p, if t(mod p) ∈where i,j ∈{0,1}.

Lemma 2.2(see [15]) Let the symbols be the same as before.Then

Lemma 2.3(see [12]) Let the symbols be the same as before.Then

Lemma 2.4Let the symbols be the same as before.Then

Proof(i) If t(mod p) ∈, then by Lemma 2.1 (ii), we havethus

The assertions in (iii) and (iv) can be similarly proved, so we omit them here.

Lemma 2.5Let the symbols be the same as before.For t ∈and t(mod q) ∈where i,j ∈ {0,1}.Then t ∈ D0∪ D2if and only if i = j, and t ∈ D1∪ D3if and only if ij.

ProofLet t ∈ Dkwith k ∈ {0,1,2,3}.Then there exists a uniquely determined integer u0with 0 ≤ u0≤ e?1 such that t ≡ gu0xk(mod pq).Since x ≡ g(mod p)and x ≡ 1(mod q),we have t ≡ gu0+k≡ g(u0+k)(modp?1)(mod p) and t ≡ gu0≡ gu0(modq?1)(mod q).It is easily verified that k is even if and only if u0+k and u0have the same parity, or equivalently, if and only if (u0+k)(mod p ? 1) and u0(mod q ? 1) have the same parity since p ? 1 and q ?1 are both even.Therefore, t(mod p) and t(mod q) are either quadratic residues of both p and q or quadratic nonresidues of both p and q, and the desired result for even k follows immediately from the definition of the classical cyclotomic classes of order 2.The case of odd k can be proved in the similar way.

Lemma 2.6Let the symbols be the same as before.Then

ProofFor t ∈ D0∪ D2, it follows from Lemma 2.5 that t(mod p)and t(mod q)or t(mod p)and t(mod q)Then by Lemma 2.4, we always have

For t ∈ D1∪ D3, it follows from Lemma 2.5 that t(mod p)and t(mod q)or t(mod p)and t(mod q)Then by Lemma 2.4, we always have

Moreover, by Lemma 2.1 we have tDa= Da+k, tDa+1= Da+k+1for t ∈ Dkwith k ∈{0,1,2,3}, so that

Thus, when t ∈D0,

when t ∈D1,

When t ∈D2, by Lemma 2.2 (iii), we have

It follows then that

By the same arguments, for the case t ∈D3, we have

The proof is completed.

Lemma 2.7Let the symbols be the same as before.Then

ProofWhen t ∈ P, for any i ∈ Q1, ti(mod pq)=0, so that

Then by Lemma 2.3, we get

When t ∈ Q, for any i ∈ P1, ti(mod pq)=0, it follows that

Again by Lemma 2.3, we obtain

Lemma 2.8For any a ∈ {0,1,2,3}, sa(α) ∈ {0,1} if and only if 2 ∈ D0.

ProofIf 2 ∈ D0, then by Lemma 2.6, sa(α2) = sa(α) for any a ∈ {0,1,2,3}.Since the characteristic of the field GF(2m) is 2, it follows that sa(α2) = [sa(α)]2.Thus we get[sa(α)]2=[sa(α)], and so sa(α)∈ {0,1}.

To prove the necessity, we suppose, by way of contradiction, that 2D0.

If 2 ∈ D1,then it follows from Lemma 2.6 that sa(α2)=1+sa+1(α).On the other hand,since sa(α) ∈ {0,1}, sa(α) = [sa(α)]2= sa(α2).Thus sa(α) = 1+sa+1(α), which implies sa+1(α) ∈ {0,1}.By the same argument, sa+1(α) = [sa+1(α)]2= sa+1(α2) = 1+sa+2(α),and so sa(α)=sa+2(α).But from (3.2) and Lemma 2.2 (iii), it follows that

and so we arrive at a contradiction.

If 2 ∈ D2, then by Lemma 2.6, sa(α) = [sa(α)]2= sa(α2) = 1+sa(α), an obvious contradiction.

Similarly, if 2 ∈ D3, then sa(α) = [sa(α)]2= sa(α2) = sa+1(α) and sa+1(α) =[sa+1(α)]2=sa+1(α2)=sa+2(α). It follows that sa(α)=sa+2(α), a contradiction.

Lemma 2.9(see [15]) Let the symbols be the same as before.Then

Lemma 2.10(see [24]) 2 ∈if and only if p ≡ ±1(mod 8).

Now the results on the linear complexity of the sequences defined by (2.3) are summarized in the following three theorems.

Theorem 2.11Let p ≡ 1(mod 8) and q ≡ ?3(mod 8). Then

ProofBy eq.(3.3),it suffices to count the number of roots in{αj: j =0,1,··· ,pq?1}of sa(x).For t ∈R={0}, it is easily verified that

Since p ≡ 1(mod 8) and q ≡ ?3(mod 8), it follows from Lemma 2.10 that 2andand so 2 ∈ D1∪ D3by Lemma 2.5.Thus sa(αt)0 for any t ∈by Lemma 2.6 and Lemma 2.8.In addition, for any t ∈ P we have sa(αt)0 by Lemma 2.7 and Lemma 2.9 (i), but for any t ∈ Q we haveby Lemma 2.7 and Lemma 2.9(ii).We now distinguish the cases t ∈ Q0and t ∈ Q1.It is obviouswhen t ∈ Q0andwhen t ∈ Q1.Since

it follows that sa(αt) = 0 either for all t ∈ Q0or for all t ∈ Q1.In conclusion, the size of the setthen by (3.3) we get that

Theorem 2.12Let p ≡ ?3(mod 8) and q ≡ 1(mod 8).Then

ProofWhen p ≡ ?3(mod 8) and q ≡ 1(mod 8), we have 2 ∈ D1∪ D3by Lemma 2.5,and hence sa(αt)0 for any t ∈by Lemma 2.6 and Lemma 2.8.By the same arguments as in Theorem 2.11, sa(αt)0 for any t ∈ Q and sa(αt) = 0 for half of t ∈ P.Therefore,by (3.3) we have

Theorem 2.13Let p ≡ ?3(mod 8) and q ≡ ?3(mod 8).Then

ProofSince p ≡ ?3(mod 8) and q ≡ ?3(mod 8), it follows from Lemmas 2.7 and 2.9 that sa(αt)0 for any t ∈ P and t ∈ Q.

If 2 ∈D0, then sa(αt)=0 for half of t ∈by Lemma 2.6.If 2D0, then sa(αt)0 for any t ∈by Lemma 2.6.So the desired result follows immediately from (3.3).

4 Conclusion

In this paper,new class of almost balanced binary sequences of period pq is constructed via Whiteman’s generalized cyclotomy of order 4 and classic cyclotomy of order 2.The linear complexity of these sequences is determined.The results show that the proposed sequences have large linear complexity.In addition, since the parameter a in the characteristic set could be any integers in the range of 0 to 3, our construction can generate a number of binary sequences with large linear complexity.