Sum of two squares problem
A well-known result is $gcd(t+i, n)$ over Gaussian numbers where $t$ is a square root of (-1) modulo $n$. The reason is $t^2 = -1 \pmod{n}$ equivalent to $n | (t+i)(t-i)$ over $Z[i]$. Real and img components of this $gcd()$ are the squares.