Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 Answers 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.

share|improve this answer

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
share|improve this answer
    
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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.