Groups & Roots of Unity

Why groups, at all

Cryptography and proving systems repeatedly perform the same kind of operation: take objects, combine them according to a rule, and keep combining the results. We need to know that this repeated computation behaves predictably. Group theory is the language for exactly that.

A group is not primarily about numbers. It is about a set of objects plus an operation that has four guarantees. Once those guarantees hold, we can reason about repeated operations without caring about the concrete representation underneath.

What exactly is a group

Let G be a set and let ⋆ be an operation that takes two elements of G and produces another element. We write (G, ⋆) for the resulting algebraic structure.

It is a group when four properties hold.

1. Closure. For every a,b ∈ G, the result a ⋆ b is also in G. The operation never leaves the set.
2. Associativity. For every a,b,c ∈ G, (a ⋆ b) ⋆ c = a ⋆ (b ⋆ c). Parentheses can move without changing the answer.
3. Identity. There is an element e ∈ G such that e ⋆ a = a ⋆ e = a. It does nothing.
4. Inverse. Every a ∈ G has an element a⁻¹ ∈ G such that a ⋆ a⁻¹ = a⁻¹ ⋆ a = e.

Notice what is not required: the operation does not have to be commutative. If a ⋆ b = b ⋆ a for every pair, the group is called abelian. Otherwise it is non-abelian.

Start with familiar examples

The last row is important. The whole finite field F₅ = {0,1,2,3,4} is a field, but its non-zero elements form a multiplicative group:

This distinction is fundamental in ZK work: addition lives on all field elements, while multiplication-with-inverses lives on the non-zero elements.

Repeated multiplication gives powers

Suppose we choose one element g in a multiplicative group. We can repeatedly multiply it by itself:

Because a finite group contains only finitely many elements, these powers must eventually repeat. Once a repetition occurs, the sequence cycles forever.

The smallest positive integer n such that

is called the order of g, written ord(g).

For example, in F₅× = {1,2,3,4}, take g=2:

We visited every non-zero element before returning to 1. Therefore ord(2)=4.

Cyclic groups and generators

If the powers of one element visit every element of the group, that element is called a generator, and the group is cyclic.

We write the cyclic group generated by g as:

If |G| = n and ord(g)=n, then g generates the entire group.

Now: what is a root of unity?

A root of unity is simply a number whose positive power equals 1.

If ω is a solution to xⁿ − 1 = 0, then ω is an n-th root of unity.

Over the complex numbers, the picture is especially intuitive. The solutions of xⁿ=1 lie equally around the unit circle:

The same definition works inside a finite field. We do not need a geometric circle. We only need an element ω satisfying ωⁿ=1.

Primitive roots of unity

There can be several n-th roots of unity. A primitive n-th root of unity is one whose order is exactly n:

So there is a direct connection:

These are the same fact viewed from two directions. The polynomial tells us the equation; the group tells us the repetition structure.

Roots of unity inside a finite field

Now connect this to finite fields. Let F_q be a finite field with q elements. Its non-zero elements form a multiplicative group:

In fact, the multiplicative group of every finite field is cyclic. Therefore there exists a generator g whose order is exactly q−1.

That immediately gives us roots of unity. If n divides q−1, define

Then:

And with g primitive, this ω has order exactly n.

Concrete example: roots in F₁₇

Take F₁₇. Its non-zero elements form a group of size 16. Because 16 = 2⁴, this field has primitive roots of unity of orders 2,4,8,16.

Take g=3. It is a generator of F₁₇×. For an 8-th root of unity:

And the intermediate powers do not equal 1, so 9 has order 8. Therefore 9 is a primitive 8-th root of unity in F₁₇.

This is the finite-field analogue of walking around a circle: the values are not visually arranged on a real-number circle, but the multiplication law produces the same cyclic structure.

Subgroups: smaller cycles inside a group

A subgroup is a subset that is itself a group under the same operation. If G is cyclic, its powers naturally create subgroups.

For the order-8 element above:

The elements {1, ω², ω⁴, ω⁶} form a subgroup of order 4. The elements {1, ω⁴} form a subgroup of order 2.

This matters because FFTs do not need the entire field's multiplicative group. They need a convenient subgroup of a specific size, usually a power of two.

Why roots of unity make FFTs possible

This is the connection that matters most for a ZK prover.

Suppose we want to evaluate a polynomial

at a structured set of points. Pick a primitive n-th root of unity ω. The evaluation domain becomes:

The crucial property is that multiplying a domain point by ω simply moves to the next point. That symmetry is what the FFT exploits.

The same root-of-unity structure appears in interpolation. The FFT converts coefficient form to evaluations; the inverse FFT converts those evaluations back to coefficients.

Deriving the FFT idea from scratch

Start with an even-sized polynomial of degree less than n. Split its coefficients into even and odd powers:

Now evaluate at x = ωᵏ:

Because ω has order n, ω² has order n/2. So the original problem of size n becomes two problems of size n/2.

That is the heart of the radix-2 FFT: the roots of unity give us exactly the recursive domain structure that the divide-and-conquer algorithm needs.

Why ZK provers love powers of two

Modern STARK implementations frequently choose an evaluation domain of size 2ᵐ. To support that efficiently, the field needs a large power-of-two subgroup.

For a prime field F_p, the multiplicative group has size p−1. Therefore we want:

The integer s is the field's 2-adicity. It tells us how large a power-of-two subgroup the field can contain.

If s ≥ m, then the field contains a primitive 2ᵐ-th root of unity, which gives an FFT domain of size 2ᵐ.

From the math to Rust

At implementation level, a root of unity is just a field element with a known multiplicative order. We can represent it with the same field type used everywhere else.

const MODULUS: u64 = 17;

// Multiplication in F_17.
fn mul(a: u64, b: u64) -> u64 {
    (a * b) % MODULUS
}

// Compute a^e with binary exponentiation.
fn pow(mut base: u64, mut e: u64) -> u64 {
    let mut result = 1;

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

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

    result
}

// ord(g) is the smallest positive n with g^n = 1.
fn order(g: u64) -> u64 {
    let mut x = 1;

    for n in 1..MODULUS {
        x = mul(x, g);

        if x == 1 {
            return n;
        }
    }

    unreachable!()
}

fn main() {
    for g in 2..MODULUS {
        if order(g) == MODULUS - 1 {
            println!("generator = {g}");
            break;
        }
    }
}

// If g generates F_p^*, and n divides p - 1:
fn root_of_unity(generator: u64, n: u64, p: u64) -> u64 {
    assert!((p - 1) % n == 0);

    // omega = g^((p - 1) / n)
    pow_mod(generator, (p - 1) / n, p)
}

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

    while exp > 0 {
        if exp & 1 == 1 {
            result = (result * base) % p;
        }

        base = (base * base) % p;
        exp >>= 1;
    }

    result
}

fn main() {
    let p = 17;
    let g = 3;

    let omega = root_of_unity(g, 8, p);

    assert_eq!(pow_mod(omega, 8, p), 1);
    println!("omega = {omega}");
}

The code is a direct translation of the mathematics:

1. Represent the finite field and its multiplication.
2. Implement exponentiation using repeated squaring.
3. Find an element whose order is p−1; that is a generator of F_p×.
4. Choose a desired domain size n dividing p−1.
5. Compute ω = g^((p−1)/n).
6. Use {1,ω,ω²,…} as the structured evaluation domain.

Where this appears in a STARK prover

Once you understand groups and roots of unity, a large part of a STARK prover becomes easier to see.

The conceptual chain is:

That chain is why this topic belongs immediately after finite fields. The field gives you the arithmetic; the group gives you the structure; roots of unity give you the structured points on which polynomial algorithms become fast.

Common mistakes to avoid

1. A field is not the same thing as its multiplicative group. The field contains zero; the multiplicative group does not.
2. Not every non-zero element is a generator. Its order may be a proper divisor of q−1.
3. ωⁿ=1 does not by itself prove that ω is primitive. You also need its order to be exactly n.
4. Roots of unity are not inherently complex numbers. They are solutions of xⁿ=1 in whatever field you are working in.
5. The FFT needs the right domain size. In a prime field, that means checking that the desired size divides p−1.
6. Field choice affects implementation. A mathematically valid field may still be a poor engineering choice if its arithmetic or available roots of unity are inconvenient.

The whole idea in one picture

If finite fields answer “what arithmetic universe are we computing in?”, groups answer “what structure does repeated operation have?”, and roots of unity answer “where can we find a perfectly structured set of evaluation points?”