NTT multiplication.

Torbjorn Granlund tg at
Wed May 13 10:13:42 CEST 2009

Paul Zimmermann <Paul.Zimmermann at> writes:

  with Pierrick Gaudry and Alexander Kruppa, we have published some FFT code
  (still using Schönhage-Strassen) which outperformed GMP 4.2.x by a factor 2
  for some sizes, and still outperforms GMP 4.3.0 by a factor of 1.45 for some
  sizes (for example for 10^6 limbs on a Core 2):
  quiche% ./speed -s1000000 mpn_mul_fft # vanilla gmp-4.3.0
  1000000    0.559915000
  quiche% ./speed -s1000000 mpn_mul_fft # gmp-4.3.0 with our FFT code
  1000000    0.385942000
  This code is available from <>. You'll have to
  do a few changes to compile it with GMP 4.3.0 (we might publish a new version).
This is excellent, but still not anywhere the 2.3 factor I had expected:



More information about the gmp-devel mailing list