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

$\begingroup$

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

$\endgroup$ 3

1 Answer

$\begingroup$

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

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy