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.)
Best Answer
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.