# Find first positive perfect square in polynomial time

I have a quadratic. for example $$1x^2+6884x+3297$$ Is it possible to find the first perfect square in the series in polynomial time where both x and y are whole positive integers.

In the above example the first perfect square occurs when $x = 192$ and $y = 1361889$ and $sqrt(y) = 1167$

The above example is a trivial example, in reality I am trying to solve for numbers in excess of 100bits thus factoring is non trivial so I am looking for a faster solution.

One possible solution I have considered is finding where the quadratic intersects another quadratic $h^2+0h+0$ i.e. $h^2$ in the above example when $h = -975$ the two parabola's intersect at $x = 192$ but I am stuck on how to quickly find $h$ and whether its any sort of improvement.

The reason I chose the above as a possible solution is because the first perfect square must occur when $h$ and $x$ are whole integers. For every other intersection either $h$ or $x$ would be fractional. My thinking is this fact may be exploitable to find only solutions where both $h$ and $x$ are whole numbers.

Of course I am probably wrong...

• It will certainly occur before $\beta/2$ where the polynomial is $x^2+\beta x + \gamma$. I know that's not very helpful for a polynomial-time algorithm, but really you want something subpolynomial if you're dealing with hundred-bit numbers. – Patrick Stevens Aug 30 '15 at 8:15
• The most negative number you can go to is $-\beta/2+1$ interestingly, and I have not extensively tested this, that always seems to fall on the only other positive perfect square in the series. – DeveloperChris Aug 31 '15 at 12:19