1

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?

J. M. ain't a mathematician
  • 75,051
Vojtěch
  • 123
  • 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

3 Answers3

2

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.

Robert Israel
  • 448,999
1

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.

picakhu
  • 4,906
  • 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
0

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
Tunococ
  • 10,303
  • 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