A new lower bound on the family complexity of Legendre sequences

Cakiroglu Y., Yayla O.

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, vol.33, no.2, pp.173-192, 2022 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 33 Issue: 2
  • Publication Date: 2022
  • Doi Number: 10.1007/s00200-020-00442-y
  • Journal Name: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH
  • Page Numbers: pp.173-192
  • Keywords: Family complexity, Family of Legendre sequences, Lambert W function, Polynomials over finite fields, Pseudo-randomness
  • Middle East Technical University Affiliated: Yes

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.