Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a fast (probabilistic or deterministic) algorithm for determining whether an integer $n$ is a sum of two squares?

By "fast" here I mean polynomial time (i.e. time $O((log n)^{O(1)})$). Note that I am interested only in whether the integer can be represented in such a way, not in how it is represented.

Since a fast algorithm is required, it will not do to use factorization.

It would be odd if this turned out to be harder than detecting primality, since prime numbers are rarer.

(This is a question that came up in a talk I just gave.)

share|improve this question
    
I wouldn't expect detecting representable numbers to be substantially easier than computing such a representation. There is a probabilistic polynomial-time algorithm for finding these representations by Rabin and Shallit (dx.doi.org/10.1002/cpa.3160390713), but it only works for primes, which is the case you are not interested in (detecting whether a prime can be represented is trivial). –  Emil Jeřábek Mar 9 '11 at 19:07
1  
@J.C. Ottem: "Polynomial time" in this context generally means "polynomial in the number of bits needed to represent the input", i.e. polynomial in $log(n)$. Harald makes this completely clear in the question. –  David Loeffler Mar 9 '11 at 19:15
9  
"It would be odd if this turned out to be harder than detecting primality, since prime numbers are rarer." This intuition seems completely false to me. I can test whether $n$ is a power of $3$ is $O((\log n)^2)$, and that's a very rare condition! –  David Speyer Mar 9 '11 at 19:16
2  
@Emil: If a prime p is 1 mod 4 then a representation p=a^2+b^2 can be found in deterministic polynomial time. First use Schoof's algorithm (Math. Comp. 44 (1985), 483-494) to find a solution of x^2 = -1 mod p in polynomial time, then use the Euclidean algorithm in Gaussian integers to find a+bi=gcd(p,x+i) in polynomial time. –  GH from MO Mar 9 '11 at 19:24
1  
An idea that does not help : It is equivalent to ask to check if the conic $x^2+y^2 = n$ has a rational solution. But unless I factor $n$, I would not know at which finitely many primes $p$ I have to check locally solubility. –  Chris Wuthrich Mar 9 '11 at 19:39

3 Answers 3

This problem is equivalent to detecting whether there is some prime $p\equiv3\pmod4$ dividing the number which is raised to an odd power. In the worst case, where the number is a large semiprime equivalent to 1 mod 4, this is almost surely as hard as FACTORIZATION. If it was easy, then it would give away the second-lowest bit in both prime factors of such numbers; if we had enough information of this type we could recover the factors via Coppersmith's algorithm.

Practically, check the number mod 4 (once you remove trailing 0s) and see if it's 3, then trial divide by small primes.

share|improve this answer
    
Please explain - how would you use Coppersmith's algorithm? What information would you be assuming, precisely? –  H A Helfgott Mar 12 '11 at 20:12
    
?? You would CRT all the known residues together so that for one of the primes dividing n, p = r mod m. Then use Coppersmith to find numbers in that residue class which have a nontrivial gcd with n, recovering the factor. Isn't that a standard use of the algorithm? Of course you'd need a lot of information, but Coppersmith makes "a lot" a much smaller number than if the only available algorithm was testing numbers of the form r, r+m, r+2m, ... sequentially. (Obviously, if only a very small amount of information is known, general-purpose factorization is faster.) –  Charles Mar 13 '11 at 3:45
    
See also Tao's answer mathoverflow.net/questions/3820/… . –  Charles Mar 13 '11 at 3:50

The question is equivalent to testing whether -1 is a square modulo n. This corresponds to the quadratic residuosity problem which is supposedly computationally hard: http://en.wikipedia.org/wiki/Quadratic_residuosity_problem

share|improve this answer
9  
But is testing whether -1 is a square as hard as testing whether an arbitrary residue (with Jacobi symbol 1) is a square? Testing whether an arbitrary residue is a square is the supposedly hard quadratic residuosity problem. –  Peter Shor Mar 9 '11 at 23:32
1  
To expand on Peter’s comment, the quadratic residuosity problem is supposed to be hard when $n$ is a Blum integer, in which case we know a priori that $-1$ is not a square. –  Emil Jeřábek Mar 10 '11 at 11:02
    
Why "quadratic residuosity problem is supposed to be hard when n is a Blum integer"? It is formulated for a generic composite number. A Blum integer would be a particular case of the problem. –  Max Alekseyev Jul 19 '11 at 15:45
    
Can you explain your equivalence? It is not directly equivalent as, for example, 45 is a sum of two squares but -1 is not a square modulo 45. –  ndkrempel Oct 20 at 21:22
    
@ndkrempel: Strictly speaking, equivalence here is with being the sum of two coprime squares. For non-coprime squares, we can try to cancel all possible square factors of $n$ and then test if it becomes the sum of coprime squares. In particular, for $n=45$, we have that -1 is a square modulo $45/3^2=5$. –  Max Alekseyev Oct 21 at 16:48

There are situations where we know that a number is a sum of two squares although we do not know the factorization, and in fact know very little about the factors. This question, for example, notes that $F_{2k+1}=F_k^2+F_{k+1}^2$ (the $F_k$ are the Fibonacci numbers). On the flip side, though, while Fibonacci numbers are easier to factor than most, they are not trivial (I think Blair Kelly maintains a list of factors).

To be specific, $F_{1049}$ is a sum of two squares, but has not yet been factored.

share|improve this answer
9  
Ditto the various $2^{2^n}+1.$ –  Aaron Meyerowitz Jun 26 '11 at 2:49

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.