How many bits have to be changed to decrease the linear complexity?
The \(k\)-error linear complexity of periodic binary sequences is defined to be the smallest linear complexity that can be obtained by changing \(k\) or fewer bits of the sequence per period. For the period length \(p^n\), where \(p\) is an odd prime and 2 is a primitive root modulo \(p^2\), the author shows a relationship between the linear complexity and the minimum value \(k\) for which the \(k\)-error linear complexity is strictly less than the linear complexity, and describes an algorithm to determine the \(k\)-error linear complexity which is based on an algorithm of \textit{G. Xiao, S. Wei, K.Y. Lam} and \textit{K. Imamura} [IEEE Trans. Inf. Theory 46, 2203--2206 (2000; Zbl 0997.94013)]. For the period length \(2^n\) analogous results were presented in \textit{M. Stamp} and \textit{C. F. Martin} [IEEE Trans. Inf. Theory 39, 1398--1401 (1993; Zbl 0801.94009)] based on the algorithm of \textit{R. A. Games} and \textit{A. H. Chan} [IEEE Trans. Inf. Theory 29, 144--146 (1983; Zbl 0498.68034)]. Similar results for \(p^n\)-periodic sequences over finite fields of order \(p\) have been recently obtained by the author [Linear complexity and \(k\)-error linear complexity for \(p^n\)-periodic sequences. Coding, cryptography and combinatorics. Basel: Birkhäuser. Progress in Computer Science and Applied Logic 23, 227--235 (2004; Zbl 1088.94014)]. These results are based on the algorithm of \textit{G. Xiao} and \textit{S. Wei} [Prog. cryptology -- INDOCRYPT 2002. Lect. Notes Comput. Sci. 2551, 12--21 (2002; Zbl 1033.94508)].
- scientific article; zbMATH DE number 5651473
- Counting Functions for the k-Error Linear Complexity of 2 n -Periodic Binary Sequences
- A relationship between linear complexity and k-error linear complexity
- 2 n -Periodic Binary Sequences with Fixed k-Error Linear Complexity for k = 2 or 3
- On the Stability of<tex>$2^n$</tex>-Periodic Binary Sequences
- Joint linear complexity of multisequences consisting of linear recurring sequences
- Lower bounds on error complexity measures for periodic LFSR and FCSR sequences
- On the linear complexity of binary threshold sequences derived from Fermat quotients
- Complete characterization of the first descent point distribution for the \(k\)-error linear complexity of \(2^n\)-periodic binary sequences
- Structure analysis on the \(k\)-error linear complexity for \(2^n\)-periodic binary sequences
- On the \(k\)-error linear complexity of sequences with period \(2p^{n}\) over \(GF(q)\)
- On the error linear complexity spectrum of \(p^n\)-periodic binary sequences
- On the \(k\)-error linear complexity for \(p^n\)-periodic binary sequences via hypercube theory
- Additive character sums of polynomial quotients
- How Much Can Complexity of Linear Cryptanalysis Be Reduced?
- Determining the k-error joint linear complexity spectrum for a binary multisequence with period p^n
- Thek-error linear complexity and the linear complexity forpq n-periodic binary sequences
- A relationship between linear complexity and k-error linear complexity
- Linear complexity of transformed sequences
- On the k-error linear complexity of binary sequences derived from polynomial quotients
- On the k-error linear complexity of -sequences
- An algorithm for computing the error sequence of \(p^{n}\)-periodic binary sequences
This page was built for publication: How many bits have to be changed to decrease the linear complexity?
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q702172)
