Given a polynomial of the form $f(x) = x^2 + ax + b$, where $a$ and $b$ are integer coefficients, is there an efficient algorithm for finding integer values $x$ for which $f(x)$ is a perfect square? That is, for finding all integers $x$ where $f(x) = y^2$ for some integer $y$?
EDITED TO ADD: My apologies for not being clearer before. If it wasn't already obvious, what I'm wondering is whether there is an efficient algorithm, i.e., something better than just trying all possibilities.
For example, an algorithm that finds the smallest such $x > 0$ and which runs in constant time (or at least something better than $O(x)$) would qualify.
Best Answer
$y^2=x^2+ax+b$, $(2y)^2=4x^2+4ax+4b=(2x+a)^2+4b-a^2$, $4b-a^2=(2y)^2-(2x+a)^2$, so we want to express $4b-a^2$ as a difference of two squares.
Such expressions arise from, and only from, factorizations of $4b-a^2$ of the form $4b-a^2=mn$ with $m,n$ both even or both odd; we get $$ 4b-a^2=\left({m+n\over2}\right)^2-\left({m-n\over2}\right)^2 $$ and then $y=(m+n)/4$, $x=(m-n-2a)/4$.
So the algorithm is, compute $4b-a^2$; find all factorizations $4b-a^2=mn$ with $(m+n)/4$ and $(m-n-2a)/4$ both integers; that gives you all the values of $x$ and $y$ that work.
All of these computations take negligible time, except (for very large values of $a$ and/or $b$) the factorization of $4b-a^2$. That can't be helped; if you had a superfast way to find $x$ and $y$, you'd also have a superfast way of factoring large numbers.