# Devising an Algorithm to find out if a natural number n is the sum of 2 squares

The title says it all. On my homework I am tasked with creating an algorithm that determines whether or not a natural number n can be written as the sum of two squares.

The only stipulation I am given is that I have access to (theoretically) a computer which will quickly tell me if a number k is a perfect square.

I really am just stuck on how to go about doing this, so even just a small hint in the right direction would be appreciated!

-
Not helpful for large numbers, but the non-negative integer $n$ is a sum of two squares iff every prime of the form $4k+3$ in the prime factorization of $n$ occurs to an even power. (Am counting $0$ as a perfect square, and allow the two squares to be equal.) – André Nicolas Sep 11 '12 at 3:15
– lhf Sep 11 '12 at 3:28
Whoops, thought I searched far and wide before asking. Sorry about that. – madisonfly Sep 11 '12 at 16:39

From the description, I guess you're supposed to brute-force it:

a=0
while true do
b=n-a^2
if b<0 return false
if b is a perfect square return true
a=a+1
end

-
If $n$ is $2$ or $3 \pmod 4$ you can return false immediately. – Ross Millikan Sep 11 '12 at 3:45
Should that not be "if $n$ is $3 \pmod{4}$ then return false"? Since $10 \equiv 2 \pmod{4}$ and 10 is a sum of 2 squares. – Old John Sep 11 '12 at 10:19
You can also stop as soon as $b < a^2$ instead of $b<0$. – lhf Sep 11 '12 at 12:03
It might not be a great saving, but we could also divide by any square factors first, since they have no effect on representability by a sum of 2 squares. e.g. if $n\equiv 0 \pmod{4}$, then replace $n$ by $n/4$. – Old John Sep 11 '12 at 23:42