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

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866095-8

MathSciNet review:
866095

Full-text PDF

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 *L*-functions. 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****[2]**John Brillhart,*Note on representing a prime as a sum of two squares*, Math. Comp.**26**(1972), 1011–1013. MR**0314745**, https://doi.org/10.1090/S0025-5718-1972-0314745-6**[3]**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****[4]**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****[5]**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**[6]**H. L. Montgomery and R. C. Vaughan,*The large sieve*, Mathematika**20**(1973), 119–134. MR**0374060**, https://doi.org/10.1112/S0025579300004708**[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****[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-London, 1978, pp. 155–168. MR**513187****[10]**J. Barkley Rosser,*Real roots of Dirichlet 𝐿-series*, Bull. Amer. Math. Soc.**55**(1949), 906–913. MR**0032694**, https://doi.org/10.1090/S0002-9904-1949-09306-0**[11]**J. O. Shallit,*An Exposition of Pollard's Algorithm for Quadratic Congruences*, Technical Report 84-006, Dept. of Computer Science, University of Chicago, 1984.**[12]**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****[13]**R. Solovay and V. Strassen,*A fast Monte-Carlo test for primality*, SIAM J. Comput.**6**(1977), no. 1, 84–85. MR**0429721**, https://doi.org/10.1137/0206006

Retrieve articles in *Mathematics of Computation*
with MSC:
11Y16,
11A07,
11Y05

Retrieve articles in all journals with MSC: 11Y16, 11A07, 11Y05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1987-0866095-8

Article copyright:
© Copyright 1987
American Mathematical Society