Suppose we are given two polynomials p(x) and q(x) of degree n 1 and m 1 respectively, n m, and suppose we want to find p(x)/q(x). Consider the following algorithm:

Algorithm Div-Poly(p, q)

1. Let n' be the smallest power of 2 greater than n.

2. Use the FFT to compute y = DFTn'(p), and z = DFTn'(q).

3. Compute the n'-dimensional vector

4. Compute a = DFT1 n' (), and return this as the coefficient vector for p(x)/q(x).

Give a formal characterization of all the different circumstances under which this procedure will (respectively will not) correctly reconstruct the coefficient representation of a polynomial r(x) such that r(x) = p(x)/q(x) for all x. Prove your answers.