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

[Brian Quach]

Shorter and more general:
When 2 is not the only divisor of N, x^N + 1 can be factorised into coprime
polynomials over the small integers. Toom-Cook multiplication can then be
applied to find polynomial products modulo these factors. The resulting
required number of 'pointwise multiplications' is 2N minus the number of
these factors. This frequently allows saving major multiplications in
negacyclic convolutions done using Toom-Cook for multiplication modulo
Fermat numbers, without the multiplication overhead associated with FFT.

On Wed, Jul 3, 2019 at 5:57 PM Brian Quach <bqruiaacnh at gmail.com> wrote:

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