How do I solve the Diophantine equation $ax^2 + bx + c = y^2$?
The approach I have so far is to use the transformation $$ X = 2ax + b, \\ Y = 2y. $$
Applying this, we get,
$$X^2 - dY^2 = n,$$
where $$n = b^2 - 4ac \text{ and } d = a.$$
$X^2 - dY^2 = n$ is a Pell equation which may be solved using the method for solving Pell-type equations.
Questions:
- Is there any other method?
- What is the complexity of the algorithm for finding the solution to the Pell equation?
The "usual" method is continued fractions. This is (asymptotically) slower than $O(p(n))$ for any polynomial $p$.
Using the quadratic sieve and assuming the generalized Riemann hypothesis (described in [L2002]), solutions can be found in time $\exp \left( O(\sqrt{\log n \log \log n}) \right)$, which is still (asymptotically) slower than any polynomial.
There are polynomial time quantum algorithms.[H2007]
[H2007]: Hallgren, Sean (2007), "Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem", Journal of the ACM, 54 (1): 1–19, doi:10.1145/1206035.1206039, S2CID 948064
[L2002]: Lenstra, H. W., Jr. (2002), "Solving the Pell Equation" (PDF), Notices of the American Mathematical Society, 49 (2): 182–192, MR 1875156