Title :
Periodic sequences with large k-error linear complexity
Author :
Niederreiter, Harald
Author_Institution :
Inst. for Math. Sci., Nat. Univ. of Singapore, Singapore
Abstract :
We establish the existence of periodic sequences over a finite field which simultaneously achieve the maximum value (for the given period length) of the linear complexity and of the k-error linear complexity for small values of k. This disproves a conjecture of Ding, Xiao, and Shan (1991). The result is of relevance for the theory of stream ciphers.
Keywords :
computational complexity; cryptography; sequences; time-varying systems; cyclotomy; k-error linear complexity; periodic sequences; stream ciphers; Cryptography; Galois fields; Hamming distance; Linear feedback shift registers; Mathematics; Stability; Vectors;
Journal_Title :
Information Theory, IEEE Transactions on
DOI :
10.1109/TIT.2002.807308
