On the distribution of quadratic residues and nonresidues modulo a prime number
HTML articles powered by AMS MathViewer
- by René Peralta PDF
- Math. Comp. 58 (1992), 433-440 Request permission
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
-
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)
- Eric Bach, Analytic methods in the analysis and design of number-theoretic algorithms, ACM Distinguished Dissertations, MIT Press, Cambridge, MA, 1985. MR 807772 —, Realistic analysis of some randomized algorithms, 19th ACM Sympos. on Theory of Computing, 1987.
- Alfred Brauer, Combinatorial methods in the distribution of $k$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
- D. A. Burgess, The distribution of quadratic residues and non-residues, Mathematika 4 (1957), 106–112. MR 93504, DOI 10.1112/S0025579300001157 H. Davenport, On the distribution of quadratic residues $\pmod p$, J. London Math. Soc. 6 (1931), 49-54. —, On the distribution of quadratic residues $\pmod p$, J. London Math. Soc. 8 (1933), 46-52.
- 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
- 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, DOI 10.1007/BF02763169 R. Peralta, On the randomness complexity of algorithms, Technical Report TR90-1, Electrical Engineering and Computer Science Dept., University of Wisconsin-Milwaukee, 1990.
- Wolfgang M. Schmidt, Equations over finite fields. An elementary approach, Lecture Notes in Mathematics, Vol. 536, Springer-Verlag, Berlin-New York, 1976. MR 0429733
Additional Information
- © Copyright 1992 American Mathematical Society
- 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