A lot of what you do as a Math major is Algebra, but not the kind most people are familiar with! I’ve found myself having this exact encounter numerous times:
Friend/Family: “So, what are you studying in school?”
Me: “Oh, Algebra!”
Friend/Family: “I sucked at Algebra in high school”
Me: “Well, it’s not really the same kind of Algebra”
Me: … *tries to beam this gif into their prefrontal cortex* …
The kind of Algebra I do is called Abstract Algebra – a branch of mathematics that generalizes arithmetic by focusing on the underlying properties of sets and operations, rather than specific numerical calculations.
I find a lot of beauty in Abstract Algebra, and I think more people should know about it, so I’m going to try and do my part. Fair warning–this is math!–so, we will be doing a bit of math. However, I truly think it will be more intuitive than you might expect! We won’t be solving any equations like the Algebra in high school. But we’ll be learning some new notation, and most importantly, a new way of viewing the world. Henceforth I will refer to Abstract Algebra as simply “Algebra”.
[!cite] Aside Again, a lot (or ~most) of the mathematics that I study in college does not concern itself with numerical computation at all! Pure Mathematics is the study of mathematical structures for their own sake, including writing proofs and theorems about these structures as opposed to applying them to solve real-world problems. Though there is frequently important results in pure mathematics that have applications to the real world (Abstract Algebra is a prime example of this).
To this end, we need to do a small Pure Math lesson before we can get to the good stuff. There a few prerequisites that we need to cover before we can truly understand and appreciate Algebra. The first building block we’ll need is the concept of a set and the theory of sets.
Set Theory
Sets are one of the most fundamental building blocks in mathematics. Set Theory is the study of sets of objects, and the relationships between them. For example, $$ \{1,2,3\} $$ is the set of the numbers $1$, $2$, and $3$. The curly braces $\{\}$ are used to denote a set, and the elements of the set are listed inside, separated by commas. And while we did put numbers in this set, we could’ve put anything we wanted, like symbols: $$ \{\lambda,\star,\square,\Sigma\} $$
or, the set of all of Pluto’s moons: $$ \{\text{Charon},\text{Nix},\text{Hydra},\text{Kerberos},\text{Styx}\} $$
The Naturals and The Integers
While we could sit around and make any set we wish, there are a handful of sets that are fundamental, already familiar, and extremely useful.
The natural numbers are the set of all positive whole numbers–the “counting numbers” that we use to count objects: $0,1,2,3,\ldots$ and so on.
The integers are the set of all whole numbers, both positive and negative, and including zero: $\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots$ and so on.
These sets are so fundamental that they have their own special symbols: $$ \begin{aligned} \mathbb N&=\{0,1,2,3,\ldots\} \\ \mathbb Z&=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\} \end{aligned} $$
[!warning] On Notation There is no consensus on whether or not $0$ is included in the natural numbers–it’s like whether you think Pluto is a planet or not. I think those in the camp of planethood would say that $0$ is a natural number, and so I include it in $\mathbb N$. Sometimes this will be made explicit by writing $\mathbb N_0$. If $0$ is not to be included then you may see it written as $\mathbb N_1,\mathbb N^+$, or $\mathbb N^*$. However, I will strictly be using $\mathbb N$ generically, and you can just assume that it includes $0$ (I’m a planethood for Pluto kinda guy).
Important Concepts and Notation
Set theory is a load-bearing foundation for all of mathematics, so it would be good to touch on some stuff before going on to the main event. We’ll need these tools later.
The simplest is the idea of an element being in a set. We write $x\in S$ to mean: “$x$ is an element of the set $S$”, or more simply, “$x$ is in the set $S$”. This is referred to as set membership. Often times, we want to talk about the size of a set–how many elements are in the set–which is called the size/order/cardinality of the set. We denote this as $|S|$.
As pure mathematicians go, we must prove things about the systems we study. In this vein we often like to make provable claims about all elements of a set. This is really just saying, “for all $x$ in the set $S$, some property $P$ holds”. To express these ideas, we use $\forall x$ to mean “for all $x$”, and $P(x)$ to mean “the property $P$ holds for $x$”. So, putting it all together, we can write: $$ \forall x\in S, P(x) $$
Additionally, if $P(x)$ does not hold for $x$, we can write $\neg P(x)$, which is read as “not $P(x)$”.
The final two symbols we’ll need are $\exists$ and $\mid$. The symbol $\exists$ means “there exists” – so $\exists x\in S$ means “there exists an element $x$ in the set $S$”. This symbol is then often combined with $\mid$ in the following manner:
$$ \exists x\in S\mid P(x), $$ which is to be read as “there exists an element $x$ in $S$ such that the property $P$ holds for $x$”.
Alright, with all the basic set notation out of the way, we can move up the abstraction ladder and get to the Algebra part of Abstract Algebra. Here’s a quick summary of the notation we just covered:
| Symbol | Meaning | Example |
|---|---|---|
| $\in$ | “in” | $3\in\mathbb Z$ |
| $\mid S\mid$ | “the size/order/cardinality of the set $S$ | If $S={1,2,3}$, then $\mid S\mid=3$ |
| $\forall x$ | “for all $x$” | $\forall x\in\mathbb Z, x+0=x$ |
| $P(x)$ | “the property $P$ holds for $x$” | If $P(x)$ is “is even”, then $P(2)$ is true and $P(3)$ is false |
| $\neg P(x)$ | “not $P(x)$” | If $P(x)$ is “is even”, then $\neg P(2)$ is false and $\neg P(3)$ is true |
| $\exists x$ | “there exists an element $x$” | $\exists x\in\mathbb Z\mid P(x)$ is true, since $2$ is an element of $\mathbb Z$ such that $P(2)$ is true |
Groups
A group $(G,\circ)$ is a set $G$ along with a binary operator $\circ: G\times G\rightarrow G$. A group satisfies the following properties:
- Associativity: For all $a,b,c\in G$, $$ (a \circ b) \circ c = a \circ (b \circ c) $$
- Identity Element: There exists an element $e\in G$ such that for all elements $a\in G$, $$ e\circ a=a\circ e=a $$
- Inverse Element: For every $a\in G$, there exists an element $a^{-1}\in G$ such that $$ a\circ a^{-1}=a^{-1}\circ a=e $$
- (Optional) Commutativity: For all $a,b\in G$, $$ a\circ b=b\circ a $$
Every group satisfies the first three properties, and if it also satisfies property 4, then we call it an Abelian Group. Out of these simple rules, an enormous world of cryptography falls out.
Familiar Examples
To help build intuition, let’s look at a group that you’ve been working with since you were a kid, without even knowing it: the integers under addition.
We denote the set of integers as $\mathbb Z$, and just as a refresher, this is the set of all whole numbers, both positive and negative, including zero: $$ \mathbb Z={\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots} $$
Recall that a group is made up of both an underlying set and a binary operator. When we say “the integers form a group under addition”, we are saying that $(\mathbb Z,+)$ is a group, where the binary operator is just plain old addition. We can prove that $(\mathbb Z,+)$ is indeed a group by proving that it satisfies the properties of a group:
[!hint] Proof. $(\mathbb Z,+)$ is a group
Associativity: $\forall a,b,c\in\mathbb Z$, $$ (a+b)+c=a+(b+c) $$ Associativity of addition on $\mathbb Z$ is inherited from the Peano Axioms. It is proven by induction on $\mathbb N$ and then extended to $\mathbb Z$ via the construction of the integers as equivalence classes of pairs of natural numbers. This is outside the scope of this article, but I hope by just looking at the above equation, you can reasonably accept that addition is associative through experience working on $\mathbb Z$.
Identity Element: The identity element for integer addition is $0$, since $\forall a\in\mathbb Z$, $$ a+0=0+a=a $$
Inverse Element: The inverse element for any integer $a\in\mathbb Z$ is $-a$, since $$ a+(-a)=(-a)+a=0 $$
Thus we have proved that the integers $\mathbb Z$ form a group under addition. Since addition is also commutative – it’s clear that $a+b=b+a$ for any integers $a$ and $b$ – we also say that $(\mathbb Z,+)$ is an Abelian group. Most groups that we encounter in cryptography are Abelian, so this distinction is important to keep in mind.
Finite Groups and Order
A group is called finite if it has a finite number of elements. The number of elements in a group is called the order of the group. For a finite group $(G,\circ)$, we denote the order of the group as $|G|$.
Every element $a$ in a finite group also has an individual order, which is defined as the smallest positive integer $n$ such that $a^n=e$. Now, this notation can be a little confusing at first. It looks like exponentiation, but it’s actually just a shorthand for repeated application of the group operation. So when you see $a^n$, keep this in mind:
$$ a^n=\underbrace{a\circ a\ldots\circ a}_{n\text{ times}} $$
This element-specific order always exists in a finite group. If you keep computing $a,a^2,a^3,\ldots$, you will eventually cycle back to the identity element $e$, because there are only finitely many elements to visit. So, again, the order of an element $a$ is the smallest $n$ such that when you repeatedly apply the group operation to $a$ $n$ times, you return back to the identity element.
Before we move on from the concept of order, we need to introduce a theorem that will be powerful for us later: Lagrange’s Theorem.
Lagrange’s Theorem
Let $(G,\circ)$ be a finite group. The order of any element $a\in G$ divides the order of the group $|G|$.
[!example] If $|G|=12$, then the order of any element in $G$ must be some factor of $12$: $1,2,3,4,6,$ or $12$.
Modular Arithmetic and The Integers Modulo $n$
You should be familiar with the concept of modular arithmetic from your experience with clocks. Clocks are modulo $12$, because they “wrap” around after $12$ hours. For example, if it’s $10$ o’clock now, and you have an exam in $5$ hours, you don’t say that your exam is at $15$ o’clock, you say that your exam is at $3$ o’clock.
The integers modulo $n$ can be viewed as a generalization of this concept. The set of integers modulo $n$ is denoted $\mathbb Z/n\mathbb Z$, and it consists of the integers from $0$ to $n-1$.
$$ \mathbb Z/n\mathbb Z={0,1,2,\ldots,n-1} $$
This set forms a group under addition modulo $n$, which we define as follows: for any two elements $a,b\in\mathbb Z/n\mathbb Z$, we define their sum as:
$$ a+b\pmod n $$
So, from our clock example, we take $n=12$, and we have: $$ \begin{align} 10+5\pmod{12}&=15\pmod{12}\notag\ &=3\notag \end{align} $$
Something important to note here is that the value of $n$ itself is not contained in the set $\mathbb Z/n\mathbb Z$. This is because, when operating under modulo $n$, $n$ is equivalent to $0$. In other words, $n\pmod n=0$.
It might not yet be clear why we care about modular arithmetic and the integers modulo $n$. But let us now build upon this idea and see how it’s relevant to cryptography.
Cyclic Groups and Generators
A group $(G,\circ)$ is said to be cyclic if there exists an element $g\in G$ such that every element in $G$ can be written as $g^n$ for some integer $n$. Thought about another way, the group can be generated by repeatedly applying the operation to a single element $g$, which we call a generator of the group.
[!example] Consider again, $\mathbb Z/n\mathbb Z$ under modular $n$ addition. This group is cyclic, and has a generator $1$, since every element in $\mathbb Z/n\mathbb Z$ can be written as $1+1+\ldots+1$ ($n$ times) modulo $n$. For example, in $\mathbb Z/5\mathbb Z$, we have: $$ \begin{align} 1&=1\notag\ 2&=1+1\notag\ 3&=1+1+1\notag\ 4&=1+1+1+1\notag\ 0&=1+1+1+1+1\notag \end{align} $$
[[dlp|The Discrete Logarithm Problem]]