Nonlinear Complexity Of Sequences And Its Algorithm

To serve as keystream in a stream cipher,Binary sequences should have properties such as high unpredictability,good balance,low correlation,and long period among others.One of the most important criterions used to evaluate the security of a stream cipher is its complexity,which is defined to be the length of the shortest feedback shift register that generates the sequence.If the feedback shift register is nonlinear,we call it nonlinear complexity.On the contrary,if the feedback shift register is linear,we call it linear complexity.Generally,for a periodic sequence,its nonlinear complexity is al-ways less than its linear complexity.In order to be robust against Berlekamp-Massey algorithm,sequences must have large linear complexity,which has aroused widespread attention and stimulated deep study by many researchers.However sequences with large linear complexity can be generated by much shorter nonlinear feedback shift registers,which means that the sequence has low nonlinear complexity.Consequently,construct-ing periodic sequences with large nonlinear complexity is of great significance.In section one,we establish the necessary background,clarify its importance and introduce the current research status at home and abroad on the nonlinear complexity of sequences.In section two,we introduce the related information about finite fields,linear complexity and nonlinear complexity.In section three,we discuss two types of binary periodic sequences whose nonlinear complexity is less than the linear complex-ity by one or two.Then,by Lagrange interpolation,we construct periodic sequences with period N = 2m-1 whose nonlinear complexity is less than its linear complexity by one.Finally an algorithm has been proposed for calculating the nonlinear complex-ity.In section four,based on previous work of Panagiotis Rizomiliotis and Nicholas Kolokotronis,we extend the conclusions to non binary sequences.