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

and

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 values

Not 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 of
we will have

It 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:

Boogie Math Newsletter

Some characters on this website might be partially or entirely fictional. You have been warned, my friend!

© 2023 Boogie Math, all rights reserved Follow us: Twitter