An algorithm for the k-error linear complexity of binary sequences with period 2n

Certain applications require pseudo-random sequences which are unpredictable in the sense that recovering more of the sequence from a short segment must be computationally infeasible. It is shown that linear complexity is useful in determining such sequences. A generalized linear complexity that has application to the security of stream ciphers is proposed, and an efficient algorithm is given for the case in which the sequence is binary with period 2ⁿ. This algorithm generalizes an algorithm presented by R.A. Games and A.H. Chan (1983)