Algorithm to find when a polynomial with integer coefficients has a perfect square value 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.
 A: $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.
A: Your function is:
$$ f(x) = x^2+ax+b $$
and you seek the form:
$$ y^2 = x^2+ax+b $$
for some integer $y$ to find $x$. We must solve for $x$ hence let us make the quadratic equation equal to zero:
$$ 0 = x^2+ax+b-y^2 $$
The solution to this equation (https://en.wikipedia.org/wiki/Quadratic_formula) is:
$$ x_{1,2} = \frac{-a\pm\sqrt{a^2-4(b-y^2)}}{2}$$ 
For this to have a solution in the set of integer numbers the condition $ a^2-4(b-y^2) \geq 0 $ must be satisfied. As you are seeking for integer values of $x$ then you should only check whether the values of $x_1$ and $x_2$ are integer in your algorithm for the given constants in the solution. 
One more condition that you could test for integer solutions is whether $ -a\pm\sqrt{a^2-4(b-y^2)} $ is divisible by $2$. If it is then you have your integer solutions. 
Here is a flowchart of the algorithm:

A: In general, the equation,
$$x^2+ax+b =y^2$$
has infinitely many rational solutions given by,
$$x = \frac{(a-n)^2-4b}{4n}$$
$$y = \frac{a^2-n^2-4b}{4n}$$
for any rational $n$. But you want integer $(x,y)$. For odd a, then an obvious choice is $n = \pm 1$ and $(x,y)$ become integers.
