FFT in action

Let's have the polynomial $p(x) = a_0 + a_1 \cdot x + ... + a_{n-1} \cdot x^{n-1}$ and the domain $\{1, \omega, \omega^2, ..., \omega^{n-1}\}.$ That means we are only interested in the evaluations of the polynomial at the points of this domain. This is the case for example in Plonk.

Note that $\omega^n = 1.$

It holds:

$\begin{pmatrix} p(1) \\ p(\omega) \\ ... \\ p(\omega^{n-1}) \end{pmatrix} = \begin{pmatrix}1 & 1 & 1 &... & 1 \\1 & \omega & \omega^2 & ... & \omega^{n-1} \\... & ... & ... & ...& ... \\1 & \omega^{n-1} & \omega^{2(n-1)} & ... & \omega^{(n-1)(n-1)} \end{pmatrix} \cdot \begin{pmatrix} a_0 \\ a_1 \\ ... \\ a_{n-1} \end{pmatrix}$

Let's denote

$a = \begin{pmatrix} a_0 \\ a_1 \\ ... \\ a_{n-1} \end{pmatrix}$

and

$e = \begin{pmatrix} p(1) \\ p(\omega) \\ ... \\ p(\omega^{n-1}) \end{pmatrix}$

For a polynomial, FFT enables us to efficiently move between the coefficient form and its evaluations (between $a \text{ and } e$).

Switching between the two forms is useful because it enables for example a simple division of polynomials − it takes time to divide a polynomial by a polynomial, but if we only do it at the points of our domain, there are only $n$ simple divisions (dividing a field element by a field element). So, if we need to divide $p$ by the polynomial $x^n - 1,$ we just divide the values in the vector $e$ by the values $1^n - 1, \omega^n - 1, \omega^{2n} - 1, ..., \omega^{(n-1)n}-1.$

Not really.

The element $\omega$ is of the order $n,$ so for every integer $i$ it holds:

$\omega^{in} - 1 = 0$

We cannot divide by zero. We can get around this problem though, we just need to move into the coset domain.

Let's say we have the element $z.$ Instead of

$a = \begin{pmatrix} a_0 \\ a_1 \\ ... \\ a_{n-1} \end{pmatrix}$

we will have

$a_z = \begin{pmatrix} a_0z^0 \\ a_1z^1 \\ ... \\ a_{n-1}z^{n-1} \end{pmatrix}$

It holds:

$\begin{pmatrix} p(z) \\ p(z\omega) \\ ... \\ p(z\omega^{n-1}) \end{pmatrix} = \begin{pmatrix}1 & 1 & 1 &... & 1 \\1 & \omega & \omega^2 & ... & \omega^{n-1} \\... & ... & ... & ...& ... \\1 & \omega^{n-1} & \omega^{2(n-1)} & ... & \omega^{(n-1)(n-1)} \end{pmatrix} \cdot \begin{pmatrix} a_0z^0 \\ a_1z^1 \\ ... \\ a_{n-1}z^{n-1} \end{pmatrix}$

Now we can divide $p(z), p(zw), p(zw^2),..., p(zw^{n-1})$ by the values $z^n - 1, z^n\omega^n - 1, z^n\omega^{2n} - 1,..., z^n\omega^{n-1}-1$ because these values are not zero. We obtain the polynomial $\frac{p(x)}{x^n-1}$ evaluated at $n$ points: $z, z\omega, z\omega^2,..., z\omega^{n-1}.$

Now, we can use the FFT to switch back to the coefficient form of $\frac{p(x)}{x^n-1}.$

We can make things even more efficient by choosing $z$ such that $z^3 = 1.$ This way we operate with only three values: $z, z^2, 1.$ For example, $a_z$ becomes:

$a_z = \begin{pmatrix} a_0 \\ a_1z \\ a_2z^2 \\ a_3 \\ a_4z\\ a_5z^2 \\ a_6 \\ ... \\ a_{n-1}z^{n-1} \end{pmatrix}$