On the distribution of quadratic residues and nonresidues modulo a prime number

Abstract:

Let P be a prime number and ${a_1}, \ldots ,{a_t}$ be distinct integers modulo P. Let x be chosen at random with uniform distribution in ${Z_P}$, and let ${y_i} = x + {a_i}$. We prove that the joint distribution of the quadratic characters of the ${y_i}$’s deviates from the distribution of independent fair coins by no more than $t(3 + \sqrt P )/P$. That is, the probability of $({y_1}, \ldots ,{y_t})$ matching any particular quadratic character sequence of length t is in the range ${\left ( {\frac {1}{2}} \right )^t} \pm t(3 + \sqrt 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.