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

[Torbjörn Granlund]

Brian Quach <bqruiaacnh at gmail.com> writes:

  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.

That sounds great!

What's the state of your implementation?

How much faster did this become than the present GMP multiply code?


-- 
Torbjörn
Please encrypt, key id 0xC8601622