Analysis of the Linear Complexity in Pseudorandom Sequence Generators

In this paper, binary sequences generated by nonlinearly filtering maximal length sequences are studied. Specifically, the parameter linear complexity of the filtered sequences has been considered and analyzed. In fact, a method of computing all the nonlinear filters that generate sequences with a cryptographically large linear complexity has been developed. The procedure is based on the concept of equivalence classes of nonlinear filters and on the addition of filters from different classes. Three distinct representations of nonlinear filters have been systematically addressed. The method completes the class of nonlinear filters with guaranteed linear complexity found in the cryptographic literature.