The expansion complexity of ultimately periodic sequences over finite fields

Zhimin Sun; Xiangyong Zeng; Chunlei Li; Yi Zhang; Lin Yi

doi:10.1109/TIT.2021.3112824

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

Department of Foundational Mathematics

Hubei University
University of Bergen

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

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 language	English
Pages (from-to)	7550-7560
Number of pages	11
Journal	IEEE Transactions on Information Theory
Volume	67
Issue number	11
DOIs	https://doi.org/10.1109/TIT.2021.3112824
Publication status	Published - 1 Nov 2021

Keywords

Expansion complexity
nonlinear complexity
ultimately periodic sequence

Access to Document

10.1109/TIT.2021.3112824

Cite this

@article{76e501d2df1a49ba82d3128b179e5309,

title = "The expansion complexity of ultimately periodic sequences over finite fields",

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.",

keywords = "Expansion complexity, nonlinear complexity, ultimately periodic sequence",

author = "Zhimin Sun and Xiangyong Zeng and Chunlei Li and Yi Zhang and Lin Yi",

note = "Publisher Copyright: {\textcopyright} 1963-2012 IEEE.",

year = "2021",

month = nov,

day = "1",

doi = "10.1109/TIT.2021.3112824",

language = "English",

volume = "67",

pages = "7550--7560",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

number = "11",

}

TY - JOUR

T1 - The expansion complexity of ultimately periodic sequences over finite fields

AU - Sun, Zhimin

AU - Zeng, Xiangyong

AU - Li, Chunlei

AU - Zhang, Yi

AU - Yi, Lin

PY - 2021/11/1

Y1 - 2021/11/1

N2 - 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.

AB - 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.

KW - Expansion complexity

KW - nonlinear complexity

KW - ultimately periodic sequence

UR - https://www.scopus.com/pages/publications/85115143575

U2 - 10.1109/TIT.2021.3112824

DO - 10.1109/TIT.2021.3112824

M3 - Article

AN - SCOPUS:85115143575

SN - 0018-9448

VL - 67

SP - 7550

EP - 7560

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 11

ER -

The expansion complexity of ultimately periodic sequences over finite fields

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this