On relation between FFT and polynomial multiplication
Suppose you have vectors $u$ and $v$. Imagine a table $M$ of the products of each of their entries.

$$M = |u\rangle\langle v| = \begin{bmatrix}
u_0 v_0 &amp; u_1 v_0 &amp; u_2 v_0 &amp; \dots &amp; u_{n-1} v_0 \\
u_0 v_1 &amp; u_1 v_1 &amp; u_2 v_1 &amp; \dots &amp; u_{n-1} v_1 \\
u_0 v_2 &amp; u_1 v_2 &amp; u_2 v_2 &amp; \dots &amp; u_{n-1} v_2 \\
\vdots &amp;\vdots &amp;\vdots &amp; \ddots &amp; \vdots \\
u_0 v_{n-1} &amp; u_1 v_{n-1} &amp; u_2 v_{n-1} &amp; \dots &amp; u_{n-1} v_{n-1} \\
\end{bmatrix}$$

The convolution $u \ast v$ of the two vectors is a vector of the values you get when summing along each anti-diagonal of this grid. For example:

$$(u \ast v)_2 = \sum \begin{bmatrix}
 &amp;  &amp;  &amp;  &amp;   &amp; &amp; u_{n-3} v_0 &amp; 0 &amp; 0\\
 &amp;  &amp;  &amp;  &amp;   &amp; u_{n-4} v_1 \\
 &amp;  &amp;  &amp;  &amp; \ddots \\
 &amp;  &amp;  &amp; u_2 v_{n-5} &amp;  \\
 &amp;  &amp; u_1 v_{n-4} &amp;  &amp;  \\
u_0 v_{n-3} &amp;  &amp;  &amp;  &amp;  \\
0 &amp;\\
0&amp;
\text{ }
\end{bmatrix}$$

We can also think of the FFT of a vector as summing entries in a grid defined by multiplying two vectors' entries. The second vector is the sequence of roots of unity.

$$M = | u \rangle \langle e^{\tau i k/n} |\begin{bmatrix}
u_0 &amp; u_1 &amp; u_2 &amp; \dots &amp; u_{n-1} \\
u_0 e^{\tau/n} &amp; u_1 e^{\tau/n} &amp; u_2 e^{\tau/n} &amp; \dots &amp; u_{n-1} e^{\tau/n} \\
u_0 e^{2\tau/n} &amp; u_1 e^{2\tau/n} &amp; u_2 e^{2\tau/n} &amp; \dots &amp; u_{n-1} e^{2\tau/n} \\
\vdots &amp;\vdots &amp;\vdots &amp; \ddots &amp; \vdots \\
u_0 e^{-\tau/n} &amp; u_1 e^{-\tau/n} &amp; u_2 e^{-\tau/n} &amp; \dots &amp; u_{n-1} e^{-\tau/n}
\end{bmatrix}$$

The Fourier transform doesn't track along the diagonals, though. Its row-hop is different from its column-hop. For the $k$'th entry of the output we go through each column $c$ and sum up the cell from that column and the $k \cdot c$'th row (wrapping around).

$$FFT(v)_2 = \sum \begin{bmatrix}
u_0 \\
 &amp;&amp;&amp;&amp;u_4e^{\tau/7} \\
 &amp; u_1 e^{2\tau/7} \\
 &amp;&amp;&amp;&amp;&amp;u_5e^{3\tau/7} \\
 &amp; &amp; u_2 e^{4\tau/7} \\
 &amp;&amp;&amp;&amp;&amp;&amp;u_6e^{5\tau/7} \\
 &amp;&amp;&amp; u_3 e^{6\tau/7} \\
\end{bmatrix}$$

So our question becomes: can we somehow re-arrange our vectors so that the each-stride sums $\sum u_i v_{k \cdot i}$ correspond to the each-diagonal sums $\sum u_i v_{k-i}$? Can we turn index-multiplication into index-adding?

We can, as long as we're operating in a context that allows for a logarithm. Suppose our vector size is $n$ and $g$ is a multiplicative generator for the integers modulo $n$. Then we can use the powers of $g$, i.e. the base-$g$ discrete logarithm, to define a permutation of the non-zero elements that does most of what we need. Our transformation goes roughly as follows:


Define permuted vectors $a$ and $b$ so that $a_k = u_{g^k}$ and $b_k = v_{g^{k}}$.
Compute the convolution $c = a \ast b$. So $c_k = \sum_{d=0}^{n-1} a_d b_{k-d} = \sum_{d=0}^{n-1} u_{g^d} v_{g^{-k} \cdot g^d}$.
Now un-permute $c$, and also un-permute the sum over $d$. $x_{g^{-k}} = c_{k}$ and $e=g^d$. So $x_k = c_{\log_g k} = \sum_{e=0}^{n-1} u_{e} v_{k \cdot e}$.


In other words: define a permutation $P$ based on when indices are reached when iteratively multiplying by $g$. Permute the input vector and the vector of $e^{\tau k /n}$ powers by $P$. Convolve. Unpermute by $P$. The result is the Fourier transform.

... Except that I've ignored one important issue. Our permutation doesn't work for $k=0$, because $g^k \mod n$ is never 0. Also, $g^0 = g^{n-1} = 1$. Fixing this hole requires special-casing the edges of the grid. But hopefully I've communicated the core idea of performing an FFT by delegating the heavy-lifting to a convolution and a permutation.

Note that, if you care about bit complexity instead of the number of arithmetic operations, computing the permutation may also be an obstacle. If multiplying by $g \pmod{n}$ costs $\log n$ time, and you don't have the permutation ahead of time, then overall the algorithm will still cost $O(n \log n)$.