The Nonlinear Complexity Profile Of A Class Of Automatic Sequences

Stream ciphers have been widely used in cryptographic systems since their algorithms are simple,they are easy to implement and efficient i n e ncryption a nd decryption.The security of stream ciphers most depends on the randomness of the key stream.However,the nonlinear complexity of sequences is one of the important indicators to measure the randomness.In general,a sequence with small nonlinear complexity is easy to be predicted.Automatic sequence is a kind of non-periodic infinite length sequence.Two famous automatic sequences are Thue-Morse sequence and Rudin-Shapiro sequences.These two sequences have large nonlinear complexity and are widely applied in practice.This motives us to explore the nonlinear complexity of other automatic sequences.Based on the properties of nonlinear complexity,this paper first d etermine the nonlinear complexity of a class of automatic sequences.However,the expansion complexity of these sequence is small.So they can be easy to predicted in applications.New sequences can be obtained by these sequences along squares,which are not automatic sequences.The expansion complexity of these sequences may reach infinite.To further discuss the unpredictability,this paper presents a lower bound of the nonlinear complexity of these sequences.