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.
 A: 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$.
A: This seems to be addressed in this paper by Bumby.
A: I am going to provide you with 4 links and I hope it will help you.
this one is an online calculator based on an algorithm from math overflow.
http://www.mathcelebrity.com/foursquare.php?num=+178&pl=Show+Lagrange+Four-Square+Notation 
the math overflow algorithm can be found here.
https://stackoverflow.com/questions/11732555/how-to-find-all-possible-values-of-four-variables-when-squared-sum-to-n 
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. 
https://math.stackexchange.com/questions/1972771/is-this-the-general-solution-of-finding-the-two-original-squares-that-add-up-to/1977767?noredirect=1#comment4062390_1977767
