notes - October 16, 2023

FFT in finite fields




The finite field fast Fourier transform is incredibly useful in cryptography, in particular in modern ZKP schemes like PLONK.

Let’s have the polynomial

and let

Also, let’s have the field

and in it, we have the multiplicative subgroup

We would like to have an efficient evaluation of the polynomial

at all points of
(this is for example needed in PLONK). The FFT enables us to do exactly this.

It holds:

The FFT trick is to express

as:

Note that:

And we can simplify it to have exponents smaller than

The first half of the vector uses the same arguments for

as the second half. We only need to compute
for
values.

This way, instead of evaluating the polynomial

in
values, we evaluate two polynomials in
values. Hey, but isn’t this the same number of operations?

Yeah, it’s even more operations, because we need to do the multiplications with the powers of

and some additions too. However, if we recursively split the polynomials in this way, we will end up with
steps.

And

is much less than
which is the number of operations needed if we evaluate the polynomial the naive way (like in the first matrix expression at the top of the page).

Let’s observe the example:

The polynomial has

coefficients (its degree is
), because that’s what we need to describe values in the domain of size
In our case

Let’s split

into

We would need to evaluate both polynomials at

But we split further:

To compute

we just need to have
(which is precomputed because
is some power of
) and evaluate two functions,
But we need to evaluate these two functions only at
We do the same for

And to compute

, we again just need to evaluate the function
Note that we already have
and

Now to the inverse operation – the inverse transformation in our case is a polynomial interpolation. That is, we have a set of evaluation points and need to find the coefficients of the polynomial.

Let’s observe the matrix we had above:

We didn’t need the matrix

for FFT actually, but it becomes helpful to see how to construct the inverse function.

Some quick calculation shows that the matrix

is the inverse of
So we can proceed similarly as above.

Next time, I will write about how the FFT helps speed up schemes like PLONK.

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