Determine if a positive integer is a sum of two positive squares Given a positive integer $N$, what is the best/most efficient way to determine if $N=x^2+y^2$ for some positive integers $x&lt;y$? Only the decision is needed, not explicitly $x,y$.
As shown in this answer, $n$ is the sum of two non-negative squares if and only if for each prime $p\equiv3\pmod4$, $p$ appears with even exponent in the factorization of $n$.

If the factorization of $n$ contains at least one prime $p\equiv1\pmod4$ with positive exponent, or $p=2$ with odd exponent, then $n$ can be written as the sum of two positive squares.

If the factorization of $n$ contains at least one prime $p\equiv1\pmod4$ with positive exponent, then $n$ can be written as the sum of two distinct positive squares.
Fermat's Theorem says,


  If $p$ is an odd prime and $x,y$ are integers numbers. $p=x^2+y^2$ iff $p≡1 \pmod 4$.