Solving bivariate quadratic congruences in random polynomial time
Authors:
Leonard M. Adleman, Dennis R. Estes and Kevin S. McCurley
Journal:
Math. Comp. 48 (1987), 1728
MSC:
Primary 11Y16; Secondary 11A07, 11Y05
MathSciNet review:
866095
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: It has been known for some time that solving is as difficult as factoring n, at least in the sense that the two problems are random polynomial time equivalent. By contrast, solving a bivariate quadratic congruence can usually be done in random polynomial time even if the factorization of n is unknown. This was first proved by Pollard and Schnorr in 1985 under the assumption of the Piltz conjecture for Dirichlet Lfunctions. We now prove the result without assuming any unproved hypothesis.
 [1]
Enrico
Bombieri, Le grand crible dans la théorie analytique des
nombres, Société Mathématique de France, Paris,
1974 (French). Avec une sommaire en anglais; Astérisque, No. 18. MR 0371840
(51 #8057)
 [2]
John
Brillhart, Note on representing a prime as a sum
of two squares, Math. Comp. 26 (1972), 1011–1013. MR 0314745
(47 #3297), http://dx.doi.org/10.1090/S00255718197203147456
 [3]
Harold
Davenport, Multiplicative number theory, 2nd ed., Graduate
Texts in Mathematics, vol. 74, SpringerVerlag, New York, 1980.
Revised by Hugh L. Montgomery. MR 606931
(82m:10001)
 [4]
Donald
E. Knuth, The art of computer programming. Vol. 2, 2nd ed.,
AddisonWesley Publishing Co., Reading, Mass., 1981. Seminumerical
algorithms; AddisonWesley Series in Computer Science and Information
Processing. MR
633878 (83i:68003)
 [5]
Kevin
S. McCurley, Explicit zerofree regions for Dirichlet
𝐿functions, J. Number Theory 19 (1984),
no. 1, 7–32. MR 751161
(85k:11041), http://dx.doi.org/10.1016/0022314X(84)900891
 [6]
H.
L. Montgomery and R.
C. Vaughan, The large sieve, Mathematika 20
(1973), 119–134. MR 0374060
(51 #10260)
 [7]
C.
Pomerance, Analysis and comparison of some integer factoring
algorithms, Computational methods in number theory, Part I, Math.
Centre Tracts, vol. 154, Math. Centrum, Amsterdam, 1982,
pp. 89–139. MR 700260
(84i:10005)
 [8]
J. M. Pollard & C. P. Schnorr, "Solution of , with application to digital signatures," preprint, 1985.
 [9]
Michael
O. Rabin, Digitalized signatures, Foundations of secure
computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977), Academic
Press, New York, 1978, pp. 155–168. MR 513187
(80b:94017)
 [10]
J.
Barkley Rosser, Real roots of Dirichlet
𝐿series, Bull. Amer. Math. Soc. 55 (1949), 906–913.
MR
0032694 (11,332c), http://dx.doi.org/10.1090/S000299041949093060
 [11]
J. O. Shallit, An Exposition of Pollard's Algorithm for Quadratic Congruences, Technical Report 84006, Dept. of Computer Science, University of Chicago, 1984.
 [12]
Daniel
Shanks, Five numbertheoretic algorithms, (Univ. Manitoba,
Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973,
pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
(51 #8072)
 [13]
R.
Solovay and V.
Strassen, A fast MonteCarlo test for primality, SIAM J.
Comput. 6 (1977), no. 1, 84–85. MR 0429721
(55 #2732)
 [1]
 E. Bombieri, "Le grand crible dans la théorie analytique des nombres" (Avec une sommaire en anglais), Astérisque, No. 18, Société Mathématique de France, Paris, 1974. MR 0371840 (51:8057)
 [2]
 J. Brillhart, "Note on representing a prime as a sum of two squares," Math. Comp., v. 29, 1972, pp. 10111013. MR 0314745 (47:3297)
 [3]
 H. Davenport, Multiplicative Number Theory, 2nd ed., revised by Hugh L. Montgomery, SpringerVerlag, Berlin and New York, 1980. MR 606931 (82m:10001)
 [4]
 D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed., AddisonWesley, Reading, Mass., 1981. MR 633878 (83i:68003)
 [5]
 K. McCurley, "Explicit zerofree regions for Dirichlet Lfunctions," J. Number Theory, v. 19, 1984, pp. 732. MR 751161 (85k:11041)
 [6]
 H. L. Montgomery & R. Vaughn, "The large sieve," Mathematika, v. 20, 1973, pp. 119134. MR 0374060 (51:10260)
 [7]
 C. Pomerance, "Analysis and comparison of some integer factoring methods," in Computational Methods in Number Theory: Part 1 (H. W. Lenstra, Jr. and R. Tijdeman, eds), Math. Centre Tract 154, Math. Centre, Amsterdam, 1982, pp. 89139. MR 700260 (84i:10005)
 [8]
 J. M. Pollard & C. P. Schnorr, "Solution of , with application to digital signatures," preprint, 1985.
 [9]
 M. Rabin, Digitalized Signatures and PublicKey Functions as Intractible as Factorization, MIT Laboratory for Computer Science Report TR212, 1979. MR 513187 (80b:94017)
 [10]
 J. B. Rosser, "Real roots of Dirichlet Lseries," Bull. Amer. Math. Soc., v. 55, 1949, pp. 906913. MR 0032694 (11:332c)
 [11]
 J. O. Shallit, An Exposition of Pollard's Algorithm for Quadratic Congruences, Technical Report 84006, Dept. of Computer Science, University of Chicago, 1984.
 [12]
 D. Shanks, Five NumberTheoretic Algorithms, Proc. Second Manitoba Conference on Numerical Mathematics, 1972, pp. 5170. MR 0371855 (51:8072)
 [13]
 R. Solovay & V. Strassen, "A fast MonteCarlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 8485. MR 0429721 (55:2732)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
11Y16,
11A07,
11Y05
Retrieve articles in all journals
with MSC:
11Y16,
11A07,
11Y05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198708660958
PII:
S 00255718(1987)08660958
Article copyright:
© Copyright 1987 American Mathematical Society
