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

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?

-
What about dividing x^2 by const1 and see if the remainder is equal to const2? (You need to reduce const2 in some way before to guarantee const2 is between 0 and const1 - 1. I think const2 := const2 mod const1 should work.) –  Tunococ Aug 14 '12 at 21:56
Having const$1$ prime helps in several ways. First there is a relatively cheap computation (keyword: Legendre symbol) for finding out whether there is a solution. Then there are many good algorithms for finding an actual solution. Much better than quasi brute force search, for large numbers. –  André Nicolas Aug 14 '12 at 21:57
The trick is to first figure out if there is a solution(refer to Andre). For example 3n+2 is never a square number (why?). Once, you know this, you can figure out the maximum number of n's to test (how?). The rest is easy. –  picakhu Aug 14 '12 at 22:21
Actually, my problem is not knowing whether there is solution. I know there is one. And I want to find it as fast as possible. Knowing "maximum number of n's to test" does not help, because I still need to test them and testing them all is slow. There must be some better way. –  Vojtěch Aug 18 '12 at 22:29
Andre: "Then there are many good algorithms" - for instance which one? :-) –  Vojtěch Aug 19 '12 at 18:35

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.

-

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

-
Is this wrong? Why is it downvoted? –  Tunococ Aug 15 '12 at 18:48
I tried to implement your solution, but it is way slower than the algorithm, which I described. But still it gave me different point of view and made me think (I was not the one, who downvoted your solution), thanks! –  Vojtěch Aug 18 '12 at 22:27
@Vojech, if you know there is a solution, this method is supposed to be a lot quicker than yours. Perhaps you should state what the numbers are, my best guess is that your algorithm is wrong or there is a mistake in your code. Also, what language are you using? –  picakhu Aug 20 '12 at 12:19

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.

-
You've just defined properly the problem, but it does not help to find the solution more quickly. Testing all the values is still slow. –  Vojtěch Aug 19 '12 at 18:34