Testing whether an integer is the sum of two squares 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.)
 A: 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
A: 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.
A: 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.
