Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)$.

share|cite|improve this question
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 See the end for a little about algorithms for four squares. – Alex J Best Apr 5 '13 at 13:03

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).$

share|cite|improve this answer
Yes I know but I want to find all the solution. – fran.aubry Apr 5 '13 at 11:20

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.