The Linear Complexity Research On Pseudo-random Sequences

Pseudo-random sequence can be generated by a linear feedback shift register or a feedback with carry shift register,and it has a wide application.It is often used in CDMA,GPS,software testing,stream cipher.Linear complexity and 2-adic complexity are important indicators that measure pseudo-random properties of sequences.In the stream cipher system,according to the B-M algorithm,the linear complexity of a safe key stream sequence must not be less than half of a period.Similarly,based on the rational approximation algorithm proposed by A.Klapper,2-adic complexity has been viewed as one of the most important security criteria of sequences.If the 2-adic complexity of a key stream sequence is less than half of a period,it may bring risks for cryptography and communication systems.Hence investigating linear complexity and 2-adic complexity of some sequences should be significant.This paper mainly considers the linear complexity and 2-adic complexity of some binary sequences with the construction of(?).Main results are as follows:(1)Based on the idea of cyclotomic,we give the linear complexity and minimal polynomials of a class of binary interleaved sequences for the case of(a,b,c,d)=(t',t,t',t).Results show that the linear complexity of these sequences satisfies the requirements of cryptography.(2)Based on the theories of polynomials,this paper computes the 2-adic complexities of two classes of binary interleaved sequences for the case of(a,b,c,d)=(l,l',l,l')and(a,b,c,d)=(l,l,l,l).Results show that the 2-adic complexities of these sequences equals to their periods.(3)This paper verifies the theoretical value for the case(a,b,c,d)=(t',t,t',t)by using the Magma soft.And it shows that the experimental value and theoretical value is consistent.