What is the fastest way to calculate the $n$th coefficient of a generating function Modulo a prime $p$

Question

I have a generating function defined as $(1+x+x^2+...+x^k)^m$ and I want to find the $n$th coefficient of it modulo a prime $p$. What would be the most efficient approach here (programmatically) aside than just multiplying all the polynomials in $O(k^2 \log(m))$ and finding the coefficient?

Answer 1

I'm not quite sure where $O(k^2 \log m)$ comes from. If you're doing naïve multiplication to build the full polynomial (with coefficients modulo $p$, so that we can say that multiplication of coefficients is $O(1)$) then you have to multiply polynomials of degree up to $\frac{km}{2}$, so I think you would be looking at $O(k^2 m^2 \log m)$. If you're calculating the polynomial modulo $x^n, p$ then it's $O(\min(n, k^2 m^2) \log m)$.

The fastest way to do it is probably to borrow a trick from fast polynomial multiplication: the fast Fourier transform. If you evaluate the function at the $km+1$ roots of unity (exploiting the relationships between powers of roots of unity) you can then interpolate back to the coefficients in $O(km \log(km))$. Alternatively, given your application, it may make more sense to do this in a finite field of characteristic $p$.

There is a wealth of literature on FFT and polynomial multiplication, so I'm not going to go into details here. I'm also not overly concerned if link rot sets in, but to give you a starting point: http://www.cs.ust.hk/mjg_lib/Classes/COMP3711H_Fall16/lectures/FFT_Slides.pdf