[Math] Efficient sum of squares decomposition

algorithmscomputational-number-theorynt.number-theorysums-of-squares

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?

Best Answer

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.

Related Question