So the problem we need to solve is that of multiplying polynomials fast. Doing it the regular convolution way takes quadratic time -O(n2). This is OK for small n but won't do for large n. So what do we do? Here is a sketch of what needs to be done -the Discrete Fourier Transform: Take two polynomial