A new lower bound on the family complexity of Legendre sequences


Cakiroglu Y., Yayla O.

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING, cilt.33, sa.2, ss.173-192, 2022 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 33 Sayı: 2
  • Basım Tarihi: 2022
  • Doi Numarası: 10.1007/s00200-020-00442-y
  • Dergi Adı: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Applied Science & Technology Source, Compendex, Computer & Applied Sciences, INSPEC, MathSciNet, zbMATH
  • Sayfa Sayıları: ss.173-192
  • Anahtar Kelimeler: Family complexity, Family of Legendre sequences, Lambert W function, Polynomials over finite fields, Pseudo-randomness
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.