1
$\begingroup$

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...

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Patrick Stevens Aug 30 '15 at 8:15
  • $\begingroup$ 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. $\endgroup$ – DeveloperChris Aug 31 '15 at 12:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.