A new lower bound on the family complexity of Legendre sequences


Cakiroglu Y., YAYLA O.

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, 2020 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume:
  • Publication Date: 2020
  • Doi Number: 10.1007/s00200-020-00442-y
  • Title of Journal : APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING

Abstract

In this paper we study a family of Legendre sequences and its pseudo-randomness in terms of their family complexity. We present an improved lower bound on the family complexity of a family based on the Legendre symbol of polynomials over a finite field. The new bound depends on the LambertWfunction and the number of elements in a finite field belonging to its proper subfield. Moreover, we present another lower bound which is a simplified version and approximates the new bound. We show that both bounds are better than previously known ones.