$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?



System of Diophantine equations
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 Hardy-Muskat-Williams 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. 125-129. The first page can be seen at this [link](http://www.jstor.org/pss/2323912). 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 928-931, *A Note on Euler's Factoring Problem* by John Brillhart.


[Testing whether an integer is the sum of two squares](https://mathoverflow.net/questions/57981/)


