Efficient sum of squares decomposition Sum of 4 squares decomposition is the well-known result. I'm interested only in negative/non-negative separation with focus on efficiency and large numbers. I'm looking for alternatives or extensions like sum of five or with multipliers.
Any known chance to do better than expected $\log^2(n)$ time (Paul Pollack and Enrique Treviño, "FINDING THE FOUR SQUARES IN LAGRANGE’S THEOREM") with alternatives?
 A: I think I found an efficient way to do so. Proceed like that to find four numbers $a, b, c, d$, having their squares add up to a given integer:

*

*Given a random number $n$, assign $a:=\lfloor{\sqrt{n}}\rfloor$.

*Assign $b:=\lfloor{\sqrt{n-a^2}}\rfloor$.

*Call the remainder $m:=n-a^2-b^2$. Check, in this order:

*Is $m\equiv 1$ $(\mathop{mod} 4)$? If not, decrease $a$ by $1$ and go to Step 2.

*Is $m$ prime? If not, decrease $a$ by $1$ and go to Step 2.

*$p:=m$ is now a prime $\equiv 1$ $(\mathop{mod} 4)$.

*Find a square root of $-1$ $(\mathop{mod} p)$. A common way to do this is to take random numbers $x$ and compute $y=x^{(p-1) \over 4}$. $y^2 \equiv -1$ $(\mathop{mod} p)$ sometimes.

*$r:=y$ is now a square root of $-1$.

*This allows to state $r^2 + 1^2 \equiv 0$ $(\mathop{mod} p)$.

*Now, use the euclidean algorithm to find a factor $s$ of $r$ so that $s\approx{\sqrt{p}}$ and $r\cdot s\approx{\sqrt{p}}$ $(\mathop{mod} p)$ (Thue's Lemma)

*Step 10 always appears to find two numbers whose squares add up to $p$. This means we found the missing two squares.

Finding a suitable prime is not hard. It depends on the density of primes around $n^{1\over 4}$. Roots of $-1$ are readily available modulo these primes. The ("extended") euclidean algorithm isn't hard, either. I do not know why, but it always appears to find exactly the two squares that fit. They even turn up twice, once with a flipped sign.
A: Another representation was found, in five or more variables,
Theorem XII on the last page of
L. E. Dickson, Quaternary Quadratic Forms Representing all Integers
http://www.ams.org/journals/bull/1927-33-01/S0002-9904-1927-04312-9/S0002-9904-1927-04312-9.pdf
The major part of the question remains on faster algoritms finding such a representation. Citing Idemix specifications (RZ 3730), Rabin-Shallit algorithm "accounts for a substantial fraction of the computation time" of an interactive argument (section 6.2.6).
