TY - JOUR

T1 - Periodic sequences with maximal linear complexity and almost maximal k-rrror linear complexity

AU - Niederreiter, Harald

AU - Shparlinski, Igor E.

PY - 2003

Y1 - 2003

N2 - C. Ding, W. Shan and G. Xiao conjectured a certain kind of trade-off between the linear complexity and the k-error linear complexity of periodic sequences over a finite field. This conjecture has recently been disproved by the first author, by showing that for infinitely many period lengths N and some values of k both complexities may take very large values (contradicting the above conjecture). Here we use some recent achievements of analytic number theory to extend the class of period lengths N and the number of admissible errors k for which this conjecture fails for rather large values of k. We also discuss the relevance of this result for stream ciphers.

AB - C. Ding, W. Shan and G. Xiao conjectured a certain kind of trade-off between the linear complexity and the k-error linear complexity of periodic sequences over a finite field. This conjecture has recently been disproved by the first author, by showing that for infinitely many period lengths N and some values of k both complexities may take very large values (contradicting the above conjecture). Here we use some recent achievements of analytic number theory to extend the class of period lengths N and the number of admissible errors k for which this conjecture fails for rather large values of k. We also discuss the relevance of this result for stream ciphers.

UR - http://www.scopus.com/inward/record.url?scp=35248827019&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:35248827019

SN - 0302-9743

VL - 2898

SP - 183

EP - 189

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -