The Expansion Complexity of Ultimately Periodic Sequences over Finite Fields

Zhimin Sun, Xiangyong Zeng, Chunlei Li, Yi Zhang*, Lin Yi

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

Abstract

The expansion complexity is a new figure of merit for cryptographic sequences. In this paper, we present an explicit formula of the (irreducible) expansion complexity of ultimately periodic sequences over finite fields. We also provide improved upper and lower bounds on the $N$ th irreducible expansion complexity when they are not explicitly determined. In addition, for some infinite sequences with given nonlinear complexity, a tighter upper bound of their $N$ th expansion complexity is given.

Original languageEnglish
Pages (from-to)7550-7560
Number of pages11
JournalIEEE Transactions on Information Theory
Volume67
Issue number11
DOIs
Publication statusPublished - 1 Nov 2021

Keywords

  • Expansion complexity
  • nonlinear complexity
  • ultimately periodic sequence

Fingerprint

Dive into the research topics of 'The Expansion Complexity of Ultimately Periodic Sequences over Finite Fields'. Together they form a unique fingerprint.

Cite this