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

Torbjörn Granlund tg at
Thu Jul 4 09:29:58 UTC 2019

Brian Quach <bqruiaacnh at> 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?

Please encrypt, key id 0xC8601622

More information about the gmp-discuss mailing list