This article is the first of a series explaining the mathematical prerequisites needed to understand cryptography in blockchains and zero-knowledge systems like Groth16 and PLONK.
Cryptography relies heavily on concepts like finite fields, modular arithmetic, and group theory. Learning these fundamentals will equip you to understand how zero-knowledge cryptographic systems actually work.
For example, consider this excerpt from the Groth16 paper:
“Let G1 and G2 be two groups of prime order q, and let G3 be a group of prime order q. The system uses homomorphisms between these groups, with the main idea being to construct a proof that a committed value in one group corresponds to another value in a second group, without revealing the values themselves.”
To make sense of this, we need to understand groups, generator points, homomorphisms, and finite sets (which involve modular arithmetic).
Think of this series as a guide to the "math language" of cryptography, helping you understand these terms when you encounter them in research papers or codebases.
This article series is not meant as a stand-alone, conclusive resource for studying the math topics outlined. Rather, it is an overview to share the high-level concepts required for understanding zero-knowledge proofs and cryptography. For a more detailed breakdown, links can be found in the references section at the end of each article. Also, note that mathematical proofs of the theorems and definitions have been omitted for simplicity. If you are interested, I encourage you to use the linked resources or your favorite AI assistant to understand how to derive the concepts from first principles.
With that said, let’s get into it!
The modulus is a binary operator representing the remainder after division. A binary operator takes two operands (inputs) and performs an operation on them (an example operation is addition, but don’t worry too much about this yet, it will be covered again when we formally introduce binary operators in a different article on group theory).
The following symbol is used to denote the modulus operation:
$$\mod n$$
Where $n$ is an integer.
Note that, in programming, the % symbol is used instead.
Let’s go through an example,
$$7\pmod 5 :$$
$7 \div 5 = 1$ with a remainder of $2$. Therefore, $7\mod 5 = 2$
Here are some more examples:
Let’s go through an example with negative integers, which can be a bit trickier.
Consider:
$$−7\pmod5$$
Step 1: Divide and find the remainder
If we divide $−7$ by $5$, we get:
$$-7 \div 5 = -1 \text{ with a remainder of } -2$$
But $−2$ is not a valid remainder for $\pmod 5$, because remainders are typically taken to be in the set:
$$\{0, 1, 2, 3, 4\}$$
Step 2: Adjust the remainder
To bring the remainder into the correct range, we add 5:
$$−2+5=3$$
So:
$$−7\pmod5=3$$
Another way to think about modular arithmetic is by rewriting the number in the form:
$$−7=(−2×5)+3$$
This shows clearly that the remainder is $3$.
Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value—the modulus. The term "modular" refers to the fact that all arithmetic operations are performed with respect to a modulus.
Modular arithmetic is used frequently in daily life, when telling the time on an analog clock! There is no “100 o’clock” because the hours wrap around. Each time the hour hand reaches 12, the time reference restarts (assuming you’re not using a 24-hour clock).
.png)
The set of integers modulo some integer $n$ is denoted as $\mathbb{Z}_n$ and contains $n$ elements, represented as:
$$\{0, 1, 2, \ldots, n-1\}$$
After performing an operation, such as addition, the result is taken modulo some number $n$:
Where $n$ is the modulus, the result is taken modulo $n$. Meaning, the result of the initial operation is divided by $n$. This always results in a value between $0$ and $n−1$. The "wrap-around" happens naturally due to this modulo operation!
In the context of cryptography and zero-knowledge proofs, the modulus $n$ is often chosen as a prime number and therefore denoted as $p$. The reason for using a prime modulus will become clear as this series progresses.
Technically speaking, division doesn't exist in modular arithmetic in the usual sense. However, a "division-like" operation can be defined using the multiplicative inverse, which will be explained in a later article on group theory.
Two integers $a$ and $b$ are said to be congruent modulo $n$ if they have the same remainder when divided by $n$. This is written as:
$$a \equiv b \pmod{n}$$
$a$ and $b$ are congruent modulo $n$ if the difference between them is a multiple of $n$.
The symbol $\equiv$ is used to denote congruence (this symbol is also used for equivalence).
Consider $n = 5$ and the integers $a = 17$ and $b = 2$. In this example, $17$ is congruent to $2$ modulo $5$ because both $17$ and $2$ leave a remainder of $2$ when divided by $5$:
$$17 \div 5 = 3 \text{ remainder } 2$$
$$2 \div 5 = 0 \text{ remainder } 2$$
Thus,
$$17 \equiv 2 \pmod{5}$$
Extending this,
$$17 \equiv 12 \equiv 7 \equiv 2 \pmod{5}$$
Etc…
Understanding congruence is more than just useful for recognizing when two numbers leave the same remainder after dividing by a given modulus. The concept is necessary when defining equivalence classes in modular arithmetic, which are crucial for understanding cryptography and many other areas of mathematics.
An equivalence class, under a modulus $n$, groups all integers that are congruent to each other modulo $n$.
Two integers $a$ and $b$ are in the same equivalence class modulo $n$ if their difference ($a−b$) is divisible by $n$, i.e., $a \equiv b \pmod{n}$.
For example, with a modulus of $5$, the integers $2$, $7$, $12$, and $-3$ all belong to the same equivalence class because they all leave a remainder of $2$ when divided by $5$.
We can write this as:
$$[2]_5 = \{ \dots, -8, -3, 2, 7, 12, 17, \dots \}$$
Where the curly brace notation informally represents a collection of elements known as a set (sets will be formally introduced in our next article on set theory).
Each equivalence class corresponds to one of the possible remainders when dividing by $n$. In this case, the equivalence class of $2$ modulo $5$ includes all integers of the form $5k + 2$, where $k$ is any integer.
The collection of all such equivalence classes, $\{ [0]_n, [1]_n, \dots, [n-1]_n \}$, forms what mathematicians call a residue system modulo $n$ or quotient set.
In the next part of the series, we’ll look at set theory and how modular arithmetic fits into these algebraic structures, especially finite fields, which are central to elliptic curve cryptography and ZK proofs.
a % n
Prefer to learn via video? Check out this YouTube video instead!
Other resources:
