16

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?

Pedro Alves
  • 1,667
  • 4
  • 17
  • 37

1 Answers1

2

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!

Kuno
  • 75
  • 1
  • 11
  • Yeah, I tried it but didn't work. I'm still receiving the same error. – Pedro Alves Sep 06 '15 at 23:27
  • Sorry for asking those 'standard questions' first, before diving deeper, but which version of GMP do you use? – Kuno Sep 07 '15 at 08:01
  • 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 (http://www.cs.berkeley.edu/~fateman/papers/polysbyGMP.pdf). – Kuno Sep 07 '15 at 08:12