How many bits have to be changed to decrease the linear complexity? (Q702172): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1023/b:desi.0000035466.28660.e9 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2091317732 / rank | |||
Normal rank |
Latest revision as of 09:50, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | How many bits have to be changed to decrease the linear complexity? |
scientific article |
Statements
How many bits have to be changed to decrease the linear complexity? (English)
0 references
17 January 2005
0 references
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)].
0 references
stream ciphers
0 references
linear complexity
0 references
k-error linear complexity
0 references
algorithm
0 references
periodic sequences
0 references