Enumerating ways to decompose an integer into the sum of two squares

The factorization of $N$ is useful, since $$(a^2+b^2)(c^2+d^2)=(ac+bd)^2+(ad-bc)^2$$ There are good algorithms for expressing a prime as a sum of two squares or, what amounts to the same thing, finding a square root of minus one modulo $p$. See, e.g., http://www.emis.de/journals/AMEN/2005/030308-1.pdf

Edit: Perhaps I should add a word about solving $x^2\equiv-1\pmod p$. If $a$ is a quadratic non-residue (mod $p$) then we can take $x\equiv a^{(p-1)/4}\pmod p$. In practice, you can find a quadratic non-residue pretty quickly by just trying small numbers in turn, or trying (pseudo-)random numbers.

This is the simplest case of the Hardy-Muskat-Williams algorithm. Anyway, here is a link to a 1995 paper by Kenneth S. Williams, http://www.mathstat.carleton.ca/~williams/papers/pdf/202.pdf and to the original HMW paper http://www.ams.org/journals/mcom/1990-55-191/S0025-5718-1990-1023762-3/S0025-5718-1990-1023762-3.pdf .

As I'm not sure you are aware of these details, let me point out that if $$ 4^k \;| \; \; x^2 + y^2$$ then $ 2^k \; | \; x $ and $ 2^k \; | \; y. $ That is, you might as well divide your target by powers of 4 before doing anything difficult. Then after you are finished multiply $x,y$ by the appropriate power of $2.$

This is very similar. If there is a prime $$ q \equiv 3 \pmod 4 $$ and $ q | n,$ then keep dividing the target by powers of $q^2$ until it is no longer divisible by $q^2.$ If the remaining number is divisible by $q$ there is actually no representation at all. But if $$ q^{2k} \;\parallel \; \; x^2 + y^2$$ then $ q^k \; | x $ and $ q^k \; | y. $ The notation $ q^{2k} \;\parallel \; \; x^2 + y^2$ means $ q^{2k} \; | \; \; x^2 + y^2$ but it is not true that $ q^{2k +1} \; | \; \; x^2 + y^2$

Well, that is enough caution. What you really need to know is expressing primes $$ p \equiv 1 \pmod 4 $$ and indeed $ p^m,$ which is not much more difficult. Once you can do that, combine my notes with all possible ways of applying Gerry's multiplication formula (by changing $\pm$ signs and order),

(This elaborates on Gerry's answer.)

This article describes how to solve the $p=x^2+y^2$ equation quickly if $p\equiv 1$ mod 4 and $p$ is a prime.

John Brillhart: Note on representing a prime as a sum of two squares

It also explains how $x^2\equiv-1$ mod $p$ can be solved.