"F is a prime field of super-polynomial size
”PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge (2019)
In this article, we will finally learn what a “field” is.
In the previous article, we covered group theory. We defined a group as a set that, when equipped with a single binary operator, satisfies four specific properties: closure, it has an identity element, every element has an inverse, and the operator is associative. This made up the acronym "Cyfrin Is Incredibly Awesome."
Additionally, we defined an Abelian group as a group that also has the property of being commutative.
In this article, we will extend this knowledge to define two new algebraic structures:
- Rings
- Fields
These structures are used in cryptography, and understanding what they are and what their properties are is necessary for understanding the math behind zero-knowledge proofs and many cryptographic methods.
The key difference between these new structures and groups is that, rather than considering our set equipped with a single binary operator, we will instead be considering how the set behaves under two binary operators.
Prerequisites
This article is part of a series of math articles for zero-knowledge proof. Before reading this article, we recommend you read the first three in this series:
What is a ring?
A ring is a set $R$ equipped with two binary operators, typically called addition* $(+)$ and multiplication $(\cdot)$, that satisfy the following conditions:
- Operator 1 - Addition ($+$): First, let’s consider how the set behaves under addition. Under addition, the set $R$ must form an Abelian group. Remember the Cyfrin Is Incredibly Awesome acronym? We need those properties PLUS commutativity for it to be Abelian:
- Closure: For any $a, b \in R$, the sum $a + b$ is also in $R$.
- Associativity: For all:
- $$(a + b) + c = a + (b + c)$$.
- (Additive) Identity: There exists an element $0 \in R$ such that for all $a \in R$
- $$a + 0 = a$$.
- This means that adding 0 to any element leaves the element unchanged.
- (Additive) Inverses: For each $a \in R$, there exists an element $-a \in R$ such that
- $$a + (-a) = 0$$.
- Commutativity: For all $a, b \in R$
- $$a + b = b + a$$.
- Operator 2 - Multiplication ($\cdot$): Now, under multiplication, the set $R$ must satisfy the following properties to form a ring**:**
- Closure: For any $a, b \in R$, the product $a \cdot b$ is also in $R$.
- Associativity: For all $a, b, c \in R$:
- $$(a \cdot b) \cdot c = a \cdot (b \cdot c)$$.
- Operators 1 & 2 - distributive laws: Finally, let’s consider how the set behaves under both operators. To form a ring, multiplication must distribute over addition:
- Left distributive: When you multiply a single element by the sum of two elements, the result is the same as if you first multiply the single element by each of the two elements separately and then add those products together.
- Formally, for all $a, b, c \in R$:
- $$a \cdot (b + c) = (a \cdot b) + (a \cdot c)$$.
- Right distributive: When you multiply the sum of two elements by a single element, the result is the same as if you first multiply each of the two elements by the single element separately and then add those products together.
- Formally, for all $a, b, c \in R$:
- $$(a + b) \cdot c = (a \cdot c) + (b \cdot c)$$.
Additional notes:
- A ring does not necessarily have a multiplicative identity (i.e., an element $I$ such that $a \cdot I = a$ for all $a \in R$), but if it does, it is called a ring with unity or a unital ring.
- Multiplication in a ring is not required to be commutative. If multiplication is commutative (i.e., $a \cdot b = b \cdot a$ for all $a, b \in R$, then the ring is called a commutative ring (woooooah, no way! Sorry, British sarcasm again).
What is a field?
A field is a set that forms an Abelian group under two different binary operators. It is a specific type of ring that satisfies additional properties under the second operator.
Formally, a field is a set $F$ equipped with two binary operators, typically called addition $(+)$ and multiplication $(\cdot)$, that satisfy the following algebraic properties:
- Operator 1 - Addition ($+$): Under addition, the set $F$ with this operation forms an Abelian group:
- Closure: For any $a, b \in F$, the sum $a + b$ is also in $F$.
- Associativity: For all $a, b, c \in F$:
- $$(a + b) + c = a + (b + c)$$.
- Commutativity: For all $a, b \in F$:
- $$a + b = b + a$$.
- Identity: There exists an element $0 \in F$ such that for all $a \in F$
- $$a + 0 = a$$.
- Inverses: For each $a \in F$, there exists an element $-a \in F$ such that
- $$a + (-a) = 0$$.
- Operator 2 - Multiplication ($\cdot$): Under multiplication, the set $F \setminus \{0\}$ (the set $F$ excluding the additive identity $0$) forms an Abelian group:
- Closure: For any $a, b \in F$, the product $a \cdot b$ is also in $F$.
- Associativity: For all $a, b, c \in F$
- $$(a \cdot b) \cdot c = a \cdot (b \cdot c)$$.
- Commutativity: For all $a, b \in F$
- $$a \cdot b = b \cdot a$$.
- Multiplicative identity: There exists an element $1 \in F \setminus \{0\}$ such that for all $a \in F$:
- $$a \cdot 1 = a$$.
- Multiplicative inverses: For each $a \in F \setminus \{0\}$, there exists an element $a^{-1} \in F \setminus \{0\}$ such that:
- $$a \cdot a^{-1} = 1$$.
Remember that we can use Fermat’s Little Theorem to find the multiplicative inverse when considering the finite set of integers, excluding $0$, modulo prime $p$, denoted $\mathbb{Z_p}^*$.
- Operator 1 & 2 - distributive laws:
- Left distributive: For all $a, b, c \in F$, $( a \cdot (b + c)) = (a \cdot b) + (a \cdot c)$.
- Right distributive: For all $a, b, c \in F$, $(a + b) \cdot c = (a \cdot c) + (b \cdot c)$.
Let’s go through some examples to understand how to identify a field.
Field examples and Finite Fields
Examples of sets that form fields under addition and multiplication:
- The set of integers modulo $p$ (where $p$ is a prime number) under addition and multiplication forms a finite field (it is a field in which the set has a finite number of elements).
- While $\mathbb{F}_p$ includes zero, the multiplicative group of nonzero elements $\mathbb{F}_p^* = \{1, 2, \ldots, p-1\}$ forms a group under multiplication modulo $p$, since every nonzero element has a multiplicative inverse.
- You will frequently hear the term finite field in this series, so make sure you are comfortable with what this means!
- As you may recall, in cryptography and zero-knowledge proof protocols, we often use the set of integers modulo $p$ , where $p$ is a prime number. So now you will understand that this is because this set forms a finite field!
- The set of real numbers $\mathbb{R}$ is an infinite field under the addition and multiplication operations.
Example of a set that does not form a field under addition and multiplication:
- The set of integers modulo $n$ (where $n$ is not a prime number, e.g., $4$) under addition and multiplication is not a field.
- This is because, under multiplication, it does not form a group, as not every element has an inverse. For example, for the set of integers modulo $4$, element $2$ does not have a multiplicative inverse.
What’s next?
In the next part of the series, we'll explore cyclic groups and generator points - special elements that can create every other element in the group through repeated operations. We'll also examine the discrete logarithm problem (DLP), a computationally hard problem that provides the security backbone for elliptic curve cryptography and zero-knowledge proof systems.
Summary
This article defined two new algebraic structures called rings and fields. These structures consider sets with two binary operators, typically called addition and multiplication:
- Ring: A set $R$ that:
- Forms an Abelian group under addition
- Is closed and associative under multiplication
- Has multiplication that distributes over addition (both left and right)
- Field: a set $F$ that:
- Forms an Abelian group under addition
- Forms an Abelian group under multiplication
- Has multiplication that distributes over addition (both left and right)
Footnote
*Why do we refer to the two operators as ”typically” called multiplication and addition?
The terms "addition" and "multiplication" in fields are abstractions that refer to operations that follow certain axioms (commutativity, associativity, distributivity, etc.). We use these familiar names because:
- The operations behave mathematically like addition and multiplication and follow the same rules.
- In simple cases like the rational numbers, they actually are the familiar operations.
References
💡 Prefer to learn via video? Check out this YouTube video instead!
