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

Harald Niederreiter*, Igor E. Shparlinski

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

13 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)183-189
Number of pages7
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2898
Publication statusPublished - 2003

Fingerprint

Dive into the research topics of 'Periodic sequences with maximal linear complexity and almost maximal k-rrror linear complexity'. Together they form a unique fingerprint.

Cite this