On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences

Niu Zhi-hua; Bai En-jian; Xiao Guo-zhen

Volume 26 Issue 11

Nov. 2004

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2004 > 26(11): 1787-1791

Niu Zhi-hua, Bai En-jian, Xiao Guo-zhen . On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences[J]. Journal of Electronics & Information Technology, 2004, 26(11): 1787-1791.

Citation:

Niu Zhi-hua, Bai En-jian, Xiao Guo-zhen . On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences[J]. Journal of Electronics & Information Technology, 2004, 26(11): 1787-1791.

Citation:

PDF( 898 KB)

On the Expected Value of the Linear Complexity and the k-Error Linear Complexity of Periodic Sequences

Received Date: 2003-05-15
Rev Recd Date: 2003-12-02
Publish Date: 2004-11-19

Abstract

Abstract

Cryptographically strong sequences not only should have a large linear com-plexity, but also no a significant decrease of the linear complexity when a few terms are changed. This requirement leads to the concept of the /c-error linear complexity of periodic sequences. In the following two cases: (1) gcd(N,p) = 1; (2) N= pv, where p denotes the characteristic of the finite field GF(q), the counting function NN,o(c), i.e., the number of N-periodic sequences with given linear complexity c, is showed, the expected value of the linear complexity En,o is determined, and a useful lower bound on the expected value of the k-errov linear complexity EN, is established.

FullText(HTML)

References(1)

References

Ding C, Xiao G, Shan W. The stability theory of stream ciphers. Lecture Notes in Computer Science. Vol.561, Berlin: Springer-Verlag, 1991.[2]Stamp M, Martin C F. An algorithm for the k-error linear complexity of binary sequences of period 2n. IEEE Trans. on Information Theory, 1993, IT-39(4): 1398-1401.[3]Kaida T, Uehara S, Imamura K. A new algorithm for the k-error linear complexity of sequences over GF(pm) with period pn. In Sequences and Their Applications. Ding C, Helleseth T, Niederreiter H. Eds. London, U. K.: Springer, 1999: 284-296.[4]Rueppel R A.Analysis and Design of Stream Ciphers. Berlin: Springer-Verlag, 1986.[5]Meidl W, Niederreiter H. On the expected value of the linear complexity and the k-error linear complexity of periodic sequences. IEEE Trans. on Information Theory, 2002, IT-48(11): 2817-2825.[6]Wei S, Zhang Y, Xiao G. Distribution of linear complexity for periodic sequences. CrypTEC99,Hong Kong, July 1999: 250-253.

Relative Articles

Supplements(0)

Cited By

Proportional views