Mathematicians spent centuries doing algebra. Then in the late 1800s they asked: what if we classify the rules themselves? This week's lecture was about that classification — and why it matters for ZK proofs.
Last week we covered modular arithmetic — addition, multiplication, inverses, all in a finite set of numbers. This week João stepped back and asked a deeper question: what exactly makes these operations work the way they do?
The answer is abstract algebra — sometimes called modern algebra. It's the branch of mathematics that classifies mathematical structures by the rules their operations follow. Not the specific numbers or objects, but the rules themselves.
Here's the key insight: integers, rationals, matrices, polynomials, elliptic curve points — they all look completely different, but some of them follow the exact same rules. If you classify by rules instead of by the objects, you can reason about all of them at once. A theorem you prove for "groups" automatically applies to anything that's a group — whether it's numbers, matrices, or points on an elliptic curve.
Why this matters for ZK: Next week, elliptic curve points will form a group. If you understand what a group is — the abstract rules, not just specific examples — you'll immediately understand what operations are legal on elliptic curves and what properties those operations guarantee. That's the payoff.
Abstract algebra is surprisingly recent. The term "algebra" itself goes back five centuries — it originally meant the art of solving equations. Mathematicians found formulas for quadratic equations, cubic equations, quartic equations. Then Évariste Galois (in the 1830s) showed you can't have a general formula for fifth-degree equations. That proof involved analyzing permutations of roots — and those permutations followed certain rules. That was the seed of group theory.
By the late 1800s and early 1900s, mathematicians had accumulated a zoo of objects — integers, rationals, reals, complex numbers, matrices, polynomials, permutations — and they started asking: which of these are fundamentally "the same" in terms of what you can do with them? The result was a hierarchy of algebraic structures, each defined by increasingly strict rules.
João's framing: Before abstract algebra, math was practical — here's an equation, solve it. After abstract algebra, math became axiomatic — let's define the rules first, then see what follows. This shift happened around the same time as Hilbert's formalism and set theory. There's a great book called Plato's Ghost about this transformation in mathematical thinking.
Before we can talk about groups, rings, or fields, we need the thing they're all built on: sets. A set is simply a collection of distinct elements. No operations, no order, no duplicates. Just a bag of things.
The symbol ∈ means "is an element of" or "belongs to." It's how you say whether something is inside a set or not.
3 ∈ {1, 2, 3, 4, 5} — true. 3 is in the set.
7 ∈ {1, 2, 3, 4, 5} — false. We write 7 ∉ {1, 2, 3, 4, 5}.
0 ∈ ℕ — this is actually debated! João was firm: zero is NOT a natural number (he even disagreed with his kids' school textbook about this). In our course, ℕ = {1, 2, 3, ...} with no zero.
That's the only question a set answers: is this element in the bag, or not? There's no "add two elements" or "compare elements." Just membership. ∈ or ∉.
A subset is a set entirely contained inside another set. If every element of A is also in B, then A is a subset of B, written A ⊆ B.
A proper subset means A is inside B but A ≠ B — B has at least one element that A doesn't. Written A ⊂ B. In the example above, {1, 2, 3} ⊂ {1, 2, 3, 4, 5} because B has extra elements. But {1, 2, 3} is NOT a proper subset of {1, 2, 3} — they're equal.
Think of it this way: subset (⊆) means "fits inside or equals." Proper subset (⊂) means "fits inside but is strictly smaller."
These are the two fundamental ways to combine sets:
Union (A ∪ B) — everything that's in A or B (or both). You merge the two bags together, removing duplicates.
Intersection (A ∩ B) — only the elements that are in both A and B. The overlap.
Why sets matter for what comes next: Every algebraic structure we're about to build — magma, group, ring, field — starts with a set. Then we add an operation. Then we add rules. The set is the raw material; the rules are what give it power. Without understanding what a set is, you can't define any of the structures below.
In cryptography specifically: when we write 𝔽7 = {0, 1, 2, 3, 4, 5, 6}, that's a set. When we say 𝔽7* = {1, 2, 3, 4, 5, 6}, that's a subset (zero removed). When we say "the elements with gcd = 1 form the units," we're taking an intersection of the set with a property. The language of sets is the language everything else is written in.
Now that we have sets as our foundation, we start adding structure. Each new rule we impose creates a new algebraic structure, and each one is strictly more powerful than the last:
| Structure | What you add | Intuition |
|---|---|---|
| Set | Nothing | A bag of elements. Can't do anything with them. |
| Magma | + Closed binary operation | You can combine two elements, and the result stays in the set. |
| Semigroup | + Associativity | Parentheses don't matter: (a ○ b) ○ c = a ○ (b ○ c) |
| Monoid | + Identity element | There's a "do nothing" element: a ○ e = e ○ a = a |
| Group | + Inverses for all elements | Every action can be undone: a ○ a⁻¹ = identity |
| Ring | + Second operation (×) with associativity + distributivity | You can add, subtract, and multiply. But not necessarily divide. |
| Field | + Multiplicative inverses (÷) | You can add, subtract, multiply, AND divide. Full arithmetic. |
Let's walk through each one with concrete examples, exactly as João did in class.
Take a set. Define a way to combine two elements. Make sure the result is always in the set. That's it — you have a magma.
"Closed binary operation" sounds fancy but it's simple: if you pick any two elements from your set and apply the operation, you must get back an element that's in the set. No escaping.
Natural numbers {1, 2, 3, ...} with addition? That's a magma — 1 + 2 = 3, still a natural. Any two naturals added together give a natural. Closure holds.
A magma where the operation is associative. Associativity means:
(a ○ b) ○ c = a ○ (b ○ c)
The grouping (parentheses) doesn't change the result. This is NOT the same as commutativity (a ○ b = b ○ a), which is about the order. Associativity is about how you group three or more elements.
Don't confuse these: Associativity = parentheses don't matter. Commutativity = order doesn't matter. Matrix multiplication is associative but NOT commutative. These are independent properties.
Natural numbers with addition? Associative — (2 + 3) + 4 = 2 + (3 + 4) = 9. So it's a semigroup.
A semigroup with an identity element — a special element e that does nothing when combined with any other element:
a ○ e = e ○ a = a
For addition, the identity is 0 (anything + 0 = itself). For multiplication, the identity is 1 (anything × 1 = itself).
Closed? Yes. Associative? Yes. Identity? We'd need 0, but 0 is not a natural number.
NOT A MONOID — it stops here. It's only a semigroup.
João was adamant about this: "My kid's school textbook puts 0 in the naturals. I tell them they're wrong." Whether 0 ∈ ℕ is a convention that varies — but in this course, it doesn't.
Closed? Yes. Associative? Yes. Identity? Yes — it's 1 (anything × 1 = itself).
MONOID ✅ — but not a group, because there are no multiplicative inverses in the integers (1/3 isn't an integer).
A monoid where every element has an inverse. For every element a, there exists some a⁻¹ such that:
a ○ a⁻¹ = a⁻¹ ○ a = identity
The inverse "undoes" the operation. For addition, the inverse of 3 is −3 (because 3 + (−3) = 0). For multiplication, the inverse of 3 is 1/3 (because 3 × 1/3 = 1).
A group gives you an operation and its undo. If the operation is addition, the group automatically gives you subtraction (via additive inverses). If the operation is multiplication, the group gives you division (via multiplicative inverses).
João walked through the most important example in class, having a student check each property:
Closed? Yes — integer + integer = integer.
Associative? Yes — (2 + 3) + 4 = 2 + (3 + 4).
Identity? Yes — it's 0.
Inverses? Yes — inverse of 3 is −3, inverse of −7 is 7, inverse of 0 is 0 (0 + 0 = 0, the inverse can be itself).
GROUP ✅
The inverse can be itself. A student asked: "Does 0 have an inverse?" Yes — 0 + 0 = 0. The inverse of 0 is 0. There's no rule saying the inverse must be a different element.
Closed? Yes. Associative? Yes. Identity? Yes — it's 1.
Inverses? No! The multiplicative inverse of 3 would be 1/3, but 1/3 is not an integer.
NOT A GROUP — only a monoid. This is why you can't divide integers and stay in the integers.
Closed? Yes. Associative? Yes. Identity? 1. Inverses? Yes — inverse of a/b is b/a. Every non-zero rational has a multiplicative inverse that's rational.
GROUP ✅ — This is why rational numbers support division (excluding zero).
Why exclude zero? Because zero has no multiplicative inverse. There's no number x where 0 × x = 1. So if we want multiplicative inverses for all elements, zero must go. This "exclude zero" pattern comes back when we define fields.
There was also a tricky non-example that João explored: rationals under division. Division isn't associative — (12 ÷ 6) ÷ 2 = 1, but 12 ÷ (6 ÷ 2) = 4. Same elements, different grouping, different answer. Without associativity, you can't even reach monoid, let alone group. Not every operation works.
This is the structure we actually need for cryptography. A field is where you can do all four basic operations: addition, subtraction, multiplication, and division. To get there, you need two operations, not just one.
Why is it structured this way? Because addition and subtraction are one group (subtraction = adding the inverse). Multiplication and division are another group (division = multiplying by the inverse). Two groups give you four operations. And distributivity is the bridge — without it, the two operations would exist independently with no way to mix them. You couldn't simplify something like 3 × (x + 2).
Why remove zero from the multiplicative group? Same reason as before: zero has no multiplicative inverse. You can't divide by zero. So the multiplicative group operates on everything except the additive identity.
The integers form a ring — a weaker structure where the second operation (multiplication) doesn't need inverses. You can add, subtract, and multiply, but you can't always divide. Rings are useful in math, but for cryptography, we need the full power of a field.
This was the key worked example in class. Is this set with addition mod 6 and multiplication mod 6 a field? Let's check both groups.
Identity: 0 (anything + 0 mod 6 = itself). ✅
Inverses: João walked through each element:
All elements have additive inverses. Addition mod 6 is a group. ✅
Now we check {1, 2, 3, 4, 5} with multiplication mod 6. Identity is 1. Do all elements have multiplicative inverses?
The number 2 has no multiplicative inverse mod 6. You can try every element — none of them satisfy 2 × ? ≡ 1 (mod 6). So {1, 2, 3, 4, 5} with multiplication mod 6 is not a group, and therefore the whole structure is not a field.
The root cause: 6 is not prime. For a number a to have a multiplicative inverse mod n, the greatest common divisor gcd(a, n) must be 1. Since gcd(2, 6) = 2 ≠ 1, the number 2 can never have an inverse mod 6. This is exactly why finite fields require a prime modulus.
This was João's punchline. For ZK cryptography, we need a structure where we can add, subtract, multiply, and divide. We need a field. But we also need it to be:
The simplest finite fields are called prime fields:
This is why last week's modular arithmetic always used prime moduli. It wasn't arbitrary — it's because prime moduli are the only ones that give you a finite field. Mod 6 doesn't work (not prime). Mod 7 does. Mod 11 does. Mod 2,147,483,647 does (it's a Mersenne prime).
João also mentioned that there are other finite fields called extension fields where the elements are polynomials instead of numbers. These are used in some cryptographic schemes, but for Groth16 we'll stick with prime fields.
Here's the connection João previewed: elliptic curves form a group. The "elements" are points on a curve, and the "operation" is a geometric rule for combining two points to get a third point. That operation is closed, associative, has an identity (the "point at infinity"), and every point has an inverse.
If you understand what a group is — abstractly, not just for numbers — you immediately know what an elliptic curve group gives you: you can "add" points, and you can "undo" that addition. You also know what you can't do: since it's a group (one operation) and not a field (two operations), you can't "multiply" two points together. This constraint is fundamental to elliptic curve cryptography — the inability to directly "multiply" points is what makes the discrete logarithm problem hard.
I came into this week thinking abstract algebra was going to be dry theory disconnected from auditing. I was wrong. The classification tells you exactly what operations are safe and what can go wrong.
If a cryptographic implementation assumes it's working in a field but the modulus isn't prime, division silently breaks — you get elements with no inverse, and any computation that depends on division produces garbage. If a protocol treats elliptic curve points as if they have two operations (field) when they only have one (group), the security assumptions collapse. If an implementation doesn't check that its elements actually belong to the group (not just any point on the curve, but a point in the correct subgroup), you get invalid curve attacks.
The abstract classification isn't abstract at all. It's a specification. Violate it and things break — sometimes silently.
Week 3 is elliptic curves — taking these abstract group rules and instantiating them with actual geometric objects. Points on curves that you can "add" together using a weird geometric rule involving drawing lines and finding intersections. That's where the math starts feeling like magic.
Also: the course has chunked exercises (chapters 6, 7, 8, possibly 9) to do before next session. João's advice: a little bit every day. The chunked exercises go deeper into the details than the lecture can cover — especially on sets and groups.
Week 2 done. Now I know what a group is — and next week I'll see one made of points on a curve. 🧮