Random polynomials in Legendre symbol sequences (Q6169855)

This article presents a novel approach to designing pseudo-random binary sequences with desirable properties, based on the Legendre symbol. The construction is rooted in Hoffstein and Lieman's idea of utilizing polynomials with the Legendre symbol. The paper's novelty comes from the idea of defining quadratic non-residues that are admissible to a polynomial \(f(x)\). A quadratic non-residue \(n\) modulo \(p\) is considered admissible to \(f(x)\in\mathbb{F}_p[x]\) if \(f(x)\) does not have a factor of the form \((x-c)^2+n,\) where \(c\in\mathbb{F}_p\). The authors establish bounds on the correlation measure and provide a probabilistic algorithm that yields an admissible \(n\) for a given polynomial \(f(x)\).