On the k-operation linear complexity of periodic sequences

Ramakanth Kavuluru, Andrew Klapper

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

Abstract

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
Pages322-330
Number of pages9
DOIs
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

Conference

Conference8th Annual International Conference on Cryptolology in India, INDOCRYPT 2007
Country/TerritoryIndia
CityChennai
Period12/9/0712/13/07

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

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

Cite this