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

Author:
René Peralta

Journal:
Math. Comp. **58** (1992), 433-440

MSC:
Primary 11Y16; Secondary 11A15

DOI:
https://doi.org/10.1090/S0025-5718-1992-1106978-9

MathSciNet review:
1106978

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Let *P* be a prime number and be distinct integers modulo *P*. Let *x* be chosen at random with uniform distribution in , and let . We prove that the joint distribution of the quadratic characters of the 's deviates from the distribution of independent fair coins by no more than . That is, the probability of matching any particular quadratic character sequence of length *t* is in the range . 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*.

**[1]**N. S. Aladov,*On the distribution of quadratic residues and nonresidues of a prime number p in the sequence*, Mat. Sb.**18**(1896), 61-75. (Russian)**[2]**Eric Bach,*Analytic methods in the analysis and design of number-theoretic algorithms*, MIT Press, Cambridge, 1985. MR**807772 (87i:11185)****[3]**-,*Realistic analysis of some randomized algorithms*, 19th ACM Sympos. on Theory of Computing, 1987.**[4]**A. Brauer,*Combinatorial methods in the distribution of kth power residues*, Combinatorial Mathematics and Its Applications (R. C. Bose and T. A. Dowling, eds.), Univ. of North Carolina Press, Chapel Hill, 1969, 14-37. MR**0248076 (40:1330)****[5]**D. A. Burgess,*The distribution of quadratic residues and non-residues*, Mathematika**4**(1957), 106-112. MR**0093504 (20:28)****[6]**H. Davenport,*On the distribution of quadratic residues*, J. London Math. Soc.**6**(1931), 49-54.**[7]**-,*On the distribution of quadratic residues*, J. London Math. Soc.**8**(1933), 46-52.**[8]**Carl Friedrich Gauss,*Disquisitiones arithmeticae*, English edition, Springer-Verlag, 1986. MR**837656 (87f:01105)****[9]**R. H. Hudson,*On the first occurrence of certain patterns of quadratic residues and nonresidues*, Israel J. Math.**44**(1983), 23-32. MR**693652 (85g:11087)****[10]**R. Peralta,*On the randomness complexity of algorithms*, Technical Report TR90-1, Electrical Engineering and Computer Science Dept., University of Wisconsin-Milwaukee, 1990.**[11]**W. Schmidt,*Equations over finite fields*, Springer-Verlag, 1976. MR**0429733 (55:2744)**

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y16,
11A15

Retrieve articles in all journals with MSC: 11Y16, 11A15

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1992-1106978-9

Article copyright:
© Copyright 1992
American Mathematical Society