On The Nonlinear Complexity Of Periodic Sequences On The Basis Of Finite Length Sequences

Stream cipher is a class of symmetric cryptosystem which has been widely used,the security of stream cipher depends largely on the characteristic of the keystream,pseudorandom sequences are usually utilized as keystreams in stream cipher.The nonlinear complexity of a sequence is defined as the length of the shortest feedback shift register that can generate it,which is one of the most important criterion used in assessing the randomness of a sequence.To ensure the security of the communication,the keystream sequences must have high nonlinear complexity.A periodic sequence can always be regarded as the infinite expansion of it's single period,it motivates us to characterize the nonlinear complexity profile of the periodic sequences from the perspective of finite length sequences,thereby possibly inspiring us to construct periodic sequences with high nonlinear complexity.In this paper,we concentrate on the finite length sequence with nonlinear complexity no less than the half of it's length.By investigating the number of subsequences with the length one less than their nonlinear complexity,we determine the structural properties of this kind of sequences.When this kind of finite length sequences satisfy some certain restricted condition,we consider the nonlinear complexity of the periodic sequence that contains the former finite length sequence as it's single period.Based on the structural properties of the finite length sequence,by investigating the pattern of these repeated subsequences,we analyze the changes on the nonlinear complexity of the periodic sequences.We also determine the numerical expression of the nonlinear complexity of the periodic sequences.