# 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 letAlso, let’s have the field

and in it, we have the multiplicative subgroupWe 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 caseLet’s split

intoWe 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 forAnd to compute

, we again just need to evaluate the function Note that we already have andNow 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

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