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