# Change of plans for general sum of squares

Hi All,

In my last post I described about Euler’s four square identity to for solving general sum of squares equation. My idea was to factorize the number, represent each prime as a sum of four squares, then use Euler’s four square identity to construct the sum of four squares representation for the original Number. But I found it slower than the algorithm I found here. So I adapted the latter. The idea is to reduce the problem of representing a number as a sum of four squares to representing a number as a sum of three squares.

#### Algorithm for representing a positive number n as a sum of three squares

1. If $n == 0$, then return $(0, 0, 0)$
2. Write $n$ as $4^vn_{1}$
3. if $n_{1} \in S$ then return the hard coded representation of $n_{1}$. Here, $S = {2, 3, 10, 34, 58, 85, 130, 214, 226, 370, 526, 706, 730, 1414, 1906, 2986, 9634}$. Representations for these numbers can be found here.
4. If $n_{1}$ is a perfect square then return $(2^v\sqrt{n_{1}}, 0, 0)$
5. if $n_{1} = 3 (mod 8)$, find an odd number $i, i < \sqrt{n_{1}}$ such that $\frac{n_{1} - i^2}{2}$ is a prime. Set $x = i$ and $p = \frac{n_{1} - i^2}{2}$. Find two numbers $y, z$ such that $y^2 + z^2 = p$. (You can use Cornacchia’s  algorithm for this. Return $(2^vx, 2^v(y + z), 2^v|y - z|)$.
6. If $n_{1} = 2 (mod 8)$ or $n_{1} = 6 (mod 8)$ then find an odd number $i, i < \sqrt{n_{1}}$ such that $n_{1} - i^2$ is a prime. Else find an even number $i, i < \sqrt{n_{1}}$ with the above requirement. Set $x = i$ and $p = n_{1} - i^2$. Find $y, z$ such that $y^2 + z^2 = p$ . Return $(2^vx, 2^vy, 2^vz)$.

Note that above algorithm can not be used if $n_{1} = 8k + 7$ for some integer $k \in Z$. That is if $n$ is in the form $4^v(8k + 7)$.

#### Algorithm for representing a positive number n as a sum of four squares

Every non-negative integer $n$ can be represented as a sum of four squares.

1. Write $n$ as $4^vn_{1}$.
2. If $n_{1} = 7 (mod 8)$ then set $d = 2$ and $n_{1} = n_{1} - 4$. If $n_{1} = 6 (mod 8)$ or $n_{1} = 2 (mod 8)$ then set $d = 1$ and $n_{1} = n_{1} - 1$. Otherwise set $d = 0$.
3. Use the algorithm described earlier to represent $n_{1}$ as a sum of three squares. Say, $x^2 + y^2 + z^2 = n$.
4. Return $(2^vd, 2^vx, 2^vy, 2^vz)$.

By using these two algorithms one can represent any non-negative integer as a sum of four squares. In the general sum of squares equation, where a given integer $n$ needs to be represented as a sum of $k$ squares, we can divide $k$  variables into segments of four and divide $n$ into that same number of segments and represent each segment by four squares using the algorithm given above.