Univariate Polynomial Multiplication Using FFT

Here is a brief explanation of polynomial multiplication in evaluation form using Fast Fourier Transform (FFT):

$$\text{Given two polynomials in coefficient form:}$$

$$f(x) = a_0 + a_1x + a_2x^2 + \dots + a_nx^n$$

$$g(x) = b_0 + b_1x + b_2x^2 + \dots + b_mx^m$$

1. Convert to evaluation form using FFT:

   • Evaluate the polynomials $f(x)$ and $g(x)$ at $2n+2m+2$ distinct points, typically roots of unity.

   • This converts the polynomials from coefficient form to evaluation form, where each polynomial is represented by its values at the evaluation points.

2. Perform polynomial multiplication in evaluation form:

   • Multiply the corresponding evaluated values of $f(x)$ and $g(x)$ at each evaluation point.

   • This is a pointwise multiplication, which is very efficient compared to performing a full polynomial multiplication in coefficient form.

3. Convert the result back to coefficient form using IFFT:

   • Apply the Inverse Fast Fourier Transform (IFFT) to the multiplied evaluation form values to obtain the coefficients of the product polynomial in coefficient form.

This approach using FFT and evaluation form is much more efficient than the traditional polynomial multiplication in coefficient form, especially for high-degree polynomials. The FFT and IFFT steps provide a significant speedup, making this method practical for many applications involving polynomial arithmetic.