Linear Complexity and Autocorrelation of two Classes of New Interleaved Sequences of Period $2N$
Shidong Zhang Tongjiang Yan
cs.CR


Adjoint sensitivity analysis on chaotic dynamical systems by Non-Intrusive Least Squares Adjoint Shadowing (NILSAS)
    [
    December 30, 2023
===================================================================================================================

headings

 The autocorrelation and the linear complexity of a key stream sequence in a stream cipher are important cryptographic properties. Many sequences with these good properties have interleaved structure, three classes of binary sequences of period 4N with optimal autocorrelation values have been constructed by Tang and Gong based on interleaving certain kinds of sequences of period N. In this paper, we use the interleaving technique to construct a binary sequence with the optimal autocorrelation of period 2N, then we calculate its autocorrelation values and its distribution, and give a lower bound of linear complexity. Results show that these sequences have low autocorrelation and the linear complexity satisfies the requirements of cryptography.


 

Keywords: Linear complexity, minimal polynomial, interleaved sequences, the autocorrelation value




§ INTRODUCTION

A sequence u={u_i}_i=0^∞, if u satisfies u_i+N=u_i, where u_i∈{0,1}, is called a binary sequence of period N. The set U={0≤ i <N:u_i=1} is called thecharacteristic set of u. If |U|=N/2 for even N or |U|=(N± 1)/2 for odd N, where |U| denotes the cardinality of U, then such a sequence u is called a balanced sequence.
Let u={u_i}_i=0^∞ and v={v_i}_i=0^∞ be two sequences of period N. The periodic correlation between them is defined by

    R_u, v(τ) = ∑_i = 0^N-1(-1)^u(i)+v(i+τ), 0≤τ<N,

where the addition t+τ is performed modulo N. R_u, v(τ) is called the (periodic) cross-correlation function of u and v. If u = v, R_u, v(τ) is called the (period) autocorrelation function of u, denoted by R_u(τ) for short <cit.>.

According to the remainder of N modulo 4, the optimal values of out-of-phase autocorrelations of binary sequences are classified into four types as follows:
(1) R_a(τ)=-1 if N≡3  4; (2) R_a(τ)∈{-2, 2} if N≡2  4; (3) R_a(τ)∈{1, -3} if N≡1  4; (4) R_a(τ)∈{0, -4,4} if N≡0  4, where 0<τ<N. For the second case, it is exactly the autocorrelation of the sequence we constructed. Binary sequences with low correlation have very significant applications in communication systems, radar and cryptography <cit.>. Sequences should have low autocorrelation to eliminate the effect of multipath, and low cross-correlation to extract the desired user's signal from the rest of users.

In cryptographic applications, the linear complexity of a sequence is considered as the most important property. Generally speaking, a sequence with large linear complexity is favorable for cryptography to resist the well-known Berlekamp-Massey algorithm <cit.>, and the sequence can be recovered easily if the linear complexity is less than half the period <cit.>.  It is worth to know the linear complexity of a sequence before applying them in any applications.

Many sequences with these good properties have interleaved structure, interleaved technique is widely used to analyse and design sequences <cit.>. In 2008, based on the interleaved structure, Yu and Gong <cit.> presented a family of binary sequences of period 4N with optimal autocorrelation magnitude, i.e., R_s(τ)∈{0,±4} for all 0<τ<n, and they also determined the linear complexity of the proposed sequence. Later, Tang and Gong <cit.> generalized the sequences in <cit.> and obtained more binary sequences of period 4N with optiaml autocorrelation value.

In this paper, using the interleaved technique, We construct the binary sequence with the otimal autocorrelation of period 2N, and we calculate its autocorrelation value and distribution, and give a lower bound of linear complexity. Results show that these sequences have low autocorrelation and the linear complexity satisfies the requirements of cryptography.

This paper is organized as follows. Section 2 introduces some related definitions and lemmas which would be used later. In Section 3, We first give the interleaved structure, then calculate the autocorrelation value and its distribution of the sequences. In Section 4, we give a lower bound of linear complexity. In Section 5, we give a Remark.  Conclusions are given in Section 6.



§ PRELIMINARIES



 §.§ Interleaved Sequence

<cit.>
 Let {a_0,a_1,⋯,a_T-1} be a set of T sequences of period N. An N × T matrix U is formed by placing the sequence a_i on the ith column, where 0 ≤ i ≤ T-1. Then one can obtain an interleaved sequence u of period NT by concatenating the successive rows of the matrix U. For simplicity, the interleaved sequence u can be written as

    u=𝐈(a_0,a_1,⋯,a_T-1),

where 𝐈 denotes the interleaved operator.


Let s = (s(i))_i = 0^∞ be a sequence over a field 𝔽_2. A polynomial of the form

    f(x)=1+c_1x+c_2x^2+ ⋯ +c_rx^r∈𝔽[x]

is called the characteristic polynomial of the sequence s if

    s(i)=c_1s(i-1)+c_2s(i-2)+ ⋯ +c_rs(i-r), ∀ i ≥ r.


Among all the characteristic polynomials of s, the monic polynomial m_s(x) with the lowest degree is called its minimal polynomial. The linear complexity of s is defined as the degree of m_s(x), which is described as LC(s).

Let s = (s(0),s(1), ⋯ , s(n-1)) be a binary sequence of period n and define the sequence polynomial

    S(x) = s(0)+s(1)x+ ⋯ +s(n-1)x^n-1.


Then, its minimal polynomial and linear complexity can be determined by Lemma 1.

<cit.> Assume a sequence s of period n with sequence polynomial S(x) is defined by Equation (<ref>). Then

  
  * the minimal polynomial is m_s(x)= x^n-1/gcd(x^n-1,s(x));
  
  * the linear complexity is LC(s)=n-deg(gcd(x^n-1,S(x))),

where gcd(x^n-1,S(x)) denotes the greatest common divisor of x^n-1 and S(x).


<cit.> Let a be a binary sequence of period n, and s_a(x) be its sequence polynomial. Then

  
  * S_b(x) = x^n-τS_a(x),  if b = L^τ(a);
  
  * S_b(x) = S_a(x)+x^n-1/x-1,  if b  is   the   complement  
 sequence   of  a;
  
  * S_u(x) = S_a(x^2)+xS_b(x^2),  if u = 𝐈(a,b).



<cit.> Let m be an integer. Correlation of sequences satisfies the following properties:

  
  * R_L^m(a)b(τ)=R_ab(τ-m);
  
  * R_aL^m(b)(τ)=R_ab(τ+m);
  
  * R_ab(τ)=R_ab(τ+N)=R_ba(N-τ);
  
  * R_ab(τ)+R_ab̅(τ)=R_ab(τ)+R_a̅b(τ)=0.
  
  

The autocorrelation of u=𝐈(a,b)

    R_u(τ)=
    
    R_a(τ/2)+R_b(τ/2)    τ, 
    
    R_ab(τ-1/2)+R_ba(τ+1/2)    τ.


Proof
For the case τ is even, we can know the location of sequence a is replaced by L^τ/2(a), and the location of sequence b is replaced by L^τ/2(b), in other words, 𝐈(a,b) becomes 𝐈(L^τ/2(a),L^τ/2(b)), so by the definition, we have R_u(τ)=R_a(τ/2)+R_b(τ/2).

For the case τ is odd, we can know the location of sequence a is replaced by L^τ-1/2(b), and the location of sequence b is replaced by L^τ+1/2(a), in other words, 𝐈(a,b) becomes 𝐈(L^τ-1/2(b),L^τ+1/2(a)), so by the definition we have R_u(τ)=R_ab(τ-1/2)+R_ba(τ+1/2). Hence, we have completed the proof of Lemma 4.

Let N be a prime and β a primitive element of the integer residue ring Z_N={0,1,⋯,N-1}, such that for any j∈ Z_N \{0}, there exists an integer k satisfying j=β^k. Denote by D_0 a multiplicative subgroup generated by β^4, i.e., D_0={β^4k:0≤ k<f}. Then, Z_N^*=Z_N \{0} can be decomposed as Z_N^*=∪_j=0^3D_j, where D_j={β^4k+j:0≤ k<f} is called the cyclotomic class j of order 4.

<cit.> Let u and v be two binary sequences with characteristic sets D_0∪ D_1 and D_1∪ D_2 respectively, and u(0)=0 and v(0)=0. Then we have

    R_u(τ)={[            N         τ=0,;        -1-2y τ∈ D_0∪ D_2,;        -1+2y τ∈ D_1∪ D_3, ].


    R_v(τ)= {[            N         τ=0,;        -1+2y τ∈ D_0∪ D_2,;        -1-2y τ∈ D_1∪ D_3, ].

and

    R_uv(τ)={[         -3    τ∈ D_2,;          1 otherwise. ].

   

<cit.> Let S_u(x) and S_v(x) be the sequence polynomials of sequences u and v, α a primitive Nth root of unity over the field GF(2^m), that is the splitting field of x^N-1. Then

    S_u(α^j)= {[   S_u(α)  j∈ D_0,;   S_v(α)  j∈ D_1,; 1+S_u(α)  j∈ D_2,; 1+S_v(α)  j∈ D_3,;  N-1/2 2     j=0, ].


    S_v(α^j)= {[   S_v(α)  j∈ D_0,; 1+S_u(α)  j∈ D_1,; 1+S_v(α)  j∈ D_2,;   S_u(α)  j∈ D_3,;  N-1/2 2     j=0, ].


where


S_u(x)=∑_i∈ D_0∪ D_1 x^i,

S_v(x)=∑_i∈ D_1∪ D_2 x^i.



<cit.> S_u(α)∈{0,1} if and only if 2∈ D_0.


 S_v(α)∈{0,1} if and only if 2∈ D_0.

Proof
Since (D_0,·) is a group, we have qD_0=D_0 and q^-1∈ D_0 for any q∈ D_0. Hence

    S_v(α^q)
       =   ∑_i∈ D_1∪ D_2α^qi
       =   ∑_y∈ D_1∪ D_2α^y
       =   S_v(α).

Since the characteristic of the field GF(2^m) is 2, it follows that (S_v(α))^2=S_v(α^2). From the above, we have S_v(α^2)=S_v(α) if and only if 2∈ D_0, that is to say S_v(α)∈{0,1} if and only if 2∈ D_0. So we have completed the proof of Lemma 8.



§ NEW CONSTRUCTION METHOD AND THE AUTOCORRELATION VALUES AND DISTRIBUTION 

In this section, assume that u and v are two binary sequences with characteristic sets D_i∪ D_j and D_j∪ D_l respectively, and we define

    u'(t)={[  u(t) t≠ 0,;     1  t=0. ].

 
    v'(t)={[  v(t) t≠ 0,;     1  t=0. ].

 we proposes one new way to construct sequences, then we calculate its autocorrelation values and distribution.



 §.§ New Construction Method and Sequence Correspondence

Let N=4f+1, where f=y^2 is odd and N≥ 5, and sequences u and v are the same as before, new construction as the following:

    s=𝐈(u,L^(N+1)/2v),


    s'=𝐈(u',L^(N+1)/2v).


Compare the above two constructions, we can know that when s'=𝐈(u',L^(N+1)/2v), the sequence is a balanced sequence, then we give the autocorrelation value for different characteristic sets for s', which is similarly demonstrated when s=𝐈(u,L^(N+1)/2v). Below we calculate their autocorrelation of s' in different situations.



 §.§ the Autocorrelation Values and Distribution


𝐂𝐚𝐬𝐞   1. (i,j,l)=(0,1,2), and (i,j,l)=(2,1,0).

Proof
When (i,j,l)=(0,1,2), we know that the characteristic sets of u' and v are D_0∪ D_1 and D_1∪ D_2 respectively.
Let β be a primitive element of the integer residue ring Z_N={0,1,⋯,N-1}, such that for any j∈ Z_N \{0}, there exists an integer k satisfying j=β^k. We have 1=β^4f, since ord(β)=N-1 and f is odd, f can be empressed by f=2t+1, t is an integer, so (β)^4t+2=-1, we have -1∈ D_2. For the sequences u and v, since -1∈ D_2, by Lemmas 3(3) and 5, we know:

    R_vu(τ)={[         -3    τ∈ D_0,;          1 otherwise. ].


For the autocorrelation values of sequences u' and v', since the only difference between sequences u and u' is u'(0)=1, we only need to know the values of u'(τ) and u'(N-τ), since -1∈D_2, u'(τ) and u'(N-τ) take different values of 0 and 1, we have (-1)^u'(0)+u'(τ)+(-1)^u'(0)+u'(N-τ)=0, so we have R_u(τ)=R_u'(τ), similarly we know R_v(τ)=R_v'(τ), for the cross-correlation value of sequences u and v', we only to know v(τ) and v(N-τ), then by Lemma 5 and Equation (6), we have:

    R_u'v(τ)={[          3    τ∈ D_1,;         -1 otherwise. ].


    R_vu'(τ)={[          3    τ∈ D_3,;         -1 otherwise. ].


By Lemma 4, we know:

    R_s(τ)=
    
    R_u(τ/2)+R_v'(τ/2)   τ,
    
    R_u'v(τ+N/2)+R_vu'(τ+N/2)   τ.


Then by Lemma 5, we have

    R_s(τ)={[              2N            τ=0,;              -2         τ,τ≠ 0,;              -2  τ, τ+N/2∈ D_0,;               2 τ, τ+N/2∈ D_1 ,;              -2  τ, τ+N/2∈ D_2,;               2  τ, τ+N/2∈ D_3,;              -2            τ=N.;                 ].


When (i,j,l)=(2,1,0), compared to (i,j,l)=(0,1,2), their difference is that the position of the base sequence has changed, so the autocorrelation values and cross-correlation values of the base sequences are unchanged, then by Equation (7), the autocorrelation values of the sequence s is the same as above.


𝐂𝐚𝐬𝐞   2. (i,j,l)=(1,2,3),(i,j,l)=(3,2,1).

Proof
According to the proof of case 1, we can know that when the characteristic sets (i,j,l)=(1,2,3) and (i,j,l)=(3,2,1), the autocorrelation values of the sequences are equal, and we can know the autocorrelation values of the base sequence:

    R_u'(τ)={[            N         τ=0,;        -1+2y τ∈ D_0∪ D_2,;        -1-2y τ∈ D_1∪ D_3, ].


    R_v(τ)= {[            N         τ=0,;        -1-2y τ∈ D_0∪ D_2,;        -1+2y τ∈ D_1∪ D_3, ].


The cross-correlation values of the base sequence:

    R_u'v(τ)={[          3    τ∈ D_2,;         -1 otherwise. ].


    R_vu'(τ)={[          3    τ∈ D_0,;         -1 otherwise. ].


Then by Equation (7), we have

    R_s(τ)={[              2N            τ=0,;              -2         τ,τ≠ 0,;               2  τ, τ+N/2∈ D_0,;              -2 τ, τ+N/2∈ D_1 ,;               2  τ, τ+N/2∈ D_2,;              -2  τ, τ+N/2∈ D_3,;              -2            τ=N.;                 ].


The above is the autocorrelation function of sequences s', the sequences s can be similarly demonstrated, in the case of the same characteristic set, except for τ=N, the autocorrelation values are opposite to each other, in other cases, the autocorrelation values are the same, and its proof is omitted for simplicity. Next we give the autocorrelation distribution of the sequence s.

The autocorrelation value distribution of s=𝐈(u',L^(N+1)/2v):

    R_s(τ)={[            2N      1  time,;            -2 7N-3/4  time,;             2 N-1/4  times. ].

When s=𝐈(u,L^(N+1)/2v):

    R_s(τ)={[            2N      1  time,;            -2 7N-7/4  time,;             2 N+3/4  times. ].

 

Proof
Let Q denote the quadratic residual set of modulo N, P be a quadratic non-residual set for modulo N, then Q=D_0∪ D_2, P=D_1∪ D_3, since -1∈ D_2, and N is odd, if a∈ Q is odd(even), then N-a∈ Q, and N-a is even(odd). Thus half elements in Q are even(odd). So is P. Then by Equations (8) and (9), the Equation (10) is proved. When s=𝐈(u,L^(N+1)/2v) similarly demonstrated. So Theorem 1 is proved.



§ A LOWER BOUND OF LINEAR COMPLEXITY

Since N=4f+1, 2∉ D_0 ∪ D_2, then we only consider the case 2∉ D_0, u' and v are two binary sequences with characteristic sets D_0∪ D_1 and D_1∪ D_2 respectively, then we have:
The minimal polynominls of u' and v:

  
  * m_u'(x)=x^N-1;
  
  * m_v(x)=x^N-1/x-1.
  
  
Proof
Let α be a primitive Nth root over GF(2^m) as before. Since N=4f+1, 2∉ D_0, by Lemmas 7 and 9, S_u'(α) ∉{0,1} and S_v(α) ∉{0,1}, so {α^j: 0<j≤N-1} are not the roots of S_u'(α) and S_v(α). Since S_u'(α^0)=(N-1/2+1)=1  2, S_v(α^0)=N-1/2=0  2, we have gcd(S_u'(x),x^N-1)=1, gcd(S_v(x),x^N-1)=x-1, then by the Lemma 1, we have completed the proof.

When 2∈ D_1, we have S_v(x^2)=S_u'(x), and 2∈ D_3, we have S_u'(x^2)=S_v(x).
  
Proof
When 2∈ D_1,

    S_v(x^2)
       =   ∑_i∈ D_1∪ D_2 x^2i
       =   ∑_g∈ D_2∪ D_3 x^g
       =   S_u(x);

 When 2∈ D_3,

    S_u(x^2)
       =   1+∑_i∈ D_0∪ D_1 x^2i
       =   1+∑_h∈ D_0∪ D_3 x^h
       =   S_v(x).

We have completed the proof.


Let s' be the interleaved sequence of period 2N as before and S_s'(x) is the sequence polynomial of s', s'=𝐈(u',L^(N+1)/2v). Then the linear complexity LC(s') is bounded by LC(s') ≥ 2N-4, when s=𝐈(u,L^(N+1)/2v), the linear complexity LC(s) is bounded by LC(s) ≥ 2N-5.

Proof
Let S_u'(x) and S_v(x) be the sequence polynomials of u' and v, the characteristic sets (i,j,l)=(0,1,2),(1,2,3),(2,1,0) or (3,2,1), α be a primitive Nth root of unity over the field GF(2^m). Let us take the characteristic set (i,j,l)=(0,1,2) as an example, and other cases can be similarly proved. By Lemma 2(3), we have

    gcd(S_s'(x),x^2N-1)
       =   gcd((S_u'(x^2)+x^N+1/2S_v(x^2),x^2N-1).


Since S_s'(α^0)=1, then gcd(S_s'(α^0),((α^0)^2N-1))=1, so x-α^0 is not a common factor. Then we consider whether {α^j:j∈ Z_N^*} is the common root of S_s'(x) and x^2N-1).

When 2∈ D_1, by Corollary 3, we have
 
    gcd(S_u'(x^2)+x^N+1/2S_v(x^2), x^2N-1)
       =   gcd(S_u'(x)(S_u'(x)+x^N+1/2),x^2N-1).


Since gcd(S_u'(x),x^N-1)=1, so we only consider gcd(S_u'(x)+x^N+1/2,x^2N-1), for {α^j:j∈ D_0}, (α)^j.(N+1)/2 are not equal to each other, then by Lemma 6,for {α^j:j∈ D_0}, S_u'(x) is the same value, we can know in the set {α^j:j∈ D_0}, only one number may be the root of the equation S_u'(x)+x^N+1/2=0. Similarly, there may be only three roots for the other three cases, so the linear complexity is bounded by LC(s') ≥ 2N-4.

When 2∈ D_3, then by Corollary 3, we have

    gcd(S_u'(x^2)+x^N+1/2S_v(x^2), x^2N-1)
       =   gcd(S_v(x)(1+x^N+1/2S_v(x)),x^2N-1).


Since gcd(S_v(x),x^N-1)=1, we only consider gcd(1+x^N+1/2S_v(x),x^2N-1), according to the above proof, for {α^j:j∈ D_0}, S_v(x) is the same value, we can know in the set {α^j:j∈ D_0}, only one number may be the root of the equation 1+x^N+1/2S_v(x). Similarly, there may be only three roots for the other three cases, so the linear complexity is bounded by LC(s') ≥ 2N-4. Hence, we have completed the proof of Theorem 2.

When s=𝐈(u,L^(N+1)/2v), the proof of linear complexity is the same as for s'=𝐈(u',L^(N+1)/2v), the only difference between s=𝐈(u,L^(N+1)/2v) and s'=𝐈(u',L^(N+1)/2v) is that 1 is the root of s=𝐈(u,L^(N+1)/2v), so the linear complexity is bounded by LC(s) ≥ 2N-5.



§ REMARK

s and s' possess optiaml autocorrelation if and only if its characteristic set is an almost difference set, sequences s and s' can also be obtained by the results in <cit.>.



§ CONCLUSION

In this paper, we use the interleaving technique to construct a binary sequence with the optimal autocorrelation of period 2N. From the section 3, we can conclude that this sequence is optimal, the sequence has low autocorrelation values, and we give the distribution of the autocorrelation values. Especially, in section 4, based on the discussion of roots of the sequence polynomials over the field GF(2^m), we give a lower bound of linear complexity, the linear complexity can be reached 2N-4, far larger than half of a period. Results show that these sequences have low autocorrelation and the linear complexity satisfies the requirements of cryptography.



§ ACKNOWLEDGMENTS

The project is supported by the open fund of Fujian Provincial Key Laboratory of Network Security and Cryptology Research Fund (Fujian Normal University)
(No.15002), the Natural Science Fund of Shandong Province (No.ZR2014FQ005), the National Natural Science Foundations of China(No.61170319)and the Fundamental Research Funds for the Central Universities (No.11CX04056A, 15CX08011A,15CX05060A).

tocchapterREFERENCES
10


Ref1
K. T. Arasu, Cunsheng Ding, Tor Helleseth, P. Vijay Kumar, Halvard Martinsen, “Almost difference sets and their sequences with optimal autocorrelation,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 2934–2943, 2001.

Ref2
P. Z. Fan and M. Darnell, Sequence Design for Communications Applications. London, U.K.: Wiley. Press 1996.

Ref3
Yang Yang, Xiaohu Tang and Zhengchun Zhou, “The Autocorrelation Magnitude of Balanced Binary Sequence Pairs of Prime Period N≡ 14 With Optimal Cross-Correlation,” IEEE Communications Letters, vol. 19, no. 4, pp. 585–588, 2015.

Ref4
S. W. Golomb and Guang Gong, Signal Design for Good Correlation-for Wireless Communication, Cryptography and Radar. Cambridge, U.K.: Cambridge Univ. Press, 2005.

Ref5
Xiaohu Tang and Cunsheng Ding, “New classes of balanced quaternary and almost balanced binary sequences with optimal autocorrelation value,”  IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6398–6405, 2010.

Ref6
James L. Massey, “Shift-register synthesis and BCH decoding,” IEEE Transactions on Information Theory, vol. 15, no. 1, pp. 122–127, 1969.

Ref7
Jianqin Zhou and Wei Xiong, “An algorithm for computing m-tight error linear complexity of sequences over GF(pm) with period pm,” International Journal of Network Security, vol. 15, no. 1, pp. 59-63, 2013.

Ref8
Nian Li and Xiaohu Tang, “On the linear complexity of binary sequences of period 4N with optimal autocorrelation value/magnitude,” IEEE Transactions on Information Theory, vol. 57, no. 11, pp. 7597–7604, 2011.

Ref9
T Helleseth  K Yang, “On Binary Sequences of Period n = p^m-1 with Optimal Autocorrelation,”Springer London. Press, pp. 209–217, 2002.

Ref10
Ying Cai and Cunsheng Ding, “Binary sequences with optimal autocorrelation,” Theoretical Computer Science, vol. 410, no. 24/25, pp. 2316–2322, 2009.

Ref11
H. D. Lke, H. D. Schotten, and H. Hadinejad-Mahram, “Binary and quadriphase sequence with optimal autocorrelation: A survey,” IEEE Transactions on Information Theory, vol. 49, no. 12, pp. 3271–3282,  2003.

Ref12
Xiaohu Tang and Guang Gong, “New constructions of binary sequences with optimal autocorrelation value/magnitude,” IEEE Transactions on Information Theory, vol. 56, no. 3, pp. 1278–1286, 2010.

Ref13
Jong-Seon No, Habong Chung, Hong-Yeop Song, Kyeongcheol Yang, Jung-Do Lee, Tor Helleseth, “New construction for binary sequences of period p^m-1 with Optimal autocorrelation using (z+1)^d+az^d+b,” IEEE Transactions on Information Theory, vol. 47, no. 4, pp. 1638–1644, 2001.

Ref14
Gohar M. M. Kyureghyan, Alexander Pott, “On the Linear Complexity of the Sidelnikov-Lempel-Cohn-Eastman Sequences,” Des. Codes Cryptography, vol. 29, no. 1-3, pp. 149–164, 2003.

Ref15
Rudolf Lidl and Harald Niederreiter, Finite Fields (Encyclopedia of Mathematics and Its Applications ). New York: Cambridge University Press, 1997.

Ref16
V.M.Sidelnikov, “Some k-valued pseudo-random sequences and nearly equidistant codes,” Problems of Information Transmission, vol. 5, no. 1, pp. 12–16, 1969.

Ref17
Tongjiang Yan and Guang Gong, “Some Notes on Constructions of Binary Sequences with Optimal Autocorrelation,” http://arxiv.org/abs/1411.4340, 2014.

Ref18
Abraham Lempel, Martin Cohn, Willard L. Eastman, “A class of balanced binary sequences with optimal autocorrelation properties,” IEEE Transactions on Information Theory, vol. 23, no. 1, pp. 38–42, 1977.

Ref19
Xuan Zhang, Qiaoyan Wen, and Jing Qin, “Constructions of sequences with almost optimal autocorrelation magnitude,” Journal of Electronics and Information Technology, vol. 33, no. 8, pp. 1908–1912, 2011.

Ref20
Wilfried Meidl, Arne Winterhof, “Some Notes on the Linear Complexity of Sidel'nikov-Lempel-Cohn-Eastman Sequences,” Des. Codes Cryptography, vol. 38, no. 2, pp. 159–178, 2006.

Ref21
Cunsheng Ding, Tor Helleseth and Kwok-Yan Lam, “Several Classes of Binary Sequences with Three-Level Autocorrelation,” IEEE Transactions on Information Theory, vol. 45, no. 7, pp. 2606–2612, 1999.

Ref22
Qi Wang and Xiaoni Du, “The linear complexity of binary sequences with optimal autocorrelation,” IEEE Transactions on Information Theory, vol. 56, no. 12, pp. 6388–6397, 2010.





Shidong Zhang biography.
 Shidong Zhang was born in 1992 in Shandong Province of China. He was graduated from Jining University . He will study for a postgraduate degree at China University of Petroleum in 2016. And his tutor is Tongjiang Yan. Email:zhangshdo1992@163.com


Tongjiang Yan biography.
Tongjiang Yan was born in 1973 in Shandong Province of China. He was graduated from the Department of Mathematics, Huaibei Coal-industry Teachers College, China, in 1996. In 1999, he received the M.S. degree in mathematics from the Northeast Normal University, Lanzhou, China. In 2007, he received the Ph.D. degree in Xidian University. He is now a professor of China University of Petroleum. His research interests include cryptography and algebra. Email:yantoji@163.com 

