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

MathSciNet review:
1106978

Full-text PDF Free Access

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*, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR**807772****[3]**-,*Realistic analysis of some randomized algorithms*, 19th ACM Sympos. on Theory of Computing, 1987.**[4]**Alfred Brauer,*Combinatorial methods in the distribution of 𝑘th power residues*, Combinatorial Mathematics and its Applications (Proc. Conf., Univ. North Carolina, Chapel Hill, N.C., 1967) Univ. North Carolina Press, Chapel Hill, N.C., 1969, pp. 14–37. MR**0248076****[5]**D. A. Burgess,*The distribution of quadratic residues and non-residues*, Mathematika**4**(1957), 106–112. MR**0093504****[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*, Springer-Verlag, New York, 1986. Translated and with a preface by Arthur A. Clarke; Revised by William C. Waterhouse, Cornelius Greither and A. W. Grootendorst and with a preface by Waterhouse. MR**837656****[9]**Richard H. Hudson,*On the first occurrence of certain patterns of quadratic residues and nonresidues*, Israel J. Math.**44**(1983), no. 1, 23–32. MR**693652**, 10.1007/BF02763169**[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]**Wolfgang M. Schmidt,*Equations over finite fields. An elementary approach*, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin-New York, 1976. MR**0429733**

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

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

Additional Information

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

Article copyright:
© Copyright 1992
American Mathematical Society