On pseudorandomness in families of sequences derived from the Legendre symbol (Q2460689)

The authors construct a family of finite \(\pm1\)-sequences based on the Legendre symbol and prove their uniformity with respect to the distribution of \(t\)-tuples \((\varepsilon_1,\varepsilon_2,\dots,\varepsilon_t)\) of terms \(\varepsilon_i\in\{1,-1\},\) where the terms are in not necessarily consecutive positions \(i_1<i_2<\cdots<i_t.\) The authors' result holds for sufficiently large primes. They also show that every sequence has small measures of normality, well distribution in arithmetic progressions and multiple correlations. The cryptographic security of the pseudorandom number generators based on the proposed sequences is discussed in the last section of the paper.