Composition of recursions and nonlinear complexity of periodic binary sequences
We investigate further the new approach towards the classification of periodic binary sequences into nonlinear complexity classes that commenced in the paper by Petrides and Mykkeltveit (Proceedings of SETA'06 international conference on sequences and their applications, 2006). Nonlinear complexity was first introduced by Jansen (Investigations on nonlinear streamcipher systems: construction and evaluation methods, PhD thesis, 1989) and several attempts have since been made to make it of more practical cryptographic interest. In this direction, we will follow with this article. In particular we perform composition of the recursions found in the (2006) article which are related to nonlinear complexity, and prove some of its missing results. Studying the properties of the composition operation for a certain type of recursions is an alternative to study all possible recursions, as required for completing the above mentioned classification. A complete classification will allow, amongst other things, construction of statistical tests to assess the cryptographic strength of binary sequences used in stream ciphers.
recursion nonlinear complexity binary sequence maximum order complexity nonlinear span shift register