Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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 $ {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.

References [Enhancements On Off] (What's this?)

  • [1] N. S. Aladov, On the distribution of quadratic residues and nonresidues of a prime number p in the sequence $ 1,2, \ldots ,p - 1$, 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 $ \pmod p$, J. London Math. Soc. 6 (1931), 49-54.
  • [7] -, On the distribution of quadratic residues $ \pmod p$, 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

Similar Articles

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

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

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society