The k-error linear complexity of a periodic sequence over a finite field Fq is defined to be the smallest linear complexity that can be obtained by changing k or fewer bits per period. We explicitly give the expected value of k-error linear complexity of pn-periodic sequences over Fq, where p is an odd prime, q is a prime primitive root modulo p2, and 1≤k≤(p－1)/2.
WU Cheng-Wen
,
YUE Qin
. Expected value of k-error linear complexity of periodic sequences[J]. Journal of University of Chinese Academy of Sciences, 2012
, 29(4)
: 564
-570
.
DOI: 10.7523/j.issn.2095-6134.2012.4.020
[1] Ding C, Xiao G, Shan W. The stability theory of stream ciphers //Lecture Notes in Computer Science. Springer-Verlag, 1991, 561.
[2] Meidl W, Niederreiter H. On the expected value of the linear complexity and the k-error linear complexity of periodic sequences[J]. IEEE Trans Inf Theory, 2002, 48(11): 2817-2825.
[3] Games R A, Chan A H. A fast algorithm for determining the complexity of a binary sequences with period 2n[J]. IEEE Trans Inform Theory, 1983, 29: 144-146.
[4] Stamp M, Martin C F. An algorithm for the k-error linear complexity of binary sequences of period 2n[J]. IEEE Trans Inform Theory, 1993, 39: 1398-1401.
[5] Weidl W. On the stability of 2n-periodic binary sequences[J]. IEEE Trans Inform Theory, 2005, 51(3): 1151-1155.
[6] Xiao G, Wei S, Lam K Y, et al. A fast algorithm for determining the linear complexity of a sequence with pn over GF(q)[J]. IEEE Trans Inf Theory, 2000, 46: 2203-2206.
[7] Chen H. Reducing the computation of linear complexities of periodic sequences over GF(pm)[J]. IEEE Trans Inf Theory, 2006, 52:5537-5539.
[8] Han Y K, Chung J H, Yang K. On the k-error linear compexity of pm-periodic binary sequences[J]. IEEE Trans Inf Theory, 2007, 53(6): 2297-2304.
[9] Rosen K H. Elementary number theory and its applications[M]. Addison-Wesley, Reading, MA, 1988.
