So you've got the “natural numbers”, $\mathbb{N}=\left\{0, 1, 2, \dots\right\}$. Or the “counting numbers”, or whatever you want to call them.

Addition works, and multiplication works. But subtraction is broken, because there isn't any natural number equal to $2-3$.

We might think about fixing subtraction, and one way of doing this is by moving to the integers, which allows negative numbers: $\mathbb{Z}=\left\{\dots, -2, -1, 0, 1, 2, \dots\right\}$.

But that still leaves division broken—there isn't any integer equal to $3 \div 4$!

One path forward is to move over to the rational numbers: $\mathbb{Q}=\text{“Proper Fractions”}$. This fixes division and subtraction at the same time. But… this path forward locks us into an infinitely large set. Sometimes (especially in cryptography) it's useful to have a smaller set of numbers that you can actually do ALL the math on.

The official word for “a set of numbers you can do all the math on” is a field. For example, $\mathbb{Q}$ is a field. But (obviously) there are infinitely many fractions, so it's an infinite field. Today you're going to learn about finite fields—which are exactly what they say on the tin. They're sometimes called “Galois fields” (gal'waah fields). They're used in almost all cryptographic algorithms. (They probably have other uses, too. [TODO look this up])

However, building these is a bit complicated. I'll need to explain 3 ideas first.

Idea #1: Modular arithmetic: $\mathbb{Z}_n$

One popular starting block for thinking about smaller universes of numbers is modular arithmetic. It starts out just like the natural numbers, but when you're about to reach the limit—the “modulus”—the numbers loop back around to 0. Also, if you try to go back below 0, you get sent up to the highest number. This gives you a miniature “toy version” of the integers that you can do math on without having to worry about looking infinity in the eye! (The way that galaxy-brained mathematicians think of this is “the quotient set of the integers, using the remainder of division by the modulus as the equivalence operator”—but you absolutely don't need to learn about that to get a basic understanding of how modular arithmetic works.)

Now, no matter what modulus you pick (as long as it's an integer $\ge 2$), addition works great, and multiplication at least kinda works. (Subtraction works perfectly, too; but I'll leave that as an exercise for the reader, since it doesn't matter for what we're doing today.)

For example, here's the integers modulo 8, which I'll write as $\textcolor{indigo}{\mathbb{Z}_8}$ (colored indigo so you can tell the modular integers from this “miniature universe” apart from regular integers):

Addition in $\textcolor{indigo}{\mathbb{Z}_8}$

Notice that (for example) $\textcolor{indigo}{6} + \textcolor{indigo}{2} = \textcolor{indigo}{0}$, because $6 + 2 = 8$, which wraps back around to $8-8 = \textcolor{indigo}{0}$!

Multiplication in $\textcolor{indigo}{\mathbb{Z}_8}$

Again using the “wrap-around arithmetic”, notice that $\textcolor{indigo}{3} \times \textcolor{indigo}{5} = \textcolor{indigo}{7}$, because $3 \times 5 = 15$, which wraps back around to $15-8 = \textcolor{indigo}{7}$.

However, if you look carefully, you'll also see that $\textcolor{indigo}{4} \times \textcolor{indigo}{6} = \textcolor{indigo}{0}$—that is, two things, neither of which is $\textcolor{indigo}{0}$, multiply to produce $\textcolor{indigo}{0}$! This is technically "allowed", but is very cringe because it flies in the face of common sense, which dictates “If a×b is zero, then either a or b must have been zero!”

In fact, this violation of common sense is so cringe that Nature's God will punish you for it by punching a bunch of holes in your division tables (which ruins them):

"Division" in $\textcolor{indigo}{\mathbb{Z}_8}$

Joking aside, the technical reason the division table is ruined is that $\textcolor{indigo}{2}$, $\textcolor{indigo}{4}$, and $\textcolor{indigo}{6}$ don't have any multiplicative inverse in $\textcolor{indigo}{\mathbb{Z}_8}$—that is, there isn't any solution to “$\textcolor{indigo}{2} \times \textcolor{indigo}{\text{?}} = \textcolor{indigo}{1}$”*. Because of that, we say that division just isn't defined on $\textcolor{indigo}{\mathbb{Z}_8}$.

(*Yes, you guessed right: “$\textcolor{indigo}{4} \times \textcolor{indigo}{\text{?}} = \textcolor{indigo}{1}$” and “$\textcolor{indigo}{6} \times \textcolor{indigo}{\text{?}} = \textcolor{indigo}{1}$” also have no solution. You can double-check this yourself by looking back at the multiplication table and noticing there isn't any $\textcolor{indigo}{1}$ to be found in the $\textcolor{indigo}{2}$, $\textcolor{indigo}{4}$, or $\textcolor{indigo}{6}$ columns!)

Now, you might ask: can this be fixed? The answer: yes, but it's hard. (But that's what we're here today to do!)

The easy solution is just to give up and instead use a prime number (like 2; 7; or 6,277,101,735,386,680,763,835,789,423,207,666,416,083,908,700,390,324,961,279) as your modulus. Then, multiplication and division will just work right away, without any problem.

The hard solution requires two more ideas before we can start to explain it… actually, the first of these ideas is the easy solution, so let's look into that!

Idea #2: Finite Fields of prime order ($\mathbb{F}_p$)

What if we tried to make a modular arithmetic table with $7$ (which is prime) as the modulus, rather than 8?

Well, I already spoiled it earlier: all the math—including division—will just work. (But let's look at the example anyway!)

Addition in $\textcolor{teal}{\mathbb{F}_7}$

(As you probably expected, nothing to see here; addition never had any problems. Moving along…)

Multiplication in $\textcolor{teal}{\mathbb{F}_7}$

Without putting your finger on it, doesn't that table look… prettier? Tidier? Neater?

OK, now put your finger on it: notice that each column and each row includes each (non-$\textcolor{teal}{0}$) element exactly once! That means that you can turn any (non-$\textcolor{teal}{0}$) element into any other element, just by a single multiplication! And you'll never accidentally get $\textcolor{teal}{0}$; the only way to reach it by multiplication is by multiplying by $\textcolor{teal}{0}$ on purpose. Of course, this means…

Division in $\textcolor{teal}{\mathbb{F}_7}$

…our division table doesn't have any holes in it—division actually works now!

All this to say that, if (and only if) $p$ is prime, then $\mathbb{Z}_p$ (the integers modulo $p$) is just exactly the same thing as $\mathbb{F}_p$ (the finite field with $p$ elements). Now you know about finite fields with a prime number of elements!

But there are some finite fields with a non-prime number of elements, and we occasionally need those, so let's keep learning until we find out how they work…

Idea #3: Polynomial rings

Below here under active construction, don't read further

Now, the mathematicians call a group of numbers that has addition, subtraction, and multiplication that at least kinda works a ring. (Rings don't care whether division works. As you might have guessed, $\textcolor{indigo}{\mathbb{Z}_8}$ from earlier is a ring.)

Actually, the elements of the ring don't even have to be numbers. They can be any object. Let's create a ring right now with a ridiculous object in it!

We'll start out with $\textcolor{olive}{\mathbb{F}_3}$ (which is a field, admittedly)—

Addition in $\textcolor{olive}{\mathbb{F}_3}$

Multiplication in $\textcolor{olive}{\mathbb{F}_3}$

and we just throw some garbage in there and say “this is an element now”—for example, if we added an arbitrary symbol 🗿 in just to see how the math would cope: ${\textcolor{olive}{\mathbb{F}_3}}{[{\text{🗿}}]}$.

The good news is: this “adjoinment” does not break addition, subtraction, or multiplication!

The bad news is: it breaks division (which is why the result is called a “ring”), and it has an infinite amount of elements—

Addition in $\textcolor{olive}{\mathbb{F}_3}{[{\text{🗿}}]}$