New algorithm for cube (third power) computation

[Niels Möller]

Alberto Zanoni <zanoni at volterra.uniroma2.it> writes:

> a new algorithm for the computation of the cube of a long integer has
> recently been discovered, based on a splitting in two a' la Karatsuba
> and on an ad hoc unbalanced Toom-3 method.

I've read the paper, and my first question is if it can be extended to
fourth power (which I imagine would be a more useful buildingblock for
high powers). But it looks difficult, at least with a split in two
pieces (pieces are n limbs each), since then you get

  (a1^2 x^2+ 2 a0 a1 x+ a0^2)^2

The idea, if I understand it correctly, is then to use a slightly
different polynomial with related coefficients but with a factorization
where fewer products are involved in each factor. But is seems difficult
to do that in a way which avoids computing all three of a1^2, a1 a0 and
a0^2.

However, I think the cubing it can be used as a building block for 8th
powers. Computing a^8 = (a1 x + a0)^8 using three levels of Karatsuba is
3 + 3*3 + 3*3*3 = 39 multiplications (or squarings) of size n.

But we can compute

  a^3              7 nxn (according to your paper)
  a^2              1 nxn (Karatsuba, but a0^2 and a1^2 are already computed!)
  a^5 = a^3 * a^2  4 nxn (Toom32)
  a^8 = a^5 * a^3  7 nxn (Toom53)
                 ----
                  19

Do you agree? If I get this right, it's a factor 2 speedup, if we treat
nxn as the basic building block!

I also wonder if these results are useful for powm. My first guess is
no, since all intermediate results are reduced to size n, and it seems
unlikely that anything can be gained by delaying that reduction. But
it's not clear to me if it, in the cubing algorithm, is possible to
reduce the number (A1, A0, 3B1, 27B0) early (if so, one would get down
from 6 nxn + 2 redc to 5 nxn + 2 redc). And for the 8th power, it
seems very hard to beat repeated squaring, 9 nxn + 3 redc).

Regards,
/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26.
Internet email is subject to wholesale government surveillance.