"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?

Refluent

Can you post your code, so that we can reproduce your error? – Higley

the (link to the) slide with the comment is maybe also helpful. – Sandie

This is the slide: wiki.sagemath.org/… – Refluent

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!

Lessor

Yeah, I tried it but didn't work. I'm still receiving the same error. – Refluent

Sorry for asking those 'standard questions' first, before diving deeper, but which version of GMP do you use? – Lessor

I had similar issues past year when performing computations on even larger polynomials... In the end, the use of GMP could also optimize the computation time as shown here (cs.berkeley.edu/~fateman/papers/polysbyGMP.pdf). – Lessor