$p + p' = m$
$q  q' = n$
$pp' = qq'$
$(m^{2} + n^{2})\equiv1\pmod 4$ and $n^{2}\equiv0\pmod 4$.
Only $m,n$ are known in the above. Are there any known techniques to guess the values of $p$ and $q$ efficiently?
$p + p' = m$ $q  q' = n$ $pp' = qq'$ $(m^{2} + n^{2})\equiv1\pmod 4$ and $n^{2}\equiv0\pmod 4$. Only $m,n$ are known in the above. Are there any known techniques to guess the values of $p$ and $q$ efficiently? 


Since finding all possible expressions $$ M^2 + N^2 = m^2 + n^2$$ will in fact give you a complete factorization of $m^2 + n^2,$ all you need to know is how to create all $(M,N)$ pairs from a complete prime factorization of $m^2 + n^2 = p_1 p_2 p_3 \ldots p_r q_1^2 q_2^2 \ldots q_s^2,$ where the $p_i \equiv 1 \pmod 4,$ while all $q_j \equiv 3 \pmod 4,$ and the labeled primes are not necessarily distinct. Each prime $p_i$ has essentially one representation as the sum of two squares, at least when positive and ordered. Then you just use $$ (a^2 + b^2) (c^2 + d^2) = (a c + b d)^2 + ( a d  b c)^2$$ while putting in $\pm$ signs on $a,b,c,d$ and switching order. For each expression, you just multiply through by all the $q_j.$ The $q_j$ must, of course, appear as factors of $\gcd(m,n).$ The general method for any $x^2 + k y^2 = t,$ for some $k \geq 1,$ is the HardyMuskatWilliams algorithm, which is implemented in some CAS, sometimes correctly. Given any $p_i,$ the first task in solving $u^2 + v^2 = p_i$ is finding a square root of $1 \pmod {p_i}.$ The rest of this is treated in Editor's Corner: The Euclidean Algorithm Strikes Again by Stan Wagon, M.A.A. Monthly,Vol. 97, No. 2 (Feb., 1990), pp. 125129. The first page can be seen at this link. However, the way I would do it is to take the integer with $w^2 \equiv 1 \pmod {p_i},$ or $w^2 + 1 = p_i t,$ write down the positive quadratic form $\langle p_i, 2 w, t \rangle$ and keep track of each step as I reduce it to $\langle 1,0,1 \rangle,$ reversing steps to find a representation $u^2 + v^2 = p_i.$ Although, as I think of it, I actually do the whole thing by matrix multiplication anyway. Meanwhile, there is a very nice note on using multiple expressions as the sums of two squares to factor a number, in the M. A. A. Monthly, December 2009, pages 928931, A Note on Euler's Factoring Problem by John Brillhart. 


Thanks to Noam Elkies for telling me to post my oneliner to solve this in gp (this dates from around 1993): fermat(p) = qflll([lift(sqrt(Mod(1,p))),p;1,0])[1,] What this does is to use the well known construction (I think that it's in Hardy and Wright), that says that if $0 < a < (p1)/2$ satisfies $a^2 = 1 \bmod{p}$ if you run the continued fraction algorithm for $a/p$ "halfway" to get the convergent $r/s$ then $r^2 + s^2 = p$. What the above oneliner does is to set up the lattice $$\pmatrix {a&p \cr 1 & 0 \cr}$$ The shortest vector in this lattice has $L^2$ norm of $p$. 

