Precompute FFT to speed up multiplications by same polynomial

libntl / ntl

269 stars 53 forks source link

Precompute FFT to speed up multiplications by same polynomial #12

Open hilder-vitor opened 3 years ago

hilder-vitor commented 3 years ago

Hello!

In a situation where we want to compute products f * g_i for several polynomials g_i's and a fixed polynomial f, we could precompute the FFT of f so that when we are given the g_i's, we just need to compute FFT(g_i), multiply and apply the inverse FFT...

Is there a way to precompute the FFT of a polynomial NTL::ZZX like this?

Thank you very much!

victorshoup commented 3 years ago

Something like this is done for polynomials over ZZ_p, but unfortunately not for for polynomials over ZZ. This could be a nice feature, but I don't see it happening soon.