On the \(k\)-error linear complexity of sequences with period \(2p^{n}\) over \(GF(q)\) (Q2430407)

The paper proposes an efficient algorithm for computing the \(k\)-error linear complexity (\(k\)-LC) of a pseudorandom sequence defined over a finite prime field \(F_q\) with period \(N=2p^n\), where \(p,q\)\, are odd primes and \(q\) is a primitive root modulo \(p^2\). The \(k\)-LC of a periodic sequence was defined by \textit{M. Stamp} and \textit{C. F. Martin} [IEEE Trans. Inform. Theory 39, 1389--1401 (1993; Zbl 0801.94009)] as the smallest linear complexity (LC) of the sequences obtained changing \(k\)\, or fewer terms of the original sequence within one period (therefore \(0\)-LC=LC). Stamp and Martin also provide an algorithm to compute the \(k\)-LC of binary sequences. The present algorithm is based instead on an algorithm due to \textit{S. Wei, G. Xiao} and \textit{Z. Chen} [IEEE Trans. Inform. Theory 48, No. 10, 2754--2758 (2002; Zbl 1062.94034)], which computes the LC of sequences over \(F_q\)\, with period \(2p^n\). The function \(cost(i)\) in the Stamp-Martin algorithm, which measures the cost of changing the element in position \(i\) is substituted here by the new function \(union\,\,cost(i, i+p^n)\), measuring the cost of changing elements in the positions \(i,i+p^n\) simultaneously. Section 2 of the paper shows a new version of the Wei-Xiao-Chen algorithm and Section 3 presents the proposed algorithm and studies its validity. Section 4 gives details of a numerical example (it finds the \(5\)-LC of a sequence over \(F_3\) with period \(2\times 5^2\)) and finally Section 5 gives bounds for the minimum \(k\) such that the \(k\)-LC is strictly less than the LC.