Finite Fields and Modular Arithmetic

Why finite fields, at all

Ordinary arithmetic is unbounded: 2+3=5, 4×5=20, 10/2=5, and results can grow as large as they like. That's fine for a calculator, but a cryptographic protocol can't work that way — computers store a finite number of bits, and a proving system needs every value to have an exact, bounded representation. There's no room for a number that keeps growing every time you multiply.

So instead of letting numbers grow, we wrap them. Suppose the only values allowed are {0,1,2,3,4}. Ordinarily 3+4=7, but 7 doesn't belong to that set — so we wrap around using a modulus: working mod 5, 3+4 = 7 mod 5 = 2. Finite fields take that wraparound idea and add stronger guarantees on top, so that addition, subtraction, multiplication, and — critically — division by every non-zero element all work cleanly, every time.

fig. — a field like F17 behaves like a clock face with 17 positions: every operation lands back on the wheel, nothing escapes it

What exactly is a field

A field is a set equipped with addition and multiplication that satisfy a fixed list of guarantees. Let the field be F. For all a, b, c ∈ F:

Addition closure — a+b ∈ F
Multiplication closure — ab ∈ F
Additive identity — there exists 0 such that a+0=a
Multiplicative identity — there exists 1 such that a×1=a
Multiplicative inverse — for non-zero a, a·a⁻¹=1
Associativity — (a+b)+c=a+(b+c) and (ab)c=a(bc)
Commutativity — a+b=b+a, ab=ba
Distributivity — a(b+c)=ab+ac

The multiplicative-inverse requirement is the one ordinary modular arithmetic doesn't automatically give you — it's what makes division well-defined for every non-zero element, and it's the property a proving system leans on constantly.

A finite field, and a first ZK example

A field with a finite number of elements is a finite field, usually written F_q where q = pⁿ for some prime p and integer n ≥ 1. The simplest and most common case in ZK work is a prime field, F_p.

Worked example Take p = 17 and suppose we want to prove x² = 9 — without revealing x. The prover could know x = 14, because 14² = 196, and 196 mod 17 = 9. So 14² ≡ 9 (mod 17), and a ZK proof system can establish that relationship while keeping x hidden.

That's the fundamental bridge: ZK systems turn computations into algebraic constraints evaluated over a finite field. Every later stage of a proving system — polynomials, interpolation, FFTs, FRI — is built on top of this same wraparound arithmetic.

Negative numbers inside a field

There's no separate negative-number system inside F17 — negation is just "the value that adds back to zero." So:

−1 = 16 because −1 + 17 = 16 −2 = 15 −3 = 14 −5 = 12

This matters in practice because it means subtraction can be implemented purely with addition — compute the additive inverse of the right-hand side, then add. No separate subtraction circuit or code path needed.

Real systems use much larger primes

Nobody builds a production ZK system on p = 17 — it's only useful for working examples by hand. Real fields use primes on the order of:

p ≈ 2⁶⁴ p ≈ 2¹²⁸ p ≈ 2²⁵⁴

depending on the system's security requirements. As one concrete anchor: the scalar field of BLS12-381, a curve widely used in pairing-based proving systems, is defined over a large prime modulus of this scale.

Implementing a field in Rust

Below is F17 implemented as a small Rust type, Fp. The core idea: every constructor reduces its input mod 17, so a value can never leave the field's representable range — and every arithmetic trait (Add, Sub, Mul, Neg, Div) reduces its result the same way.

    rust
    
  
// fp.rs — construction and modulus/// Prime modulus. Our field is F_17 = {0, 1, 2, ..., 16}
const MODULUS: u64 = 17;

struct Fp { value: u64 }

impl Fp {
    pub fn new(value: u64) -> Self {
        Self { value: value % MODULUS }
    }
}

Two inverse strategies are worth knowing side by side. Fermat's Little Theorem says aᵖ⁻¹ ≡ 1 (mod p) for prime p, so a⁻¹ = a^p−2 mod p — computed with fast binary exponentiation. The Extended Euclidean Algorithm finds the same inverse directly, by solving a·x ≡ 1 (mod p). Both are implemented below, and the test suite checks they always agree.

Full Fp implementation, arithmetic traits, and tests

    rust
    
  
use std::ops::{Add, Div, Mul, Neg, Sub};

/// Prime modulus.
/// Our field is F_17 = {0, 1, 2, ..., 16}
const MODULUS: u64 = 17;

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct Fp {
    value: u64,
}

impl Fp {
    // ------------------------------------------------------------
    // CONSTRUCTION
    // ------------------------------------------------------------

    /// Create a field element. Any integer is reduced modulo 17.
    /// Example: Fp::new(20) == Fp::new(3)
    pub fn new(value: u64) -> Self {
        Self { value: value % MODULUS }
    }

    pub fn zero() -> Self { Self { value: 0 } }
    pub fn one() -> Self { Self { value: 1 } }
    pub fn is_zero(self) -> bool { self.value == 0 }
    pub fn value(self) -> u64 { self.value }

    // ------------------------------------------------------------
    // EXPONENTIATION — O(log exponent) via binary exponentiation
    // ------------------------------------------------------------
    pub fn pow(self, mut exponent: u64) -> Self {
        let mut result = Self::one();
        let mut base = self;
        while exponent > 0 {
            if exponent & 1 == 1 { result = result * base; }
            base = base * base;
            exponent >>= 1;
        }
        result
    }

    // ------------------------------------------------------------
    // MULTIPLICATIVE INVERSE — Fermat: a^(-1) = a^(p-2) mod p
    // ------------------------------------------------------------
    pub fn inverse(self) -> Option<Self> {
        if self.is_zero() { return None; }
        Some(self.pow(MODULUS - 2))
    }

    // ------------------------------------------------------------
    // EXTENDED EUCLIDEAN ALGORITHM — finds x such that a*x = 1 mod p
    // ------------------------------------------------------------
    pub fn inverse_euclid(self) -> Option<Self> {
        if self.is_zero() { return None; }
        let mut old_r = self.value as i128;
        let mut r = MODULUS as i128;
        let mut old_t = 1i128;
        let mut t = 0i128;
        while r != 0 {
            let quotient = old_r / r;
            let next_r = old_r - quotient * r;
            old_r = r; r = next_r;
            let next_t = old_t - quotient * t;
            old_t = t; t = next_t;
        }
        let inverse = old_t.rem_euclid(MODULUS as i128);
        Some(Self::new(inverse as u64))
    }
}

// ================================================================
// ADD / SUB / MUL / NEG / DIV
// ================================================================
impl Add for Fp {
    type Output = Self;
    fn add(self, rhs: Self) -> Self { Self::new(self.value + rhs.value) }
}
impl Sub for Fp {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self { Self::new(self.value + MODULUS - rhs.value) }
}
impl Mul for Fp {
    type Output = Self;
    fn mul(self, rhs: Self) -> Self { Self::new(self.value * rhs.value) }
}
impl Neg for Fp {
    type Output = Self;
    fn neg(self) -> Self {
        if self.is_zero() { Self::zero() } else { Self::new(MODULUS - self.value) }
    }
}
impl Div for Fp {
    type Output = Self;
    fn div(self, rhs: Self) -> Self {
        let inverse = rhs.inverse().expect("division by zero");
        self * inverse
    }
}

// ================================================================
// TESTS
// ================================================================
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_addition() { // 15 + 5 = 20 = 3 mod 17
        assert_eq!(Fp::new(15) + Fp::new(5), Fp::new(3));
    }
    #[test]
    fn test_subtraction() { // 3 - 5 = -2 = 15 mod 17
        assert_eq!(Fp::new(3) - Fp::new(5), Fp::new(15));
    }
    #[test]
    fn test_multiplication() { // 5 * 7 = 35 = 1 mod 17
        assert_eq!(Fp::new(5) * Fp::new(7), Fp::new(1));
    }
    #[test]
    fn test_negation() { // -5 = 12 mod 17
        assert_eq!(-Fp::new(5), Fp::new(12));
    }
    #[test]
    fn test_inverse() {
        let a = Fp::new(5);
        let inverse = a.inverse().unwrap();
        assert_eq!(inverse, Fp::new(7));
        assert_eq!(a * inverse, Fp::one());
    }
    #[test]
    fn test_inverse_euclid() {
        for x in 1..MODULUS {
            let a = Fp::new(x);
            let inv1 = a.inverse().unwrap();
            let inv2 = a.inverse_euclid().unwrap();
            assert_eq!(inv1, inv2);
            assert_eq!(a * inv1, Fp::one());
        }
    }
    #[test]
    fn test_division() { // 3 / 5 = 3 * 7 = 21 = 4 mod 17
        assert_eq!(Fp::new(3) / Fp::new(5), Fp::new(4));
    }
    #[test]
    fn test_power() {
        assert_eq!(Fp::new(3).pow(2), Fp::new(9));
        assert_eq!(Fp::new(3).pow(16), Fp::one()); // 3^16 = 1 mod 17
    }
    #[test]
    fn test_zero_inverse() {
        assert_eq!(Fp::zero().inverse(), None);
    }
    #[test]
    fn test_fermat_little_theorem() {
        // For every non-zero a in F_17: a^16 = 1
        for x in 1..MODULUS {
            assert_eq!(Fp::new(x).pow(MODULUS - 1), Fp::one());
        }
    }
    #[test]
    fn test_field_elements_are_canonical() {
        assert_eq!(Fp::new(17), Fp::zero()); // 17 = 0
        assert_eq!(Fp::new(18), Fp::one());  // 18 = 1
        assert_eq!(Fp::new(34), Fp::zero()); // 34 = 0
    }
}

Four levels, one idea, increasing structure

Every level below performs the "same" addition — the difference is how much structure sits on top of it.

Level	Statement	What's guaranteed
1 Integer	`3+5=8`	Nothing bounded — grows without limit
2 Modular arithmetic	`3+5=1 (mod 7)`	Wraps around, but no inverse guarantee
3 Finite field	`3+5=1 ∈ F₇`	Every non-zero element has an inverse
4 ZK algebra	`ab−c=0 ∈ F_p`	An algebraic constraint a proof system can check

That fourth row is the bridge from basic mathematics into ZK systems: once arithmetic lives inside a finite field, a computation can be re-expressed as a set of algebraic constraints — statements that are either satisfied or aren't, and that a verifier can check far more cheaply than re-running the computation.

Where finite fields sit on the road to a STARK

This is one topic on a longer path. Everything after it — groups, polynomials, FFTs, FRI — is built directly on the guarantees a finite field provides.

01Modular arithmetic

02Equivalence classes

03Groups

04Rings

05Fields

06Prime fields F_p

07Multiplicative groups

08Fermat's theorem

09Extended Euclidean Algorithm

10Fast exponentiation

11Polynomial arithmetic

12Polynomial interpolation

13Roots of unity

14FFT / IFFT

15Evaluation domains

16Reed–Solomon codes

17Low-degree extensions

18AIR

19FRI

20STARK

What a real field implementation has to think about

The 17-element toy field above is for building intuition. A field used inside an actual proving system has a much longer list of concerns:

overflow-safe multiplication constant-time arithmetic canonical reduction Montgomery representation wide multiplication serialization deserialization equality & zero testing batch inversion optimized squaring exponentiation roots of unity domain generation Send / Sync behavior fuzz testing property-based testing

For a working reference at that level of rigor, the field implementations inside crates like ff, ark-ff, or whatever proving system you're studying are the natural next read.

Takeaway

A finite field is modular arithmetic with one extra promise kept: every non-zero element has a multiplicative inverse, so division never breaks.

That single guarantee is what lets a ZK system rewrite "prove you ran this computation correctly" as "prove these polynomial constraints hold over F_p" — the algebraic foundation everything from FFTs to FRI to a full STARK gets built on top of.