Group theory forms the mathematical backbone of modern cryptography and zero-knowledge systems. Think of it as learning a specialized language for cryptography.
Cryptographers use terms like "cyclic additive groups" and "generators" because these precise mathematical structures enable cryptographic algorithms and proofs to be created.
Without understanding groups, advanced cryptographic concepts remain inaccessible in the same way you must master arithmetic before learning calculus.
Ultimately, you will learn the definition of a group. For this, you must first learn:
By the end of this article, you'll understand the group structures that underpin zero-knowledge proofs and be able to understand future cryptographic concepts.
This is the third in a series of articles. It is recommended that you read the first two, which cover modular arithmetic and set theory, before reading this one:
A group is a set equipped with a binary operator that satisfies certain properties. To understand what this sentence means, we must first define the term “binary operator”.
The term binary operator sounds scary, but it really isn’t.
A binary operator is a type of operator that takes two operands (i.e., two elements from a set) to perform a computation or operation. A binary operator operates on two elements $a$ and $b$ to produce a result:
$$a \cdot b = c$$
Where$\cdot$ represents any binary operator. Confusingly, this symbol can also be used to denote multiplication in arithmetic in some instances (and we will be using $\cdot$ to denote multiplication in future articles).
Common examples of binary operators include:
For example, in the expression $3 + 4$, the $+$ operator is a binary operator that takes the two operands, $3$ and $4$, and performs addition to output 7.
A group is a set of elements $G$ equipped with a binary operator $\cdot$ that satisfies certain properties.
When we say “equipped with a binary operator” we mean that the only operator that can be considered in the group is the one specified. For example, let’s say we define a group as the set of integers modulo $p$ equipped with the addition operator. All other operators (e.g., multiplication, etc) do not exist in this context.
Let’s go through those “certain properties” our set $G$ plus binary operator $\cdot$ must satisfy:
The set $G$ must be "closed" under the operation, meaning that when you apply the operation to any two elements from the set, the result must also be an element of the set.
Formally, if $a$ and $b$ are elements in the set, then $a \cdot b$ must also be in the set:
$$a \cdot b = c$$
Where $c \in G$
For example, consider the set of integers under the addition operator:
$$5 + 9 = 14$$
Since $14$ is also in the set of integers, the addition operator is closed.
Or for the set of integers under multiplication:
$$5 \times 9 = 45$$
Since $45$ is also in the set of integers, the multiplication operator is closed.
There must be an identity element $I$ in the set such that for every element $a$ in the set, when operated on with the identity element, the output is the element itself:
$$a \cdot I = I \cdot a = a$$
Additionally, the identity element must be unique, meaning that only one identity element exists for each set.
Again, consider integers under addition. Here, the identity element is $0$ since
$$a + 0 = a$$
For integers under multiplication, for an integer $a$ the identity element is $1$ since:
$$a \times 1 = a$$
Every element must have an inverse. For each element $a$ in the set, there must be an element $a_{\text{inv}}$ such that when it is operated on with the element, the output is the identity element $I$:
$$a \cdot a_{\text{inv}} = a_{\text{inv}} \cdot a = I$$
For integers under addition, the inverse is the negative of the element (or the element multiplied by $-1$), e.g., for the integer $5$:
$$-5 + 5 = 0$$
However, if the set is restricted to positive integers only, not all elements have inverses within this set (e.g., there is no positive integer $b$ such that $5 + b = 0$). Therefore, the set of positive integers under addition is not a group.
For integers under multiplication, the inverse is the reciprocal of $a$. E.g., for the integer $5$:
$$5 \times \frac{1}{5} = 1$$
However, $\frac{1}{5}$ is not in the set of integers; therefore, the set of integers under multiplication is not a group.
The operation must be associative. This means that the position of parentheses does not make a difference to the outcome of the calculation. For any three elements $a$, $b$, and $c$ in the set, associativity can be defined mathematically as:
$$(a \cdot b) \cdot c = a \cdot (b \cdot c)$$
For example, the set of integers under addition:
$$(1 + 2) + 3 = 1 + (2 + 3) = 6$$
And for the set of integers under multiplication:
$$(1 \times 2) \times 3 = 1 \times (2 \times 3) = 6$$
Since all the properties are satisfied for the set of integers under addition, this set forms a group. However, for the set of positive integers under addition, since not all elements have an inverse in the set, it does not form a group.
To remember the properties of a group, use the following acronym:
Cyfrin Is Incredibly Awesome (closed, identity, inverse, associative)
Inverses are intuitive when working with “regular math.” However, they work a little differently in modular arithmetic.
Remember that, for each element $a$ in the set, the inverse $a_{\text{inv}}$ is such that:
$$a \cdot a_{\text{inv}} = a_{\text{inv}} \cdot a \equiv I \pmod{n}$$
Note that we have added $\mod{n}$ to the equation since we are now working with modular arithmetic.
Finding the additive inverse of an element $a$ in the finite set of integers modulo $n$, denoted $\mathbb{Z}n$, means finding an element $a{inv}$ such that when it is applied to the element $a$ with the binary operator $+$, it yields the identity element $0$:
$$a + a_{inv} \equiv 0 \pmod{n}$$
To find the additive inverse:
Example: Modulo $7$
Find the additive inverse of $3$ in $\mathbb{Z}_7$:
General rule
For any $a \in \mathbb{Z}_n$ ($\in$ means any element $a$ in the set of integers modulo $n$), the additive inverse is:
$$a_{inv} \equiv n - a \pmod{n} \quad \text{if } a \neq 0, \text{ and } b = 0 \text{ if } a = 0.$$
This works because adding $n - a$ to $a$ gives:
$$a + (n - a) = n \equiv 0 \pmod{n}$$
Let’s find the multiplicative inverse for the finite set of integers modulo $p$. The definition of a multiplicative inverse in modular arithmetic is:
$$a \times a_{inv} \equiv 1 \pmod{p}$$
Where the operator is multiplication, denoted by $\times$ and the identity element is $1$.
To find the multiplicative Inverse for a finite set, specifically integers modulo $p$, you must first understand Fermat’s Little Theorem:
Fermat's Little Theorem states that if and only if $p$ is a prime number and $a$ is an integer not divisible by $p$ (i.e., $a \neq 0$ modulo $p$), then:
$$a^{p-1} \equiv 1 \pmod{p}$$
Meaning, raising $a$ to the power of $p-1$ gives a result that is congruent to 1 modulo $p$.
Finding the multiplicative inverse
To find the multiplicative inverse of $a$ modulo $p$, we need to find an integer $a_{inv}$ such that:
$$a \cdot a_{inv} \equiv 1 \pmod{p}$$
Since $a_{inv} = a^{-1}$ in “basic” arithmetic:
$$a \cdot a^{-1} \equiv 1 \pmod{p}$$
$a^{-1}$ is the multiplicative inverse we are trying to find, and Fermat’s Little Theorem is used to find it. Fermat’s Little Theorem states that, if $a \neq 0 \pmod{p}$, then:
$$a^{p-1} \equiv 1 \pmod{p}$$
Then, multiply both sides of this equation by $a^{-1}$ (the hypothetical inverse we are trying to find):
$$a^{p-1} \cdot a^{-1} \equiv 1 \cdot a^{-1} \pmod{p}$$
$$a^{p-2} \equiv a^{-1} \pmod{p}$$
Thus, $a^{p-2}$ is the multiplicative inverse of $a$ modulo $p$. In other words:
$$a_{inv} = a^{-1} \equiv a^{p-2} \pmod{p}$$
Therefore, a multiplicative inverse exists for an integer $a$ modulo a prime $p$ as long as $a$ is not divisible by $p$. Meaning, if p is prime and $a \neq 0 \pmod {p}$, since $0$ does not have an inverse, then there exists an integer $a_{inv}$ such that $a \cdot a_{inv} \equiv 1 \pmod{p}$.
Fermat’s Little Theorem is crucial in understanding why the set of integers modulo a prime $p$, excluding zero, is often chosen in zero-knowledge proofs and cryptography, for example, in Groth16.
This set, denoted by $\mathbb{Z}_p^*$, consists of all non-zero elements modulo $p$ and forms a multiplicative group where every element has an inverse.
In the modular arithmetic article, we mentioned that division does not exist in modular arithmetic in the same way it does in “basic” arithmetic. We can, however, construct a division operation using multiplicative inverses.
Division operation: In modular arithmetic, division—or rather inverse multiplication*,* can be constructed by multiplying by the inverse of the denominator. For example:
$$\frac{a}{b} \rightarrow (a \cdot b_{inv}) \mod p$$
Division example: If $p = 7$ and $a = 3$, then according to Fermat's Little Theorem:
$$3^{7-1} \equiv 3^6 \equiv 1 \pmod{7}$$
To find the inverse, calculate $3^{7-2}$:
$$3^{5} \equiv 243 \equiv 5 \pmod{7}$$
Thus, the inverse of $3$ modulo $7$ is $5$ because:
$$3 \cdot 5 \equiv 15 \equiv 1 \pmod{7}$$
An Abelian group is a set and a binary operator with the four properties of groups described above, PLUS the operator MUST be commutative.
Commutativity: The order of the operands does not matter when operating.
$$a \cdot b = b \cdot a$$
Abelian groups are just another way we will describe sets equipped with binary operators later in the series, so you should get used to understanding what this means: that the operator is commutative!
To remember the definition of an Abelian group, here’s another cheeky mnemonic:
Clearly: Commutativity
Cyfrin: Closure
Is: Identity element
Incredibly: Inverse elements
Awesome: Associativity
Let’s now go through some examples to get used to figuring out if a set plus a certain operator combination is a group (and whether said group is Abelian).
We have 4 properties to check for a group plus one more to determine if it is an Abelian group:
Is it associative?
Yes! The addition of integers is associative:
$$(a + b) + c = a + (b + c)$$
Is it closed?
Yes! For any integers $a$ and $b$, $a + b$ is also an integer.
Is there an identity element?
Yes! The additive identity is $0$, since:
$$a + 0 = a$$
Do all the elements have an inverse?
Yes! The additive inverse of an integer $a$ is $-a$, and:
$$a + (-a) = 0$$
And to check if it’s an Abelian group, Is it commutative?
Yes, addition is commutative:
$$a + b = b + a$$
Since all properties are satisfied, the set of integers under addition is an Abelian group!
Let’s use integers modulo $7$ as an example: $\{0, 1, 2, 3, 4, 5, 6\}$.
Is it associative?
Yes! Let’s check this:
$$(((3 + 5) \mod 7) + 6) \mod 7 = 0$$
$$(3 + ((5 + 6) \mod 7)) \mod 7 = 0$$
We could go further and write a mathematical proof demonstrating this holds true in all cases but it’s out of scope for this article.
Is it closed?
Yes! Since we use modulus $7$, the result of any addition is always between $0$ and $6$, so it remains in the set:
$$(1 + 5) \mod 7 = 6$$
Is there an identity element?
Yes! The additive identity is $0$.
Do all elements have an inverse?
Yes! To find the additive inverse of $a$ modulo $p$, we need an element $a_{\text{inv}}$ such that:
$$a + a_{\text{inv}} \equiv 0 \pmod{p}$$
For $p = 7$, the inverse of $4$ is $3$ because:
$$4 + 3 \equiv 0 \pmod{7}$$
Generally, the inverse of $a$ is $p - a$.
Is it Abelian?
Yes, addition modulo $p$ is commutative:
$$a + b \equiv b + a \pmod{p}$$
The set of integers modulo $p$ under addition is an Abelian group!
Let’s take the set of integers modulo $6$: $\{0, 1, 2, 3, 4, 5\}$.
Is it associative?
Yes! Let’s check this:
$$(((3 \cdot 4) \mod 6) \cdot 2) \mod 6 = 0$$
$$(3 \cdot ((4 \cdot 2) \mod 6)) \mod 6 = 0$$
Is it closed?
Yes! Since the operation is modulus $6$, the result of any multiplication is always within the set:
$$(2 \cdot 3) \mod 6 = 0$$
Is there an identity element?
Yes! Under multiplication, the identity element is $1$:
$$(3 \cdot 1) \mod 6 = 3$$
Do all elements have an inverse?
Finding the inverse in modular arithmetic is more complex. For element $a$, the multiplicative inverse $a_{\text{inv}}$ is such that:
$$(a \cdot a_{\text{inv}}) \mod n = 1$$
For example, for $n = 6$:
Thus, not all elements of this set have an inverse and therefore it is not a group.
Recall that, if $n$ is prime, every element (except $0$) has an inverse due to Fermat’s Little Theorem. Meaning, for any non-zero integer $a$ modulo prime $p$, a multiplicative inverse exists. The theorem provides a practical way to compute this inverse as $a^{p-2}$, ensuring the structure of $(\mathbb{Z}_p, \times)$ forms a group.
There's no need to check if this group is Abelian since it is not a group.
We'll demonstrate that if $p$ is a prime number, then the set $\{1, 2, \ldots, p-1\}$ under multiplication is a group. Note, in this example we've chosen to remove $0$ from the set because we can define the set however we choose and we want to define the set where no elements are equal to $0$. Specifically, because $0$ does not have an inverse and therefore the set doesn’t form a group under the multiplication operator.
Is it associative?
Yes! Multiplication is associative:
$$((a \cdot b) \cdot c) = (a \cdot (b \cdot c))$$
Is it closed?
Yes! Multiplying any two non-zero elements modulo $p$ results in another non-zero element modulo $p$.
Is there an identity element?
Yes! The multiplicative identity is $1$:
$$(a \cdot 1) \mod p = a$$
Do all elements have an inverse?
Yes! For a prime $p$, every non-zero element has an inverse:
$$(a \cdot a_{\text{inv}}) \equiv 1 \pmod{p}$$
For instance, the inverse of $4$ modulo $7$ is $2$ because:
$$(4 \cdot 2) \mod 7 = 1$$
The set of integers $a \neq 0$ modulo $p$ under multiplication is a group!
Is it Abelian?
Yes, modular multiplication modulo $p$ is commutative:
$$a\cdot b \equiv b \cdot a \pmod{p}$$
The set of integers modulo $p$ under multiplication is an Abelian group!
Remember from before, the finite set of integers modulo prime $p$ were often used in cryptography, this is because they form an Abelian group under both addition and multiplication!
Before we move on, let’s introduce the concept of scalar multiplication in an additive group and scalar exponentiation in a multiplicative group. At first glance, it might seem counterintuitive that we can do ”multiplication” in an additive group when earlier I said the only operation we could perform is addition (and likewise for ”exponentiation” in a multiplicative group) but all is not as it seems…
Scalar multiplication in an additive group means adding a group element to itself multiple times. If $G$ is a group element and $k$ is an integer (denoted a “scalar”), then:
$$k \cdot G = \underbrace{G + G + \cdots + G}_{k \text{ times}}$$
For example, $G = 3$ and the group is the integers under addition, then:
$$4 \cdot G = 3 + 3 + 3 + 3 = 12$$
Scalar multiplication in an additive group is just repeated addition.
Exponentiation in a multiplicative group means multiplying a group element by itself multiple times. If $g$ is a group element and $k$ is a scalar, then:
$$g^k = \underbrace{g \cdot g \cdot \cdots \cdot g}_{k \text{ times}}$$
For example, in the multiplicative group of integers modulo 7, if \( g = 3 \), then:
$$3^4 \bmod 7 = 81 \bmod 7 = 4$$
Scalar exponentiation in a multiplicative group is just repeated multiplication.
Note also that when working in finite sets of integers modulo $p$, the scalar $k$ does not have to be in the set.
These two operations, scalar multiplication and exponentiation, frequently appear in cryptography. In particular, they play a key role in a special class of groups called cyclic groups, which we will explore in a future article.
In the next part of the series, we'll explore rings and fields — other types of mathematical structures that help us build the foundation for cryptographic systems like finite fields, elliptic curves, and polynomial commitments. Understanding these structures is necessary to understand how arithmetic circuits, zk-SNARKs, and other zero-knowledge protocols work under the hood.
In this article, we've covered:
These mathematical structures aren't just abstract concepts to understand. They are the essential, necessary building blocks that enable the construction of real-world cryptographic systems and applications. Applications that protect information and prove knowledge without revealing secrets. In the next article, we'll build on these group theory foundations to explore rings and fields.
Prefer to learn via video? Check out this YouTube video on groups:
And this one on Fermat’s little theorem:
Resources:
