1
$\begingroup$

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?

  • 0
    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.)2012-08-14
  • 0
    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.2012-08-14
  • 0
    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.2012-08-14
  • 0
    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.2012-08-18
  • 0
    Andre: "Then there are many good algorithms" - for instance which one? :-)2012-08-19

3 Answers 3

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.

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
  • 0
    Is this wrong? Why is it downvoted?2012-08-15
  • 0
    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!2012-08-18
  • 0
    @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?2012-08-20
0

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.

  • 0
    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.2012-08-19