FFT / IFFT

Why do we need the FFT?

In the previous topic, we saw that a polynomial can be represented in two important ways:

Suppose we have:

and we want to evaluate it at many points:

If we evaluate the polynomial independently at every point, the straightforward method takes roughly O(n²) work.

The Fast Fourier Transform is a clever algorithm that computes the same transformation in O(n log n) time by exploiting a special structure in the evaluation points.

Start with the DFT

Before understanding the FFT, we need to understand the Discrete Fourier Transform.

Choose an integer n and a special element ω satisfying:

Ideally, ω has exact order n:

Such an element is called a primitive n-th root of unity.

Now evaluate the polynomial at the structured points:

At point ωᵏ:

Therefore the DFT is:

This is exactly the evaluation of a polynomial at the powers of ω.

The DFT as a matrix

The DFT can also be written as matrix multiplication.

The matrix contains powers of ω. A generic matrix-vector multiplication needs n² multiplications, which is exactly the expensive part we want to avoid.

The FFT does not change this matrix. Instead, it discovers that the matrix has a recursive structure.

The key identity behind the FFT

Assume n is even. Split the polynomial into its even and odd coefficients:

Define:

Then:

This equation is the heart of radix-2 FFT.

Why roots of unity make the split work

We evaluate at:

For the first half of the points, we use:

Now look at the second half:

Because ωⁿ = 1:

And because ωⁿᐟ² = −1 for a primitive even-order root:

So once we know the even and odd transforms, two outputs are obtained with just:

The butterfly

Those two equations are called a butterfly operation.

             Eₖ
              │
              ├────── (+) ────── yₖ
              │        ↑
              │       ωᵏ
              │        │
             Oₖ ───────┘
              │
              ├────── (−) ────── yₖ₊ₙ/₂
              │
              └── multiply by ωᵏ

More precisely:

The same pattern appears repeatedly at every level of the FFT recursion.

A complete 4-point FFT by hand

Take four coefficients:

The polynomial is:

Split into even and odd parts:

Now each is only a 2-point transform. If ω is a primitive 4th root of unity, then:

The first two outputs are:

and the remaining two are:

Notice what happened: four evaluations were reduced to smaller two-point transforms and a handful of butterflies.

Where does O(n log n) come from?

At every recursion level, the total number of elements being processed is still n.

For a power-of-two input, the recursion has:

Each level performs roughly n work, so:

For large proving systems, this difference is enormous.

What is the IFFT?

The inverse FFT reverses the forward transformation.

The forward transform is:

To recover the coefficients, use the inverse root:

and divide by n:

The inverse FFT is simply a fast algorithm for computing this inverse transform.

Why does the inverse formula work?

The key identity is the orthogonality of roots of unity:

Start with the proposed inverse:

Substitute the forward transform:

Every term disappears except the one where r=j. That surviving term contributes n, which is canceled by n⁻¹.

That is the algebraic reason the inverse transform recovers the original coefficients.

FFT over a finite field

In ZK systems, we usually do not perform FFTs over floating-point complex numbers. We perform them inside a finite field.

The same mathematics works as long as the field contains a primitive n-th root of unity.

For a prime field Fₚ, the non-zero elements form a multiplicative group of size:

Therefore an n-th root of unity can exist only when:

This is one of the most important field-selection requirements for FFT-friendly proving systems.

Example: a 4-point FFT in F₁₇

Take the field:

We need a primitive 4th root of unity. Take:

Check:

And neither 4¹ nor 4² equals 1, so 4 has order 4.

Therefore our evaluation domain is:

because:

The FFT evaluates the polynomial exactly at those four field elements. There are no floating-point approximations.

Recursive radix-2 FFT

The mathematical recursion can be written almost directly as code:

For each pair of outputs:

At the base case, a one-element transform is already complete.

From the math to Rust

Here is a small recursive FFT implementation over F₁₇. It deliberately mirrors the derivation above rather than hiding the algorithm behind a library.

// Radix-2 FFT / IFFT over F_17.
// Input length must be a power of two.

const P: u64 = 17;

fn add(a: u64, b: u64) -> u64 {
    (a + b) % P
}

fn sub(a: u64, b: u64) -> u64 {
    (a + P - b) % P
}

fn mul(a: u64, b: u64) -> u64 {
    (a * b) % P
}

fn pow(mut base: u64, mut exp: u64) -> u64 {
    let mut result = 1;

    while exp > 0 {
        if exp & 1 == 1 {
            result = mul(result, base);
        }

        base = mul(base, base);
        exp >>= 1;
    }

    result
}

fn inv(a: u64) -> u64 {
    assert!(a != 0);
    pow(a, P - 2)
}

fn is_power_of_two(n: usize) -> bool {
    n != 0 && (n & (n - 1)) == 0
}

// Recursive radix-2 FFT.
// root is a primitive n-th root of unity.
fn fft(values: &[u64], root: u64) -> Vec<u64> {
    let n = values.len();

    assert!(is_power_of_two(n));

    if n == 1 {
        return vec![values[0] % P];
    }

    // Split into even and odd coefficients.
    let even: Vec<u64> =
        values.iter().step_by(2).copied().collect();

    let odd: Vec<u64> =
        values.iter().skip(1).step_by(2).copied().collect();

    // root^2 is a primitive (n/2)-th root.
    let half_root = mul(root, root);

    let even_fft = fft(&even, half_root);
    let odd_fft = fft(&odd, half_root);

    let mut output = vec![0; n];

    // Butterfly stage.
    let mut omega = 1;

    for k in 0..n / 2 {
        let t = mul(omega, odd_fft[k]);

        output[k] =
            add(even_fft[k], t);

        output[k + n / 2] =
            sub(even_fft[k], t);

        omega = mul(omega, root);
    }

    output
}

fn ifft(values: &[u64], root: u64) -> Vec<u64> {
    let n = values.len();

    // Inverse FFT uses root^(-1).
    let inverse_root = inv(root);

    let mut result =
        fft(values, inverse_root);

    // Multiply every coefficient by n^(-1).
    let n_inv = inv(n as u64);

    for value in &mut result {
        *value = mul(*value, n_inv);
    }

    result
}

fn main() {
    // 4 is a primitive 4th root of unity in F_17.
    let root = 4;

    // f(x) = 1 + 2x + 3x^2 + 4x^3
    let coefficients = vec![1, 2, 3, 4];

    let evaluations =
        fft(&coefficients, root);

    println!("evaluations = {:?}", evaluations);

    let recovered =
        ifft(&evaluations, root);

    println!("recovered    = {:?}", recovered);

    assert_eq!(recovered, coefficients);
}

Notice how closely the implementation follows the mathematics:

1. Split the input into even and odd coefficients.
2. Recursively transform both halves.
3. Square the root to obtain the root for the smaller problem.
4. Multiply the odd result by the appropriate power of ω.
5. Add and subtract to form the butterfly outputs.
6. For IFFT, use ω⁻¹.
7. Finally multiply every result by n⁻¹.

Why production FFT implementations look different

The recursive version is excellent for understanding the algorithm, but a high-performance prover normally avoids allocating new vectors at every recursion level.

Production implementations commonly use an iterative in-place FFT:

For radix-2 FFT, the iterative algorithm typically starts with a bit-reversal permutation, then executes butterfly layers of size 2, 4, 8, and so on until the entire vector has been transformed.

The mathematics is the same. Only the execution order changes.

Why FFT is so important in ZK

FFT is not just a generic optimization that happens to be useful for cryptography. It is one of the core pieces that makes large polynomial workloads practical.

A simplified STARK-style flow is:

FFT and polynomial multiplication

There is another extremely important reason FFT matters: polynomial multiplication is convolution of coefficients.

If:

then:

That is exactly convolution.

FFT converts this into a much easier operation:

So polynomial multiplication can be reduced to:

This is the same high-level idea behind fast convolution algorithms.

FFT-friendly domains and 2-adicity

Radix-2 FFT repeatedly needs domains whose size can be divided by two:

Therefore powers of two are especially convenient:

For a prime field Fₚ, we need:

The largest power of two dividing p−1 is related to the field's 2-adicity.

This matters enormously in ZK engineering because large radix-2 evaluation domains allow efficient FFTs and FRI-friendly polynomial processing.

Common mistakes

The whole idea in one map

If polynomials answer “what algebraic object represents the computation?”, FFT answers “how can we move between its coefficient and evaluation representations fast enough to actually build a prover?”