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 factorisation.

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