For some $N$ that is a power of $2$. $\huge \begin{align} X_{k} &= \op{DFT} \left( \vec x,N,k \right) \\ &=\sum_{t=0}^{N-1}x_{t} \zeta_{N}^{-kt} \end{align} $ $\huge \zeta_{N} = e^{{\frac{i{2}\pi}{N}}}$ $\huge \begin{align} X_k &= \op{DFT}\left( \vec x_{\mathrm{even}}, \frac{N}{2},k \right) + \zeta_{N}^k \op{DFT}\left( \vec x_{\mathrm{odd}} , \frac{N}{2},k \right) \\ X_{\frac{N}{2}+k} &= \op{DFT}\left( \vec x_{\mathrm{even}}, \frac{N}{2},k \right) - \zeta_{N}^k \op{DFT}\left( \vec x_{\mathrm{odd}} , \frac{N}{2},k \right) \\ \op{DFT}\left( x,1,k \right) &=x \end{align} $ Where $\vec x_{\text{even}},\vec x_{\mathrm{odd}}$ are vectors composed of only the even or odd indices of $\vec x$. $\huge \begin{align} P(x) &= \sum_{n=0}^{N-1}p_{n} x^{n} \\ Q(x) &= \sum_{m=0}^{N-1}q_{n} x^{n} \\ F(x) &= P(x)Q(x)\\ \end{align} $