On the k-operation linear complexity of periodic sequences

Ramakanth Kavuluru, Andrew Klapper

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Non-trivial lower bounds on the linear complexity are derived for a sequence obtained by performing k or fewer operations on a single period of a periodic sequence over double-struck F signq. An operation is a substitution, an insertion, or a deletion of a symbol. The bounds derived are similar to those previously established for either k substitutions, k insertions, or k deletions within a single period. The bounds are useful when T/2k < L < T/k, where L is the linear complexity of the original sequence and T is its period.

Original languageEnglish
Title of host publicationProgress in Cryptology - INDOCRYPT 2007 - 8th International Conference on Cryptology in India, Proceedings
Number of pages9
StatePublished - 2007
Event8th Annual International Conference on Cryptolology in India, INDOCRYPT 2007 - Chennai, India
Duration: Dec 9 2007Dec 13 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4859 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th Annual International Conference on Cryptolology in India, INDOCRYPT 2007


  • Linear complexity
  • Periodic sequence
  • k symbol deletion
  • k symbol insertion
  • k-error linear complexity

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'On the k-operation linear complexity of periodic sequences'. Together they form a unique fingerprint.

Cite this