Solving bivariate quadratic congruences in random polynomial time
Authors: Leonard M. Adleman, Dennis R. Estes and Kevin S. McCurley
Journal: Math. Comp. 48 (1987), 17-28
MSC: Primary 11Y16; Secondary 11A07, 11Y05
MathSciNet review: 866095
Full-text PDF Free Access
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 L-functions. We now prove the result without assuming any unproved hypothesis.
-  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
-  John Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011–1013. MR 314745, https://doi.org/10.1090/S0025-5718-1972-0314745-6
-  Harold Davenport, Multiplicative number theory, 2nd ed., Graduate Texts in Mathematics, vol. 74, Springer-Verlag, New York-Berlin, 1980. Revised by Hugh L. Montgomery. MR 606931
-  Donald E. Knuth, The art of computer programming. Vol. 2, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 633878
-  Kevin S. McCurley, Explicit zero-free regions for Dirichlet 𝐿-functions, J. Number Theory 19 (1984), no. 1, 7–32. MR 751161, https://doi.org/10.1016/0022-314X(84)90089-1
-  H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134. MR 374060, https://doi.org/10.1112/S0025579300004708
-  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
-  J. M. Pollard & C. P. Schnorr, "Solution of , with application to digital signatures," preprint, 1985.
-  Michael O. Rabin, Digitalized signatures, Foundations of secure computation (Workshop, Georgia Inst. Tech., Atlanta, Ga., 1977) Academic Press, New York-London, 1978, pp. 155–168. MR 513187
-  J. Barkley Rosser, Real roots of Dirichlet 𝐿-series, Bull. Amer. Math. Soc. 55 (1949), 906–913. MR 32694, https://doi.org/10.1090/S0002-9904-1949-09306-0
-  J. O. Shallit, An Exposition of Pollard's Algorithm for Quadratic Congruences, Technical Report 84-006, Dept. of Computer Science, University of Chicago, 1984.
-  Daniel Shanks, Five number-theoretic algorithms, Proceedings of the Second Manitoba Conference on Numerical Mathematics (Univ. Manitoba, Winnipeg, Man., 1972) Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. Congressus Numerantium, No. VII. MR 0371855
-  R. Solovay and V. Strassen, A fast Monte-Carlo test for primality, SIAM J. Comput. 6 (1977), no. 1, 84–85. MR 429721, https://doi.org/10.1137/0206006
- 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)
- J. Brillhart, "Note on representing a prime as a sum of two squares," Math. Comp., v. 29, 1972, pp. 1011-1013. MR 0314745 (47:3297)
- H. Davenport, Multiplicative Number Theory, 2nd ed., revised by Hugh L. Montgomery, Springer-Verlag, Berlin and New York, 1980. MR 606931 (82m:10001)
- D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms, 2nd ed., Addison-Wesley, Reading, Mass., 1981. MR 633878 (83i:68003)
- K. McCurley, "Explicit zero-free regions for Dirichlet L-functions," J. Number Theory, v. 19, 1984, pp. 7-32. MR 751161 (85k:11041)
- H. L. Montgomery & R. Vaughn, "The large sieve," Mathematika, v. 20, 1973, pp. 119-134. MR 0374060 (51:10260)
- 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. 89-139. MR 700260 (84i:10005)
- J. M. Pollard & C. P. Schnorr, "Solution of , with application to digital signatures," preprint, 1985.
- M. Rabin, Digitalized Signatures and Public-Key Functions as Intractible as Factorization, MIT Laboratory for Computer Science Report TR-212, 1979. MR 513187 (80b:94017)
- J. B. Rosser, "Real roots of Dirichlet L-series," Bull. Amer. Math. Soc., v. 55, 1949, pp. 906-913. MR 0032694 (11:332c)
- J. O. Shallit, An Exposition of Pollard's Algorithm for Quadratic Congruences, Technical Report 84-006, Dept. of Computer Science, University of Chicago, 1984.
- D. Shanks, Five Number-Theoretic Algorithms, Proc. Second Manitoba Conference on Numerical Mathematics, 1972, pp. 51-70. MR 0371855 (51:8072)
- R. Solovay & V. Strassen, "A fast Monte-Carlo test for primality," SIAM J. Comput., v. 6, 1977, pp. 84-85. MR 0429721 (55:2732)