2
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ You should make your question more precise. What exactly are you looking for? An algorithm? With what properties? $\endgroup$
    – Greg Martin
    Commented May 26, 2018 at 18:11
  • $\begingroup$ 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? $\endgroup$
    – Vadym Fedyukovych
    Commented May 27, 2018 at 7:32
  • $\begingroup$ 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? $\endgroup$
    – Stefan Kohl ♦
    Commented May 29, 2018 at 14:49
  • $\begingroup$ @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). $\endgroup$
    – Vadym Fedyukovych
    Commented May 30, 2018 at 9:48
  • 2
    $\begingroup$ 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? $\endgroup$
    – Gerry Myerson
    Commented Aug 1, 2018 at 21:29

2 Answers 2

Reset to default
1
$\begingroup$

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:

  1. Given a random number $n$, assign $a:=\lfloor{\sqrt{n}}\rfloor$.
  2. Assign $b:=\lfloor{\sqrt{n-a^2}}\rfloor$.
  3. Call the remainder $m:=n-a^2-b^2$. Check, in this order:
  4. Is $m\equiv 1$ $(\mathop{mod} 4)$? If not, decrease $a$ by $1$ and go to Step 2.
  5. Is $m$ prime? If not, decrease $a$ by $1$ and go to Step 2.
  6. $p:=m$ is now a prime $\equiv 1$ $(\mathop{mod} 4)$.
  7. 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.
  8. $r:=y$ is now a square root of $-1$.
  9. This allows to state $r^2 + 1^2 \equiv 0$ $(\mathop{mod} p)$.
  10. 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)
  11. 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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you! Let me run it and see how it go. $\endgroup$
    – Vadym Fedyukovych
    Commented Apr 13, 2021 at 18:58
  • $\begingroup$ May I ask how it went? I'm also quite interested in finding an algorithm faster than Rabin-Shallit (I'm fine with assumptions, I'm happy if it just works very well in practice for integers in the 32 bits to 64 bits range) $\endgroup$
    – Geoffroy Couteau
    Commented Jul 29, 2021 at 16:33
  • $\begingroup$ Feel free to ask any questions. I'm reading you. $\endgroup$
    – user222134
    Commented Aug 1, 2021 at 11:57
0
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .