Finding other representations for a sum of two squares

Question

For a sum of two squares: $a^2 + b^2 = c$ where $0 < b < a$, if I know of a valid $a^2$ and $b^2$, is there a fast algorithm for finding all other two square combinations that have the same sum? One that is faster than having to sum every possible $a^2$ and $b^2$ less than $c$.

Answer 1

Let me first say a bit about how the problem goes if you don't have a representation to start from.

Writing $c$ as a sum of two squares $a^2+b^2$ is equivalent to factoring $c$ as $(a+bi)(a-bi)$ over the Gaussian integers. The way to list out all of these would be to solve the problem for each prime factor of $c$ of the form $4k+1$, and combine those in all possible ways.

For example, let $c = 65$, which factors as $5\cdot 13$. We have $5 = 2^2+1^2$, or $5 = (2+i)(2-i)$, and $13 = 2^2 + 3^2$, or $13 = (2+3i)(2-3i)$. We can write $65$ as a sum of two squares by picking one of the complex conjugates from each factor:

• Taking $(2+i)(2+3i) = 1+8i$ tells us $65 = 1^2 + 8^2$.
• Taking $(2+i)(2-3i) = 7-4i$ tells us $65 = 7^2 + 4^2$.
• The other two possibilities give us $1-8i$ and $7+4i$, which are redundant with the above.

For a more complicated example, let $c = 1170$, which factors as $2 \cdot 3^2 \cdot 5 \cdot 13$. Since $3$ is a prime of the form $4k+3$, it cannot be written as a sum of two squares, so all we can do with it is treat $3^2$ as $3^2+0^2 = (3+0i)(3-0i)$. Also, $2$ is special (it ramifies in $\mathbb Z[i]$): we can write $2 = 1^2+1^2=(1+i)(1-i)$, but this will not help us get more solutions. So we still only consider the two possibilities from $5$ and $13$:

• Taking $(1+i)(3)(2+i)(2+3i) = -21 + 27i$ tells us $1170 = 21^2 + 27^2$.
• Taking $(1+i)(3)(2+i)(2-3i) = 33 + 9i$ tells us $1170 = 33^2 + 9^2$.
• The other possibilities give us back the same representations as above.

---

Doing the above steps is hard for large $c$, because factoring is hard. In fact, solving the problem is more or less as hard as factoring: knowing all the ways to write $c$ as a sum of two squares tells us what all its prime factors of the form $4k+1$ are. To see this, consider $1170$ again. If we know that $$1170 = 21^2 + 27^2 = 33^2 + 9^2,$$ we can:

• compute $\gcd(21+27i, 33+9i) = 3+9i$ to conclude that $(3+9i)(3-9i)=90$ divides $1170$, getting $1170/90=13$ as a factor;
• compute $\gcd(21+27i,33-9i) = 15+3i$ to conclude that $(15+3i)(15-3i)=234$ divides $1170$, getting $1170/234=5$ as a factor.

Having one representation $c = a^2+b^2$ doesn't change the fact that factoring is hard, so we still have to do that work.

However, having one representation helps us tremendously with the "easy" step afterwards (which can still be quite hard when the primes are large): writing each prime factor of the form $4k+1$ as a sum of two squares. We can do this by taking the GCD again.

For example, if we know how that $1170 = 2 \cdot 3^2 \cdot 5 \cdot 13$, and also that $1170 = 21^2 + 27^2$, we can:

• compute $\gcd(5, 21+27i) = 1+2i$, concluding that $5 = 1^2 + 2^2 = (1+2i)(1-2i)$;
• compute $\gcd(13, 21+2i) = 3+2i$, concluding that $13 = 3^2 + 2^2 = (3+2i)(3-2i)$.

Then we can combine these factors in other ways, as before, to get the other representations $a^2 + b^2 = c$. (In this case, there's just one more: $(1+i)(3)(1+2i)(3-2i) = 9+33i$, for $1170 = 9^2 +33^2$.)

One caveat: if a prime of the form $4k+1$ appears to a higher power, then some representations $a^2+b^2$ might not help with that prime. For example, if we instead take $5850 = 2 \cdot 3^2 \cdot 5^2 \cdot 13$, then there are three representations: $$5850 = 51^2+57^2 = 33^2+69^2 = 15^2 + 75^2.$$ The first two will help us out with all the primes, but the last will just give us $\gcd(5, 15+75i) = 5$, so it will not tell us how to write $5$ as a sum of two squares. (The first two ways to write $5850$ are relying on nontrivial representations of $5^2=25$ as $3^2 + 4^2$; the last relies on the trivial solution $25 = 5^2+0^2$.)