Saving a significant multiplication in odd order Toom-Cook negacyclic convolution

[Brian Quach]

In "A GMP-based implementation of Schönhage-Strassen's large integer
multiplication algorithm", it was suggested that the interpolation phase of
Toom-Cook could be modified to make pointwise multiplications in the
Schönhage-Strassen algorithm more efficient.

I have an idea which can make the multiplication modulo most Fermat numbers
more efficient. This relates to the fact that x^N + 1 has the real root of
unity -1.

Multiplication modulo a Fermat number is often done as a negacyclic
convolution. Negacyclic convolution may be viewed as multiplication of
polynomials modulo x^N + 1 for some N. This negacyclic convolution may be
done by multiplying 2 polynomials of degree N - 1. Using Toom-Cook to do
this will generally involve 2N - 1 multiplications (here I am ignoring the
multiplication by small numbers).

If N is odd, the polynomial can be factorised like this: x^N + 1 = (x +
1)(x^(N - 1) - x^(N - 2) + x^(N - 3) ... + 1). Negacyclic convolution can
be done by multiplying polynomials modulo those factors, and reconstructing
the result using the polynomial CRT. This reduces the problem to
multiplying two polynomials of degree 0, and multiplying two polynomials of
degree N - 2. The former can be done using one multiplication, and the
latter can be done using 2N - 3 multiplications. This results in a total of
2N - 2 multiplications, one less than doing the negacyclic convolution with
Toom-Cook directly.

Even if it saves a multiplication, I am not sure whether this trick will be
helpful. This results in smaller evaluation and interpolation matrices, but
I'm not sure whether this would result in better optimal sequences than
those produced by Bodrato for ordinary Toom-Cook. This requires odd numbers
of pieces for the factors. This may also be complex and awkward to
implement.