Sums of Squares algorithm I want to express a large number as the sum of two squares, given that it is possible and given its prime factors.  Let's say the number is $273097$.  It's prime factors are $11^2, 37$ and $61$.  Here is is easy to see $11^2=11^2+0^2$ and $37=6^2+1^2$. Through trial and error I found that $61=5^2+6^2$, but having read Efficiently finding two squares which sum to a prime, it looks like I just needed to notice that $11^2\equiv-1\pmod{61}$ and I could then apply the Euclidean algorithm to $61$ and $11$ to find the first two remainders below $\sqrt{61}$, which are of course $5$ and $6$.  Then I have $273097=11^2(6\times5-1\times6)^2+11^2(6\times6+1\times5)^2$. Is this the best way going about a question like this?
 A: Prime number $p$ can be expressed as sum of two (non-zero) squares if $p\equiv 1 \pmod{4}$.
We know $37 = 1^2 + 6^2, 61 = 5^2 + 6^2.$
Hence $37$ and $61$ are expressed using Gaussian integers below.
Norm$(1+6i) = (1+6i)(1-6i) = 1^2 + 6^2 = 37$
Norm$(5+6i) = (5+6i)(5-6i) = 5^2 + 6^2 = 61$
Since $273097 = 11^2\cdot37\cdot61$ = Norm$(11(1\pm6i)(5\pm6i))$, then we get
$11(1+6i)(5+6i) = -341+396i  \implies 273097 = 341^2 + 396^2.$
$11(1-6i)(5+6i) = 451-264i   \implies 273097 = 451^2 + 264^2.$
$11(1+6i)(5-6i) = 451+264i   \implies 273097 = 451^2 + 264^2.$
$11(1-6i)(5-6i) = -341-396i  \implies 273097 = 341^2 + 396^2.$
A: Especial case:
Due to Fermat theorem $N=4k+1=m^2+n^2$ and we have:
$4k+1\equiv 1 \bmod 3\Rightarrow k\equiv 0\bmod 3$
Therefore parametric form of N can be:
$N=12 t+1$
So we can first check whether N can be written as the sum of two primes or not. For example $273097=22758\times 12+1$, so it is among the numbers of this type. To find numbers m and m we may use following identity:
$(2k+1)+(2i^2-k+1)^2=(2i^2-k)^2+(2i)^2\space\space\space\space\space\space$ (1)
$LHS= 4i^4+4i^2(1-k)+k^2=N\space\space\space\space\space\space\space\space\space$ (2)
So  i and k must be divisible by some prime factors of N. Also the solution  of problem leads to solving Diophantine equation (2). For example:
$4i^4+4i^2(1-k)+k^2=273097$
gives $(k, i)=(34397, 132), (35299, 132),(78067, 198), (78749, 198)$
and we have:
$273097=(2i^2-k)^2+(2i)^2=(451^2+264^2), (-451^2+264^2), (-341^2+396^2),(341^2+396^2) $
This method may be suitable for large numbers.
