Polynomial Division algorithm using DFT

Question

I am given to polynomials $p$ and $q$ of size $n-1$and $m-1$ where $n\geq m$. I also have the division algorithm below:

1. Let n' be the smallest power of 2 greater than n − 1.
2. Use the FFT to compute y = DFTn'(p), and z = DFTn'(q).
3. Compute the n-dimensional vector {y0/z0, y1/z1, . . . , yn0/zn0}.
4. Compute a = DFT^-1 {y0/z0, y1/z1, . . . , yn0/zn0}),
and return this as the coefficient vector for p(x)/q(x)

I have to find the cases when this will reconstruct $p(x)/q(x)$ succesfully both when $p(x)/q(x)$ can be represented by a polynomial and when it is an infinite series.

I have no clear idea of how to go about solving this and any help would be appreciated. I've had ideas of maybe computing the FFT and inverse DFT but can't see how I would reach my conclusion

Answer 1

There is division with reminder algorithm using DFT: http://www.diag.uniroma1.it/sankowski/lecture4.pdf