Groups, Rings, and Fields

In the previous note we listed five things that an operation might or might not have: closure, associativity, commutativity, an identity element, and inverses for each element. Mathematicians have given names to the most important combinations of these properties. Three of those names are group, ring, and field. Each one demands more than the last. Each one shows up in the cryptography we are working towards.

Names alone are abstract. We will start by playing with the integers and seeing which structure they fit, then peel the definitions off the example.

A small experiment with $(\mathbb{Z}, +)$

Look at the integers $\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}$ together with ordinary addition. Run through the five properties:

1. Closure. Adding any two integers gives an integer. Pass.
2. Associativity. $(a + b) + c = a + (b + c)$ for any integers. Pass.
3. Identity. The number $0$ does nothing: $a + 0 = a$. Pass.
4. Inverses. Every integer $a$ has an additive inverse $-a$, also an integer, with $a + (-a) = 0$. Pass.
5. Commutativity. $a + b = b + a$. Pass.

The integers under addition pass all five. Stripping the commutativity check off (it is not strictly required for the basic name "group") still leaves four passes, and that is enough to call $(\mathbb{Z}, +)$ a group. Because the commutativity does happen to hold here, it is more specifically called a commutative group or an abelian group, after Niels Henrik Abel.

02.What a group is

A group is a set $G$ together with a binary operation $*$ such that the following four conditions hold.

1. Closure. For every $a, b \in G$, the element $a * b$ is also in $G$.
2. Associativity. For every $a, b, c \in G$, $(a * b) * c = a * (b * c)$.
3. Identity. There is an element $e \in G$ such that $a * e = e * a = a$ for every $a \in G$.
4. Inverses. For every $a \in G$, there is some $a' \in G$ such that $a * a' = a' * a = e$.

If, in addition, $a * b = b * a$ for every $a, b \in G$, the group is called abelian or commutative.

The five-property check on $(\mathbb{Z}, +)$ is doing exactly this. The operation is $+$, the identity $e$ is $0$, the inverse of $a$ is $-a$.

It is worth pausing on a non-example before moving on. $(\mathbb{N}, +)$ is not a group. Closure, associativity, identity ($0 \in \mathbb{N}$) all hold. But inverses fail: the integer $-3$ is the additive inverse of $3$ in $\mathbb{Z}$, but $-3 \notin \mathbb{N}$. So $\mathbb{N}$ is missing inverses, and that is enough to disqualify it. The smallest extra thing you would need to add to $\mathbb{N}$ to turn it into a group under addition is exactly the negative integers.

A second non-example: $(\mathbb{Z}, \cdot)$ under multiplication is not a group. Closure and associativity and identity ($1 \in \mathbb{Z}$) all hold. But inverses fail: the multiplicative inverse of $5$ would be $1/5$, which is not an integer.

So the integers form a group under addition but not under multiplication. The rationals $\mathbb{Q}$, on the other hand, form a group under addition (with $0$ as identity), and the non-zero rationals $\mathbb{Q} \setminus \{0\}$ form a group under multiplication (with $1$ as identity, and $1/a$ as the inverse of $a$). The reason for excluding $0$ from the multiplicative group is that $0$ has no multiplicative inverse: there is no $x$ with $0 \cdot x = 1$.

This pattern (a set that is a group under one operation, and a different set, almost the same, that is a group under another operation) shows up so often that it has its own name: a ring. In a ring, both groups exist on the same underlying set, and the two operations interact through a distributive law.

03.What a ring is

A ring is a set $R$ together with two binary operations, called addition (written $+$) and multiplication (written $\cdot$), such that

1. $(R, +)$ is an abelian group. The additive identity is written $0$ and the additive inverse of $a$ is written $-a$.
2. Multiplication is associative: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$.
3. Multiplication has an identity: there is some $1 \in R$ with $1 \cdot a = a \cdot 1 = a$ for every $a$. (Some textbooks omit this, but we always include it. A ring without a multiplicative identity is sometimes called a rng, the missing "i" being a wink.)
4. Multiplication distributes over addition, on both sides:

$$a \cdot (b + c) = a \cdot b + a \cdot c, \qquad (a + b) \cdot c = a \cdot c + b \cdot c.$$

If multiplication is also commutative, $a \cdot b = b \cdot a$, the ring is called a commutative ring. Every ring we will meet in this chapter is commutative.

There is no requirement that every element have a multiplicative inverse. That is the gap between a ring and a field.

The integers $(\mathbb{Z}, +, \cdot)$ are the first example, and the canonical one. The two operations, the additive identity $0$, the multiplicative identity $1$: everything you want is there. Distributivity is the law you have used since elementary school, $3 \cdot (4 + 5) = 3 \cdot 4 + 3 \cdot 5$. The integers form a commutative ring. They are not a field, because $5$ has no multiplicative inverse inside $\mathbb{Z}$.

04.What a field is

A field is a commutative ring in which every non-zero element has a multiplicative inverse. Concretely, a field is a set $F$ with two operations $+$ and $\cdot$ such that

1. $(F, +)$ is an abelian group.
2. $(F \setminus \{0\}, \cdot)$ is an abelian group.
3. Multiplication distributes over addition.

The condition $(F \setminus \{0\}, \cdot)$ is a group is the new ingredient. It says that every $a \neq 0$ has an inverse $a^{-1}$ with $a \cdot a^{-1} = 1$. That single addition is the whole difference between a field and a commutative ring.

The rationals $\mathbb{Q}$ are a field. So are the reals $\mathbb{R}$. The integers $\mathbb{Z}$ are not a field, because $1/5 \notin \mathbb{Z}$.

The point of having a field is that you can divide. In a ring, you can add, subtract, and multiply, but division can fail. In a field, division by anything non-zero is always allowed. That makes fields the cleanest setting for solving equations like $3x = 7$: in a field, $x = 7 \cdot 3^{-1}$ always exists.

05.A useful picture

Picture three nested boxes.

Every field is a commutative ring. Every commutative ring is a ring. As you move from the outer ring into the inner field, more is guaranteed and more equations have solutions.

The example labels indicate where the named number systems sit. $\mathbb{Z}$ lives in the commutative-ring box but not in the field box, because integer division fails. $\mathbb{Q}, \mathbb{R}$, and the modular fields $\mathbb{Z}_p$ for $p$ prime (which we are about to construct) all live in the innermost field box.

06.Why this matters for what comes next

The post-quantum schemes Kyber and Dilithium do all their arithmetic inside a particular ring, called $R_q$. This $R_q$ is built in three steps. Step one is to take the integers and reduce them modulo a number $q$, producing $\mathbb{Z}_q$. When $q$ is a prime, $\mathbb{Z}_q$ turns out to be a field. Step two is to make polynomials with coefficients in $\mathbb{Z}_q$, giving the bigger ring $\mathbb{Z}_q[X]$. Step three is to quotient that polynomial ring by the relation $X^n = -1$, giving $R_q$. At each step the same checklist of axioms (the ones in this note) gets verified.

Knowing the words "group", "ring", and "field" precisely is what lets you read the rest of the literature. When a paper says "the secret key is an element of $R_q^k$", it is saying "the secret key is a vector of $k$ elements, each one drawn from this ring whose name we have just defined". Without the vocabulary, the sentence is unreadable. With it, the sentence is just a fact.

07.A short exercise

Decide which of the following are groups, commutative rings, or fields, under the operations indicated.

1. $(\mathbb{Z}, +)$. A group, abelian. Not a ring on its own because we have only one operation. With multiplication added, it becomes a commutative ring but not a field.
2. $(\mathbb{Q} \setminus \{0\}, \cdot)$. A group, abelian. Not a ring, only one operation.
3. $(\mathbb{R}, +, \cdot)$. A field.
4. $(\{0, 1\}, +, \cdot)$ with the rule "take the ordinary result and keep only the last bit". We will see in the next two notes that this is the field $\mathbb{Z}_2$. It happens to be the smallest field there is.

The fourth one is the bridge to the next note, where modular arithmetic is built up properly, and the small finite rings $\mathbb{Z}_n$ are constructed.