Construction of Sequences With High Nonlinear Complexity From Function Fields

Yuan Luo, Chaoping Xing, Lin YouIEEE Trans. Information Theory 2017 · OpenReview

Abstract

Complexity of sequences plays an important role in pseudorandom sequences and cryptography. In this paper, we present a construction of sequences with high nonlinear complexity from function fields. The main idea is to make use of function fields with many rational places as well as an automorphism of large order. We illustrate our construction through rational function fields and cyclotomic function fields in which there exist some automorphisms of large order. It turns out that we are able to: 1) slightly increase the length of the inversive sequence without losing nonlinear complexity and 2) obtain sequences with much larger nonlinear complexity than random sequences.
BibTeX
@article{luo2017construction,
  author = {Yuan Luo and Chaoping Xing and Lin You},
  title = {{Construction of Sequences With High Nonlinear Complexity From Function Fields}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=UshV-Uf0Jz7},
}

Loading related content...

Figure