On the Distribution of Quadratic Residues and Nonresidues Modulo a Prime Number

Let P be a prime number and a₁, … ,aₜ be distinct integers modulo P. Let x be chosen at random with uniform distribution in ZP, and let yᵢ = x + aᵢ. We prove that the joint distribution of the quadratic characters of the yᵢ’s deviates from the distribution of independent fair coins by no more than t(3 + √ P )/P. That is, the probability of (y₁, … ,yₜ) matching any particular quadratic character sequence of length t is in the range ( 1/2 )ᵗ ± t(3 + √ P )/P . We establish the implications of this bound on the number of occurrences of arbitrary patterns of quadratic residues and nonresidues modulo P. We then explore the randomness complexity of finding these patterns in polynomial time. We give (exponentially low) upper bounds for the probability of failure achievable in polynomial time using, as a source of randomness, no more than one random number modulo P.