On the distribution of quadratic residues and nonresidues modulo a prime number
Author:
René Peralta
Journal:
Math. Comp. 58 (1992), 433440
MSC:
Primary 11Y16; Secondary 11A15
MathSciNet review:
1106978
Fulltext 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), 6175. (Russian)
 [2]
Eric
Bach, Analytic methods in the analysis and design of
numbertheoretic algorithms, ACM Distinguished Dissertations, MIT
Press, Cambridge, MA, 1985. MR 807772
(87i:11185)
 [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
(40 #1330)
 [5]
D.
A. Burgess, The distribution of quadratic residues and
nonresidues, Mathematika 4 (1957), 106–112. MR 0093504
(20 #28)
 [6]
H. Davenport, On the distribution of quadratic residues , J. London Math. Soc. 6 (1931), 4954.
 [7]
, On the distribution of quadratic residues , J. London Math. Soc. 8 (1933), 4652.
 [8]
Carl
Friedrich Gauss, Disquisitiones arithmeticae, SpringerVerlag,
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
(87f:01105)
 [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
(85g:11087), http://dx.doi.org/10.1007/BF02763169
 [10]
R. Peralta, On the randomness complexity of algorithms, Technical Report TR901, Electrical Engineering and Computer Science Dept., University of WisconsinMilwaukee, 1990.
 [11]
Wolfgang
M. Schmidt, Equations over finite fields. An elementary
approach, Lecture Notes in Mathematics, Vol. 536, SpringerVerlag,
BerlinNew York, 1976. MR 0429733
(55 #2744)
 [1]
 N. S. Aladov, On the distribution of quadratic residues and nonresidues of a prime number p in the sequence , Mat. Sb. 18 (1896), 6175. (Russian)
 [2]
 Eric Bach, Analytic methods in the analysis and design of numbertheoretic 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, 1437. MR 0248076 (40:1330)
 [5]
 D. A. Burgess, The distribution of quadratic residues and nonresidues, Mathematika 4 (1957), 106112. MR 0093504 (20:28)
 [6]
 H. Davenport, On the distribution of quadratic residues , J. London Math. Soc. 6 (1931), 4954.
 [7]
 , On the distribution of quadratic residues , J. London Math. Soc. 8 (1933), 4652.
 [8]
 Carl Friedrich Gauss, Disquisitiones arithmeticae, English edition, SpringerVerlag, 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), 2332. MR 693652 (85g:11087)
 [10]
 R. Peralta, On the randomness complexity of algorithms, Technical Report TR901, Electrical Engineering and Computer Science Dept., University of WisconsinMilwaukee, 1990.
 [11]
 W. Schmidt, Equations over finite fields, SpringerVerlag, 1976. MR 0429733 (55:2744)
Similar Articles
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/S00255718199211069789
PII:
S 00255718(1992)11069789
Article copyright:
© Copyright 1992
American Mathematical Society
