Fastest way of finding solution to n*const1+ const2 = x^2

Question

I am trying to solve the following equation:

n*const1 + const2 = x^2

Where n, const1, const2 and x are integers > 0. Const1, const2 are known, n and x are variables.

The naive solution to this problem is to iterate all n's and check if the square root of the result is integer. This solution is however too slow:

for n = 0;; n++:
     if sqrt(n*const1 + const2) is integer:
         end.
     else:
         continue.

Would it help, if the const1 was a prime number?

Answer 1

I don't claim that this is a good algorithm but I think it should be faster than your original algorithm:

offset := floor(const2 / const1)
const2 := const2 mod const1
for x := 0 to some positive integer
    if x^2 mod const1 == const2
        report (x, floor(x^2 / const1) + offset) as a solution
    end if
end for

Answer 2

This is eluding to my comment. (spoiler for obvious reasons, OP should try to process my hints before looking here)

Note that if you know that a solution exists based on Legendre symbol, you can test if $x_n^2$ is equal to $b$ (mod $a$) under the assumption that you are trying to find $n$ such that $an+b=x^2$. Thus, you only need to test at most $a$ numbers.

Answer 3

You are trying to find a square root of const2 mod const1. You might look at http://www.math.leidenuniv.nl/~psh/ANTproc/02buhler.pdf problems 10 and 11.