NTT multiplication.

[Paul Zimmermann]

       Niels,

> How to do unbalanced multiplication is an area where GMP has been
> improved recently, but where there is still much room for improvements.
> 
> Theoretically, n x m multiplication (n > m) ought to take time O(n log
> m log log m), (or O(n log m log^* m) with Furer). When
> n is much larger than m, the "one lage digit" method with n/m
> multiplications each of size m x m is reasonable and it gets the right
> asymptotic complexity, but it's not clear that it's really the best
> way to do it.

what does happen currently (say in GMP 4.3.0) when n=2m? Does GMP perform
two FFTs of total size 2m, or one single FFT of total size 3m? Note that
this case happens in several applications (in particular in the half-gcd).

Paul Zimmermann