The Error Linear Complexity Spectra Of Binary Sequences With Period P～n

Stream cipher is an main and important part of cryptography. In stream ciphers, the linear complexity and the k-error linear complexity play an important role for judging the cryptographic strength of a sequence, and some correlative algorithms are proposed in succession, such as Berlekamp-Massey algorithm, Games-Chan algorithm, Stamp-Martin algorithm, and so on.For binary sequences with period 2~n, Lauder and Parterson first introduced the concept of the error linear complexity spectrum, and they proposed the Lauder-Parterson algorithm for determining the error linear complexity spectra of binary sequences with period 2~n. As a complexity measure, the error linear complexity spectrum can reveal how the linear complexity of a sequence varies as an increasing number of the bits of the sequence are changed. It is interest to investigate the distribution of the error linear complexity spectra for random sequences of a qiven period, and it is interest to find an efficient algorithm for determining the the error linear complexity spectra of the sequence.In this paper, for binary sequences with period p~n, where 2 is a primitive root(mod p~2), the error linear complexity spectrum is analysed on the base of the known algorithms of the linear complexity and the A;-error linear complexity, and a fast algorithm for determining the error linear complexity spectrum is presented. In addition, how to choose an error sequence to balance the number of 0 and 1 of a sequence with the the linear complexity and the k- error linear complexity remain high is discussed, and correlative algorithms are presented also.