Improved lower bound on the family complexity of Legendre sequences
This work provides an incremental improvement in the theoretical analysis of pseudorandom sequences, relevant for cryptography and coding theory.
The paper improves the lower bound on the family complexity of binary Legendre sequences, a pseudorandomness measure, by enhancing a previous bound from 2015, with the new bound expressed using the Lambert W function and field element properties.
In this paper we study a family of binary Legendre sequences and its family complexity. Family complexity is a pseudorandomness measure introduced by Ahlswede et.~al.~in 2003. A lower bound on the family complexity of a family based on the Legendre symbol of polynomials over a finite field was given by Gyarmati in 2015. In this article we improve the bound given by Gyarmati on family complexity of binary Legendre sequences. The bound depends on the Lambert W function and the number of elements in a finite field belonging to its proper subfield. Moreover, we present a fast method for calculating the bound.