Study On The Pseudorandom Properties Of K-ary Sidel’nikov Sequence

The construction of pseudorandom sequences and the study of the randomness of sequences are the core problems of cryptography and play an very important role in information science and computer networks.It is of great theoretical value and practical significance to construct new pseudorandom sequences or to study the pseudorandomness of existing sequences.Let E_N be a finite sequences of k symbols E_N=（e₁,e₂,…,e_N）∈A^N,where A={a₁,a₂,***,a_k}（k∈N,k≥2）is a finite set of k symbols.Letε={ε₁,ε₂,…,ε_k} be the set of the k-th roots of unity and let T denote the set of bijections φ:A?ε.The ε-correlation measure of order l of E_N is defined as where the maximum is taken over all φ=（φ₁,…,φ_l）∈F^l,D=（d₁,…,d_l）and M with 0≤d₁<…<d_l≤N-M.In this paper we shall study the lower bound of correlation measures of sequences of k symbols by using and developing the methods in the literature.Let q be a prime power,F_q be a finite field,g be a primitive element in F_q and let k>1 be a divisor of q-1.The cyclotomic classes of order k are defined by D₀={g^lk:0≤l≤q-1/k-1} and D_i=gⁱD₀,1≤i≤k-1.Sidel,nikov sequence S_q-1=｛s₁,s₂,…,s_q-1 as follows:Many scholars have studied the autocorrelation,linear complexity,and other properties of the Sidel’nikov sequence.In this paper we study the pseudorandom properties of Sidel’nikov sequences S_q-1.Our results show that Sidel’nikov sequences enjoy good well-distribution measure and correlation measure.Furthermore,we prove that the set of k-ary Sidel’nikov sequences is collision free and possesses the strict avalanche effect property provided that k=0(q^1/4).For integers c₁,c₂,i with 1≤c₁,c₂≤M-1 and 1≤i≤q-2.Scholars constructed and studied new families of k-ary sequences based on Sidel’nikov sequences u_c1,c2;i（t）=c₁s（t）+c₂s（t+i）,t=0,1,…,q-2,v_c1,c2;i（t）=c₁s（t）+c₂s（-t+i）t=0,1,…,q-2.In this paper we further study the pseudorandom properties of these sequences and show that they are asymptotically balanced if and only if gcd（c₁,c₂,M）|a and have asymptotical uniform pattern distributions if gcd（c₁c₂,M）|a.Lower bounds estimation of linear complexity of the u_c1,c2;i（t）,v_c1,c2;i（t）sequences are also studied.