Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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 | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

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

Article copyright: © Copyright 1987 American Mathematical Society