Nonlinear Complexity Of A Class Of Automatic Sequences

Stream cipher is a kind of symmetric cipher algorithms,which has advantages in fast encryption and decryption,strong operability,etc.It is widely used in cryptosystem.The security feature of stream cipher depends on the randomness of key stream,and the nonlinear complexity is an important criterion to measure a given sequence.The nonlinear complexity of a sequence is defined as the length of the shortest nonlinear feedback shift register that can generate the sequence.Automatic sequences are a class of special infinite sequences,the research shows that the randomness of automatic sequences is between random sequences and periodic sequences but not as complex as random sequences.In this thesis,we will discuss the nonlinear complexity profile of a kind of automatic sequences S(k,a),which is determined by parameters k and a.When k=2,a=3,the automatic sequence is a Rundin-Shapiro sequence.According to the result of Sun Z and Winterhof A,the nonlinear complexity profile of the sequence is very large and has a simple expression.During looking for the longest subsequences that occur at least twice and have different successors,we first calculate the nonlinear complexity profile of the automatic sequences S(k,a)in case of the parameters k=2 and a?0,1,2(mod 4).Combined with the result of Sun Z and Winterhof A,the problem of the nonlinear completely of the automatic sequences S(k,a)when the parameter k=2 are completely solved.Then,we calculate the nonlinear complexity profile of the automatic sequences S(k,a)in case that the parameters k>2,a(28)2^k-1.Based on the results,the research of the security of automatic sequences has been greatly improved,more examples for some related research of the nonlinear feedback shift registers are provided as well.