Group Theory
Deep Dive

ZK Prereqs Workshop 4 of 6

Finite groups, cyclic groups, and generators — the foundation of elliptic curve crypto

Agenda

• Quick Groups recap
• Gallery of Group examples
• Finite groups & group order
• Cyclic groups & generators
• Primitive roots
• Key properties: uniqueness of identity, cyclic ⇒ abelian
• Groups in ZK proofs

Quick Recap: What is a Group?

A set with a binary operator that has four properties:

1. Closure: a □ b is always in the set
2. Associativity: (a □ b) □ c = a □ (b □ c)
3. Identity: there exists e such that a □ e = a
4. Inverse: for every a, there exists a' such that a □ a' = e

Example 1: The Trivial Group

# The set {0} with addition
# Closure: 0 + 0 = 0 ✓ (stays in set)
# Associative: (0+0)+0 = 0+(0+0) ✓ 
# Identity: 0 (adding 0 gives 0) ✓
# Inverse: 0's inverse is 0 ✓

# This is the smallest possible group
# A group CANNOT be empty — it must have at least the identity

Example 2: Real Numbers under ×

Are real numbers a group under multiplication?

• ✓ Closed: product of reals is a real
• ✓ Associative: (a×b)×c = a×(b×c)
• ✓ Identity: 1
• ✗ Inverse: the inverse of a is 1/a, but 1/0 is undefined!

Domain sensitivity: the exact same operation can form a group or not, depending on the set.

Domain Sensitivity

Example: Matrices as Groups

Example: Polynomials under Addition

from galois import GF, Poly

GF7 = GF(7)

# Polynomials of degree ≤ 3 over GF(7) form a group under addition
f = Poly([3, 2, 5, 1], field=GF7)  # 3x³ + 2x² + 5x + 1
g = Poly([4, 5, 2, 6], field=GF7)  # 4x³ + 5x² + 2x + 6

# Closure: sum is still degree ≤ 3
print(f"f + g = {f + g}")  # coefficients reduced mod 7

# Identity: zero polynomial
zero = Poly([0], field=GF7)
print(f"f + 0 = {f + zero}")  # same as f

# Inverse: negate coefficients (mod 7)
neg_f = -f
print(f"f + (-f) = {f + neg_f}")  # zero polynomial

Addition Modulo a Prime

p = 7

# Build the complete group table
print("Addition mod 7:")
print("   | " + " ".join(f"{b}" for b in range(p)))
print("---+" + "-" * (2 * p))
for a in range(p):
    row = " ".join(f"{(a+b) % p}" for b in range(p))
    print(f" {a} | {row}")

# Verify group properties:
# Identity: 0 (row/column 0 gives same element)
# Inverse of 5: 2 (because 5+2 = 7 ≡ 0)
for a in range(p):
    inv = (p - a) % p
    assert (a + inv) % p == 0
    print(f"  Inverse of {a} is {inv}")

Multiplication Modulo a Prime (Excluding 0)

p = 7

# The set {1, 2, 3, 4, 5, 6} under × mod 7
print("Multiplication mod 7 (excluding 0):")
print("   | " + " ".join(f"{b}" for b in range(1, p)))
print("---+" + "-" * (2 * (p-1)))
for a in range(1, p):
    row = " ".join(f"{(a*b) % p}" for b in range(1, p))
    print(f" {a} | {row}")

# Identity: 1
# Inverse of a: pow(a, -1, p)
for a in range(1, p):
    inv = pow(a, -1, p)
    assert (a * inv) % p == 1
    print(f"  {a} × {inv} ≡ 1 (mod {p})")

Finite Groups & Order

• 𝔽₇ under addition: order = 7
• 𝔽₇\{0} under multiplication: order = 6
• All integers under addition: infinite order

Cyclic Groups

# Addition mod 7 is cyclic with generator 1:
p = 7
g = 1
print("Generating all elements from g=1:")
element = 0
for i in range(p):
    element = (g * i) % p  # i additions of g
    print(f"  {i} × g = {element}")

# Output: 0, 1, 2, 3, 4, 5, 6 — every element!

Starting from 1 and repeatedly adding 1 generates: 1, 2, 3, 4, 5, 6, 0 — every element of the group.

Multiplicative Cyclic Groups

Multiplication mod 7 (excluding 0) — not every element is a generator!

p = 7
g = 2
print("Powers of 2 mod 7:")
for i in range(1, p):
    print(f"  2^{i} = {pow(2,i,p)}")
# 2, 4, 1, 2, 4, 1...
# Only generates {1, 2, 4}
# NOT a generator!

p = 7
g = 3
print("Powers of 3 mod 7:")
for i in range(1, p):
    print(f"  3^{i} = {pow(3,i,p)}")
# 3, 2, 6, 4, 5, 1
# Generates {1,2,3,4,5,6}
# IS a generator!

Finding Primitive Roots

from galois import GF

# galois library can find all primitive roots
for p in [7, 11, 13, 23]:
    field = GF(p)
    roots = field.primitive_elements
    print(f"GF({p}): primitive roots = {list(roots)}")
    print(f"  {len(roots)} out of {p-1} elements are generators")
    print(f"  ratio = {len(roots)/(p-1):.1%}\n")

# Manual verification for p=7
p = 7
for g in range(1, p):
    generated = set()
    val = 1
    for _ in range(p - 1):
        val = (val * g) % p
        generated.add(val)
    is_gen = len(generated) == p - 1
    print(f"  g={g}: generates {sorted(generated)} {'← GENERATOR' if is_gen else ''}")

Cyclic ⇒ Abelian

If a group is cyclic, it is automatically abelian (commutative).

• Elliptic curve groups in ZK are cyclic → therefore abelian
• The converse is NOT true: abelian does not imply cyclic
• ℝ under addition is abelian but NOT cyclic (no single generator)

The Identity Element is Unique

• A group has exactly one identity element
• For addition groups: the identity is 0
• For multiplication groups: the identity is 1
• For elliptic curves: the identity is the "point at infinity"

Example: 2D Points as a Group

# Set: all (x, y) pairs with real coordinates
# Binary operator: element-wise addition

# Closure: (a,b) + (c,d) = (a+c, b+d) — still a point ✓
p1 = (1, 1)
p2 = (2, 3)
p3 = (p1[0]+p2[0], p1[1]+p2[1])
print(f"{p1} + {p2} = {p3}")  # (3, 4)

# Identity: the origin (0, 0)
origin = (0, 0)
print(f"{p1} + {origin} = {p1}")  # unchanged ✓

# Inverse: negate both coordinates
inv_p1 = (-p1[0], -p1[1])
print(f"{p1} + {inv_p1} = {(p1[0]+inv_p1[0], p1[1]+inv_p1[1])}")  # (0, 0) ✓

Example: Powers of a Fixed Base

# Set: {b^i : i ∈ ℤ} under multiplication (b = 2)
# {... 1/8, 1/4, 1/2, 1, 2, 4, 8, 16, ...}

b = 2

# Closure: b^x × b^y = b^(x+y) ✓
print(f"2³ × 2⁴ = 2^(3+4) = {b**3 * b**4} = {b**7}")

# Identity: b^0 = 1
print(f"2⁰ = {b**0}")

# Inverse of b^x is b^(-x)
print(f"Inverse of 2³ is 2⁻³ = {b**-3}")
print(f"2³ × 2⁻³ = {b**3 * b**-3}")  # 1 ✓

Groups in Zero Knowledge Proofs

Understanding groups gives you a vocabulary for ZK:

• "Inverse" → you immediately know what this means
• "Identity" → the neutral element
• "Cyclic" → everything comes from a generator
• "Order" → how many elements before wrapping
• "Abelian" → order of operations doesn't matter

Preview: EC Points as a Cyclic Group

# This is what we'll be doing in Workshop 6:
# from py_ecc.bn128 import G1, multiply, add, eq, neg

# G1 is the generator point
# multiply(G1, 5)     → 5G (add G to itself 5 times)
# add(A, B)           → A + B (group binary operator)
# neg(A)              → -A (group inverse)
# eq(A, B)            → A == B

# Key identity:
# multiply(G1, a) + multiply(G1, b) = multiply(G1, a + b)
# This is a HOMOMORPHISM — Workshop 5 material!

Key Takeaways

• Groups are sensitive to their domain — same operation, different sets, different structures
• Finite groups have a specific order (number of elements)
• Cyclic groups can be generated from a single element
• Primitive roots generate the full multiplicative group
• Cyclic ⇒ Abelian: cyclic groups are always commutative
• Identity is unique: there's exactly one per group
• In ZK, we exclusively use finite cyclic groups

Practice Problems

1. List all elements generated by 2 in the multiplicative group mod 11. Is 2 a primitive root?
2. Prove that if a group has prime order p, then every non-identity element is a generator.
3. Why can't strings under concatenation form a group? Identify which specific property fails.
4. For the group ℤ₁₃ under addition, find the inverse of every element.
5. Build the multiplication table for {1,2,3,4} mod 5. Verify all four group properties.
6. Find all primitive roots of GF(13) using the galois library or manually.

Next Workshop

Homomorphisms

• Structure-preserving maps between groups
• Many examples: integers → powers, strings → lengths
• Homomorphic encryption
• How ZK proofs use homomorphisms

Homomorphisms are the mathematical foundation of zero knowledge — proving computations without revealing inputs.