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

1

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