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