Discrete Fourier Transform
Motivation Let’s take a look at how we multiply two polynomials of degree \(N\): \[\begin{align*} f(x) &= 4x^{4}-2x^{3}-6x^{2}\ +4x\ +\ 3\\ g(x) &= -x^{4}+11x^{3}-9x^{2}+-1x\ +\ 6\\ \end{align*}\] We can use the distributive property to multiply two polynomials and then sum up coefficients for identical terms. \[\begin{align*} f(x) &\cdot g(x) = \\ (4x^{4}-2x^{3}-6x^{2}\ +4x\ +\ 3) &\cdot (-x^{4}+11x^{3}-9x^{2}+-1x\ +\ 6) = \\ -4x^{8}+46x^{7}-52x^{6}-56x^{5} &+ 121x^{4}-9x^{3}-67x^{2}+21x+18 \