"Polynomial too big for FFT" error on NTL

Question

I'm trying to perform a multiplication of polynomials of degree 4096 using ZZ_pEX class from NTL. However, it returns the error "Polynomial too big for FFT", and I couldn't find a way to make it works (or even something that could help on NTL's documentation) but a comment in a slide saying that it can be fix (without saying how!).

Did anyone found a fix for this?

Answer 1

You have to re-compile NTL with GMP, that provides the GNU Multiprecision number package library routines. When it seems to be appropriate, this package uses very beautiful hacks, e.g. FFTs, for bignum arithmetic.

Here, below "Building and using NTL with GMP" are the detailed steps you need to follow in order to compile NTL with GMP: http://www.shoup.net/ntl/doc/tour-gmp.html

Have fun!