Using FFT to efficiently multiply multiple polynomials modulo N
I have a set of polynomials $P_k$ defined as:
$$ P_k = \sum_{n = 0}^{n = N} p_{kn} x^n $$
$N$ is large ($2^{16}$)
I would like to perform multiplication on the polynomials:
$$ Q = \prod_{k=0}^{k=K} P_k $$
$K = 16$
But I only want to keep the coefficients from $0$ to $N$ i.e.
$$ Q = \sum_{n = 0}^{n = N} q_nx^n $$
I know the fastest way to multiply two large polynomials is using the FFT to perform linear convolution by zero padding the two polynomials by N before taking the forward transform, point wise multiplying and then taking the inverse transform. However, for $K$ polynomials I would have to pad $K*N$. Is there an efficient method where I can pad by N, do the forward transform on all the polynomials, and just take one inverse transform at the end?
$\endgroup$ 2 Reset to default
