Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1987-0866095-8
PII: S 0025-5718(1987)0866095-8
Article copyright: © Copyright 1987 American Mathematical Society