# Find all expressions of a prime as a sum of four squares

Does anyone know an efficient algorithm to compute all solutions of $$x^2 + y^2 + z^2 + w^2 = p$$ where $x, y, z, w \in \mathbb{Z}$ and $p \in \mathbb{P}$?

By efficient I mean linear on the number of solutions: $8(p + 1)$.

-
Have you seen algorithms for finding the solutions to Fermat's sum of two squares problem? Maybe there is some inspiration there. – Alex J Best Apr 4 '13 at 13:40
Thank you, with that idea I managed to write an algorithm. – fran.aubry Apr 5 '13 at 11:21
Great! Here's another reference I found arxiv.org/ftp/arxiv/papers/1108/1108.6246.pdf. See the end for a little about algorithms for four squares. – Alex J Best Apr 5 '13 at 13:03

## 1 Answer

Your question is similiar to langrage four square theorem.Michael O. Rabin and Jeffrey Shallit have found randomized polynomial-time algorithms for computing a representation $n = x^2 + y^2 + z^2 + w^2$ for a given integer n, in expected running time $O((logn)^2).$

-
Yes I know but I want to find all the solution. – fran.aubry Apr 5 '13 at 11:20