NTT multiplication.

[Torbjorn Granlund]

Paul Zimmermann <Paul.Zimmermann at loria.fr> 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
            mpn_mul_fft
  1000000    0.559915000
  
  quiche% ./speed -s1000000 mpn_mul_fft # gmp-4.3.0 with our FFT code
            mpn_mul_fft
  1000000    0.385942000
  
  This code is available from <http://www.loria.fr/~kruppaal/>. 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:
http://magma.maths.usyd.edu.au/users/allan/intmult.html

:-)

-- 
Torbjörn