notes
- February 19, 2024

# FFT in action

Let's have the polynomial

and the domain 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

It holds:

Let's denote

For a polynomial, FFT enables us to efficiently move between the coefficient form and its evaluations (between

).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

simple divisions (dividing a field element by a field element). So, if we need to divide by the polynomial we just divide the values in the vector by the valuesNot really.

The element

is of the order so for every integer it holds: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

Instead ofIt holds:

Now we can divide

by the values because these values are not zero. We obtain the polynomial evaluated at points:Now, we can use the FFT to switch back to the coefficient form of

We can make things even more efficient by choosing

such that This way we operate with only three values: For example, becomes: