Finite Fields &
Modular Arithmetic

ZK Prereqs Workshop 2 of 6

The number system that powers all of modern cryptography

Agenda

  • Why finite fields matter for ZK
  • Modular arithmetic refresher
  • What is a finite field?
  • Additive & multiplicative inverses
  • Fermat's Little Theorem
  • Division without precision loss
  • Modular square roots
  • Polynomials in finite fields
  • Python demos & Practice problems

Why Finite Fields?

The Problem

  • Real number math → rounding errors
  • Floating point → imprecise
  • Infinite sets → can't enumerate
  • Cryptography needs exact answers

The Solution

  • Finite fields give exact arithmetic
  • Division produces integers, not fractions
  • Bounded set → practical for computers
  • Foundation of elliptic curve crypto

Modular Arithmetic Refresher

Think of a clock: after 12, it wraps back to 1

a mod n = remainder when a is divided by n

  • 17 mod 5 = 2   (17 = 3×5 + 2)
  • 23 mod 7 = 2   (23 = 3×7 + 2)
  • 100 mod 11 = 1   (100 = 9×11 + 1)

We say 17 is congruent to 2 modulo 5, written 17 ≡ 2 (mod 5)

Operations in Modular Arithmetic

All operations mod p (let p = 7):

OperationExampleResult
Addition5 + 4 mod 72
Subtraction2 - 5 mod 74
Multiplication3 × 4 mod 75
Exponentiation3² mod 72
Key rule: You can take mod at any intermediate step — the result is the same.
(a + b) mod p = ((a mod p) + (b mod p)) mod p

What is a Finite Field?

A finite field π”½β‚š (or GF(p)) is:
The set {0, 1, 2, ..., p-1} with addition and multiplication mod p,
where p is prime.
  • Closed under +, −, ×, ÷ (except ÷ by 0)
  • Associative and commutative
  • Has additive identity (0) and multiplicative identity (1)
  • Every element has an additive inverse and a multiplicative inverse

Why prime? Because composite moduli lose the property that every non-zero element has a multiplicative inverse.

Why Must p Be Prime?

# Composite modulus: p = 6
# 2 Γ— 3 = 6 ≑ 0 (mod 6)  ← zero divisors!
# This means 2 has no multiplicative inverse mod 6

# Prime modulus: p = 7
# Every non-zero element has an inverse:
for a in range(1, 7):
    inv = pow(a, -1, 7)
    print(f"{a} Γ— {inv} ≑ {(a * inv) % 7} (mod 7)")

# Output:
# 1 Γ— 1 ≑ 1 (mod 7)
# 2 Γ— 4 ≑ 1 (mod 7)
# 3 Γ— 5 ≑ 1 (mod 7)
# 4 Γ— 2 ≑ 1 (mod 7)
# 5 Γ— 3 ≑ 1 (mod 7)
# 6 Γ— 6 ≑ 1 (mod 7)

Additive Inverses

The additive inverse of a is the element b such that a + b ≡ 0 (mod p)

-a ≡ p - a (mod p)
Element (mod 7)Additive InverseVerification
000 + 0 = 0
161 + 6 = 7 ≡ 0
252 + 5 = 7 ≡ 0
343 + 4 = 7 ≡ 0

Every element has a unique additive inverse. There are no "negative numbers" β€” just inverses.

Multiplicative Inverses

The multiplicative inverse of a is the element b such that a × b ≡ 1 (mod p)

By Brute Force

# Find inverse of 3 mod 7
p = 7
for b in range(1, p):
    if (3 * b) % p == 1:
        print(f"3⁻¹ ≑ {b} (mod {p})")
# 3⁻¹ ≑ 5 (mod 7)

Python Built-in

# Python 3.8+ has built-in
# modular inverse
inv = pow(3, -1, 7)
print(inv)  # 5

# Verify
assert (3 * 5) % 7 == 1

Fermat's Little Theorem

If p is prime and a is not divisible by p, then:
ap-1 ≡ 1 (mod p)
  • Direct consequence: a-1 ≡ ap-2 (mod p)
  • This gives us a formula for computing inverses!
# Verify Fermat's Little Theorem
p = 7
for a in range(1, p):
    result = pow(a, p - 1, p)
    inv_fermat = pow(a, p - 2, p)
    inv_builtin = pow(a, -1, p)
    print(f"a={a}: a^(p-1)={result}, a^(p-2)={inv_fermat}, inv={inv_builtin}")
    assert result == 1
    assert inv_fermat == inv_builtin

This theorem is the theoretical foundation for efficient modular inverse computation.

Division Without Precision Loss

In regular math: 1 ÷ 3 = 0.333... (imprecise!)

In 𝔽₇: 1 ÷ 3 = 1 × 3-1 = 1 × 5 = 5

Verify: 5 × 3 = 15 ≡ 1 (mod 7) ✓ 
p = 7

# "Divide" 1 by 3 in the finite field
result = (1 * pow(3, -1, p)) % p
print(f"1 Γ· 3 ≑ {result} (mod {p})")  # 5

# More examples
print(f"5 Γ· 2 ≑ {(5 * pow(2, -1, p)) % p} (mod {p})")  # 6
# Verify: 6 Γ— 2 = 12 ≑ 5 (mod 7) βœ“

print(f"10 Γ· 4 ≑ {(10 * pow(4, -1, p)) % p} (mod {p})")  # 6
# Verify: 6 Γ— 4 = 24 ≑ 3 (mod 7)... wait, 10 mod 7 = 3 βœ“

Encoding Rational Numbers

Any rational number a/b can be mapped into π”½β‚š:

a/b ↦ a × b-1 (mod p) 
p = 17

# Map 1/3 into the field
one_third = (1 * pow(3, -1, p)) % p
print(f"1/3 ≑ {one_third} (mod {p})")  # 6

# Map 3/5 into the field
three_fifths = (3 * pow(5, -1, p)) % p
print(f"3/5 ≑ {three_fifths} (mod {p})")  # 4

# Verify: 1/3 + 3/5 = 14/15 in regular math
regular_sum = (1*5 + 3*3) / (3*5)  # 14/15
field_sum = (one_third + three_fifths) % p
fourteen_fifteenths = (14 * pow(15, -1, p)) % p

print(f"1/3 + 3/5 = {field_sum} (mod {p})")
print(f"14/15 = {fourteen_fifteenths} (mod {p})")
assert field_sum == fourteen_fifteenths  # βœ“ Homomorphism!

Python galois Library

from galois import GF

# Create a finite field of order 7
GF7 = GF(7)

# Elements behave like regular numbers but are always mod 7
a = GF7(5)
b = GF7(3)

print(f"a + b = {a + b}")      # 1  (8 mod 7)
print(f"a * b = {a * b}")      # 1  (15 mod 7)
print(f"a / b = {a / b}")      # 4  (5 Γ— 3⁻¹ mod 7)
print(f"a ** 2 = {a ** 2}")    # 4  (25 mod 7)
print(f"-a = {-a}")            # 2  (7 - 5)

# Works with larger primes too
GF101 = GF(101)
x = GF101(50)
print(f"50⁻¹ mod 101 = {GF101(1) / x}")  # multiplicative inverse

pip install galois — Useful for experimentation and verification

Modular Square Roots

In regular math: √9 = ±3

In finite fields: √a mod p might have 0 or 2 solutions

p = 11

# Which elements have square roots mod 11?
for a in range(0, p):
    roots = [x for x in range(p) if (x * x) % p == a]
    if roots:
        print(f"√{a} mod {p} = {roots}")

# Output:
# √0 mod 11 = [0]
# √1 mod 11 = [1, 10]     ← 1Β² = 10Β² ≑ 1
# √3 mod 11 = [5, 6]      ← 5Β² = 6Β² ≑ 3
# √4 mod 11 = [2, 9]      ← 2Β² = 9Β² ≑ 4
# √5 mod 11 = [4, 7]      ← 4Β² = 7Β² ≑ 5
# √9 mod 11 = [3, 8]      ← 3Β² = 8Β² ≑ 9
Notice: the two roots always sum to p! (e.g., 5 + 6 = 11)
They are additive inverses of each other β€” just like ±3 in regular math.

Testing for Square Roots: Euler's Criterion

a(p-1)/2 ≡ 1 (mod p) ⇒ a has a square root
a(p-1)/2 ≡ p-1 (mod p) ⇒ a does NOT have a square root 
p = 11

# Test which elements are quadratic residues
for a in range(1, p):
    euler = pow(a, (p - 1) // 2, p)
    has_sqrt = euler == 1
    print(f"a={a:2d}: a^((p-1)/2) = {euler:2d} β†’ {'has' if has_sqrt else 'NO'} sqrt")

# Elements with square roots: 1, 3, 4, 5, 9  (5 out of 10)
# Elements without:           2, 6, 7, 8, 10  (5 out of 10)
# Exactly half!

Polynomials in Finite Fields

Polynomials work the same way — just reduce coefficients mod p

from galois import GF, Poly

GF7 = GF(7)

# f(x) = 3xΒ² + 2x + 5  over GF(7)
f = Poly([3, 2, 5], field=GF7)
print(f"f(x) = {f}")

# Evaluate at x = 4
print(f"f(4) = {f(GF7(4))}")  # 3(16) + 2(4) + 5 = 61 ≑ 5 mod 7

# g(x) = x + 3
g = Poly([1, 3], field=GF7)

# Polynomial addition
print(f"f + g = {f + g}")

# Polynomial multiplication
print(f"f * g = {f * g}")
Polynomials over finite fields are central to ZK proofs!
QAP, PLONK, and other ZK schemes encode computations as polynomial equations.

Why Polynomials Matter for ZK

Schwartz-Zippel Lemma (Intuition)

If two polynomials of degree d agree at more than d points, they must be the same polynomial.
  • A degree-d polynomial has at most d roots
  • If p(x) - q(x) = 0 at d+1 points → p(x) = q(x)
  • Over a large field, random evaluation is almost certainly unique
ZK Insight: The prover encodes their computation as a polynomial.
The verifier checks it at a random point.
If it passes, the polynomial (and computation) is almost certainly correct.

Linear Systems in Finite Fields

Solve 3x + 5y ≡ 2 (mod 7) and x + 4y ≡ 6 (mod 7)

p = 7

# 3x + 5y ≑ 2 (mod 7)
# x + 4y ≑ 6 (mod 7)

# From equation 2: x ≑ 6 - 4y (mod 7)
# Substitute into equation 1:
# 3(6 - 4y) + 5y ≑ 2 (mod 7)
# 18 - 12y + 5y ≑ 2 (mod 7)
# 4 - 7y ≑ 2 (mod 7)    (18 mod 7 = 4)
# 4 ≑ 2 (mod 7)         (-7y mod 7 = 0)
# Hmm, let's try different coefficients...

# Actually: 2x + 3y ≑ 1 (mod 7), 5x + y ≑ 4 (mod 7)
# From eq 2: y ≑ 4 - 5x (mod 7)
# Sub: 2x + 3(4 - 5x) ≑ 1 β†’ 2x + 12 - 15x ≑ 1 β†’ -13x ≑ -11
# β†’ x ≑ 11 Γ— pow(13, -1, 7) ≑ 4 Γ— pow(6, -1, 7) ≑ 4 Γ— 6 ≑ 3 (mod 7)
# y ≑ 4 - 5(3) ≑ 4 - 15 ≑ -11 ≑ 3 (mod 7)
# Verify: 2(3) + 3(3) = 15 ≑ 1 βœ“, 5(3) + 3 = 18 ≑ 4 βœ“
print("x = 3, y = 3")

Live Demo: Complete Field Operations

p = 23  # A prime

print("=== Finite Field GF(23) ===")
print(f"\nAdditive inverses:")
for a in [1, 5, 11, 22]:
    print(f"  -{a} ≑ {(-a) % p} (mod {p})")

print(f"\nMultiplicative inverses:")
for a in [2, 3, 7, 11]:
    inv = pow(a, -1, p)
    print(f"  {a}⁻¹ ≑ {inv} (mod {p})  [verify: {a}Γ—{inv}={a*inv}≑{(a*inv)%p}]")

print(f"\nDivision:")
for (a, b) in [(10, 3), (1, 7), (15, 4)]:
    result = (a * pow(b, -1, p)) % p
    print(f"  {a} Γ· {b} ≑ {result} (mod {p})  [verify: {result}Γ—{b}={(result*b)%p}≑{a%p}]")

print(f"\nFermat's Little Theorem:")
for a in [2, 5, 17]:
    print(f"  {a}^{p-1} ≑ {pow(a, p-1, p)} (mod {p})")  # Always 1

Real-World Field Sizes

In practice, ZK proofs use enormous primes:

# The BN128 curve (used by Ethereum) has field modulus:
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

# That's a 254-bit number!
print(f"Bits: {p.bit_length()}")  # 254

# But arithmetic still works identically:
a = 12345678901234567890
b = 98765432109876543210

print(f"a + b mod p = {(a + b) % p}")
print(f"a Γ— b mod p = {(a * b) % p}")
print(f"a / b mod p = {(a * pow(b, -1, p)) % p}")
print(f"a^(p-1) mod p = {pow(a, p - 1, p)}")  # Still 1!
Same rules, same operations — just much bigger numbers.

Key Takeaways

  • Finite field π”½β‚š = {0, 1, ..., p-1} with mod-p arithmetic (p prime)
  • Every non-zero element has a multiplicative inverse
  • Division is exact — no fractions, no rounding
  • Fermat's Little Theorem: ap-1 ≡ 1, so a-1 = ap-2
  • Polynomials work over finite fields and are the basis of ZK
  • Modular square roots exist for exactly half of non-zero elements
Everything in ZK proofs happens inside finite fields. Master this, and the rest follows.

Practice Problems

  1. Compute all multiplicative inverses in 𝔽₁₁. Verify each one.
  2. Solve: 4x ≡ 3 (mod 11). Hint: multiply both sides by 4-1
  3. Map the fraction 2/5 into 𝔽₁₃. Verify: result × 5 ≡ 2 (mod 13).
  4. Find all quadratic residues mod 13 (elements with square roots).
  5. Verify Fermat's Little Theorem for all non-zero elements of 𝔽₁₃.
  6. Using the galois library, define f(x) = x² + 3x + 2 over GF(11) and find all roots (values where f(x) = 0).

Next Workshop

Set Theory & Abstract Algebra

  • Sets, subsets, and Cartesian products
  • Binary operators and relations
  • Magma → Semigroup → Monoid → Group
  • Why this vocabulary matters for ZK

The language of abstract math gives us the power to reason about operations without understanding their implementation.