Abstract: Not only should cryptographically strong sequences have a large linear complexity, but also the change of a few terms should not cause a significant decrease in linear complexity. This requirement leads to the concept of the k-error linear complexity of periodic sequences. A relationship between the linear complexity and the k-error linear complexity of pⁿ-periodic sequences over GF(2) is studied, where p is an odd prime, and z is a primitive root modular p². A necessary and sufficient condition that the k-error linear complexity be strictly less than the linear complexity is shown. A sufficient condition expressed by the error polynomial E^N(x) that LC(S+E)k(S)

Key words: stream cipher, periodic sequence, linear compexity, k-error linear complexity