# 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?

• You should make your question more precise. What exactly are you looking for? An algorithm? With what properties? – Greg Martin May 26 '18 at 18:11
• Thank you @Greg Martin. At the core, any non-negative number has a 4-square decomposition, with $log^2$ algorithm to find the witness. Any alternative decomposition to serve as yes/no for "is non-negative?" known, with better than $log^2$ expected running time please? – Vadym Fedyukovych May 27 '18 at 7:32
• But a $\log^2$ algorithm to solve that problem is already quite good, isn't it? -- Is there any reason to hope for something still better? – Stefan Kohl May 29 '18 at 14:49
• @Stefan Kohl yes, $\log^2$ is not bad, still it hits the bottom line at mobile phone battery/accumulator. As stated at 6.2.6 (ProveInequality) of IBM report 3730 (Idemix), "this step accounts for substantial fraction of the computational time of this protocol". As cited by "Ginswich", "complexity..is governed by the cost of finding these squares". I do have my reason with "private location verification" on larger scale (linkedin). – Vadym Fedyukovych May 30 '18 at 9:48
• So, you have an integer, and you want to know whether it's positive or negative? Why not just look at it, and see whether it has a minus sign out front? – Gerry Myerson Aug 1 '18 at 21:29

## 1 Answer

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