Efficient method to write number as a sum of four squares?

Wikipedia states that there randomized polynomial-time algorithms for writing $n$ as a sum of four squares

$n=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}$

in expected running time $\mathrm {O} (\log^{2} n).$

My question is can someone give the efficient algorithm( $\mathrm {O} (\log^{2} n)$ ) to represent $n$ as sum of four squares.

• Not only does Wikipedia state this, but it gives a precise reference for where you can read about it. Jan 9 '17 at 10:50
• ...although my reading of the paper is that the $O(log^2n)$ method they give assumes ERH, and the other method (which doesn't) runs in time $O(log^2n.loglog(n))$ (so it seems to me that the statement in Wikipedia is slightly inaccurate, unless one argues that the truth of ERH is "expected" :-) ) Jan 9 '17 at 10:59
• If you have access to a library, you can see whether they can get it for you by interlibrary loan. Jan 10 '17 at 0:45
• Negative attention to this question and its answers may be explained by the fact that potentially this is related to the current CodeChef challenge. Your browser settings permitting you can follow the links here and judge yourself. Jan 10 '17 at 22:10
• Nothing, nequit. I came here because some helpful users at another related Math.SE question (trackable to that on-going competition) referred the asker here. Not accusing you of anything. It is just that the timing was a bit unfortunate. I apologize for implying anything else. Jan 11 '17 at 7:45

One of their methods for $n=4k+2$ is as follows:

Randomly select an even number $a$ and an odd number $b$ such that $a^2+b^2 < n$. Then, we hope $p=n-a^2-b^2$ is a prime (you can show there's about a $1/(A \log n \log \log n)$ chance of $p$ being prime ); $p$ is of the form $4r+1$, so if $p$ is prime there's a solution to $c^2+d^2=p$.

To find that, we try to solve $m^2+1 \equiv 0 \pmod{p}$; I'm actually going to describe a slightly different method. Select $x$ at random from $1$ to $p-1$; then, $x^{2r}=\pm 1$ depending on whether $x$ is a quadratic residue so calculate $x^r$ by repeated squaring, and with a $1/2$ chance if $p$ is prime (a smaller one if $p$ is composite) you'll find a valid $m$.

Given such an $m$, $m+i$ is a Gaussian integer with norm divisible by $p$ but smaller than $p^2$; use the Euclidean algorithm on the Gaussian integers with $p$ and get $c+di$ with norm $p$, and $a^2+b^2+c^2+d^2=n$.

For an odd number $n$, solve for $a^2+b^2+c^2+d^2=2n$; note that by mod $4$ considerations exactly two of $a,b,c,d$ must be odd, and without loss of generality assume $a,b$ are odd and $c,d$ are even. Then,$(\frac{1}{2}(a+b))^2+(\frac{1}{2}(a-b))^2+(\frac{1}{2}(c+d))^2+(\frac{1}{2}(c-d))^2=n.$

For $n$ a multiple of $4$, solve for $n/4$ recursively, and multiply all values by $4$.

This seems to be addressed in this paper by Bumby.

• Is he related to Grothendieck's ex-wife? May 26 '17 at 17:20
• That seems to rely on factorization, which I would not call efficient. May 26 '17 at 22:47
• @SylvainJULIEN By marriage, yes. May 26 '17 at 23:29
• Why the downvote? May 26 '17 at 23:29

this one is an online calculator based on an algorithm from math overflow.

the math overflow algorithm can be found here.

and then there is also this algorithm from cs stackexchange

https://cs.stackexchange.com/questions/2988/how-fast-can-we-find-all-four-square-combinations-that-sum-to-n

and if you want to do a bit of work, then there is this algorithm that can find the sum of 2 squares for a given integer. So you would have to divide your number in two ( not necessarily equal part ) and then add up the results to get a 4 square representation.