Solving bivariate quadratic congruences in random polynomial time
HTML articles powered by AMS MathViewer
- by Leonard M. Adleman, Dennis R. Estes and Kevin S. McCurley PDF
- Math. Comp. 48 (1987), 17-28 Request permission
Abstract:
It has been known for some time that solving ${x^2} \equiv a\;(\bmod n)$ 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 ${x^2} - k{y^2} \equiv m\;(\bmod n)$ 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.References
- Enrico Bombieri, Le grand crible dans la théorie analytique des nombres, Astérisque, No. 18, Société Mathématique de France, Paris, 1974 (French). Avec une sommaire en anglais. MR 0371840
- John Brillhart, Note on representing a prime as a sum of two squares, Math. Comp. 26 (1972), 1011–1013. MR 314745, DOI 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 Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass., 1981. Seminumerical algorithms. MR 633878
- Kevin S. McCurley, Explicit zero-free regions for Dirichlet $L$-functions, J. Number Theory 19 (1984), no. 1, 7–32. MR 751161, DOI 10.1016/0022-314X(84)90089-1
- H. L. Montgomery and R. C. Vaughan, The large sieve, Mathematika 20 (1973), 119–134. MR 374060, DOI 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 ${x^2} + k{y^2} \equiv m\;(\bmod n)$, 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 $L$-series, Bull. Amer. Math. Soc. 55 (1949), 906–913. MR 32694, DOI 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) Congressus Numerantium, No. VII, Utilitas Math., Winnipeg, Man., 1973, pp. 51–70. 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, DOI 10.1137/0206006
Additional Information
- © Copyright 1987 American Mathematical Society
- Journal: Math. Comp. 48 (1987), 17-28
- MSC: Primary 11Y16; Secondary 11A07, 11Y05
- DOI: https://doi.org/10.1090/S0025-5718-1987-0866095-8
- MathSciNet review: 866095