Chapter 24: Algebraic Structures — Groups, Rings, and Fields

"The introduction of the cipher 0 or the group concept was general nonsense too, and mathematics was more or less stagnating for thousands of years because nobody was around to take such childish steps." — Alexander Grothendieck

Overview

Open the source code of any cryptographic library — OpenSSL, libsodium, your language's hashlib — and you will find the same few words over and over: group, field, order, generator. They are not decoration. They are the names of the structures that make the code correct. When you write pow(message, e, n) to encrypt and pow(ciphertext, d, n) to decrypt and the original message comes back, something has to guarantee that round-trip. That guarantee is not luck and it is not "the tests passed." It is a theorem about a group.

You have spent two chapters building machinery in $\mathbb{Z}_n$: addition and multiplication modulo $n$, modular inverses, fast exponentiation, Fermat's and Euler's theorems. Each of those felt like a separate trick. This chapter reveals that they are all consequences of a single fact — that $\mathbb{Z}_n$ under addition, and the invertible elements of $\mathbb{Z}_n$ under multiplication, are groups, and that when $n$ is prime, $\mathbb{Z}_n$ is something even stronger: a field, a number system where you can add, subtract, multiply, and divide. Once you see the structure, the tricks stop being tricks. They become inevitable.

This is the chapter where abstraction earns its keep. We will deliberately throw away almost everything about numbers — what they "are," how big they are, whether they're even — and keep only how an operation behaves. The payoff is enormous: a theorem proved about "any group" is simultaneously a theorem about clock arithmetic, about the symmetries of a square, about the nonzero remainders mod a prime, and about the bytes inside an AES round. One proof, many worlds. That leverage — working at the right level of abstraction so one argument settles many cases — is the master tool of mathematics and of great engineering.

In this chapter you will learn to:

• Recognize an algebraic structure as a set plus operations plus laws, and explain why stripping away everything else is a feature, not a loss.
• State the group axioms and verify them — or find the one that fails — on a concrete set and operation.
• Tell an abelian group from a non-abelian one, and find subgroups, generators, and the order of an element.
• Move up the hierarchy to rings (two operations) and fields (where division works), and place $\mathbb{Z}_n$ exactly: a ring always, a field exactly when $n$ is prime.
• Compute inside the finite fields $\mathrm{GF}(p)$ and $\mathrm{GF}(2^n)$, including the polynomial multiplication that hides inside every AES S-box and every QR code.
• Restate RSA's correctness as a one-line consequence of a group having finite order — the abstract "why" behind the algorithm you'll implement next chapter.

Learning Paths

🏃 Fast Track: You need groups and fields to understand RSA and coding theory, not the full algebra course. Read 24.2 (groups), the statement of Lagrange's theorem in 24.3, and 24.4–24.5 (rings, fields, $\mathrm{GF}(p)$). Skim the $\mathrm{GF}(2^n)$ construction; just absorb that it exists and why. Do the ⭐⭐ exercises.

📖 Standard Path: Read in order. Verify each set of axioms yourself on a small example before reading our verification. Work every 🔄 Check Your Understanding. Make sure you can state — and justify in one sentence — why $\mathbb{Z}_n$ is a field iff $n$ is prime.

🔬 Deep Dive: Prove the corollaries of Lagrange (Fermat and Euler) from Lagrange rather than as the standalone results of Chapter 23. Build the full $\mathrm{GF}(2^3)$ or $\mathrm{GF}(2^8)$ multiplication table by hand, confirm the multiplicative group is cyclic, and read ahead to how Chapter 38 uses it for Reed–Solomon codes.

24.1 What is an algebraic structure?

Start with something you already trust: a clock. On a 12-hour clock, $9 + 5 = 2$. Add five hours to nine o'clock and you land on two o'clock — the count "wraps around." You met this in Chapter 23 as arithmetic modulo 12; here we ask a different question. Not "what is the answer?" but "what kind of system is clock arithmetic, and what other systems share its shape?"

Look at what clock addition does, ignoring what clocks are:

• You can combine any two hours to get an hour. The operation never sends you outside the set $\{0,1,\dots,11\}$.
• It doesn't matter how you group a chain of additions: $(3+4)+5$ and $3+(4+5)$ land on the same hour.
• There is a "do nothing" hour, $0$: adding it changes nothing.
• Every hour has an "undo": adding $9$ then adding $3$ returns you to where you started, because $9+3 = 12 \equiv 0$.

Now look at a completely different system: the eight ways you can rotate and flip a square so it lands back on its own outline (the symmetries of a square). "Combine" two of them means "do one, then the other." The same four behaviors appear. Combining two symmetries is a symmetry. Grouping doesn't matter. There is a "do nothing" symmetry. Every symmetry can be undone.

Two systems — remainders and rigid motions — with nothing in common at the level of "what the elements are," yet identical at the level of "how the operation behaves." An algebraic structure is exactly what you get when you keep the behavior and discard everything else.

Definition (algebraic structure). An algebraic structure is a set $S$ together with one or more binary operations on $S$ (and possibly some distinguished elements, like an identity), satisfying a fixed list of axioms — laws the operations must obey. A binary operation on $S$ is a function $\ast\colon S \times S \to S$; that it always returns an element of $S$ is the closure property, and it is part of what it means to be an operation on $S$.

The genius of this move — historically a hard one; the abstract group concept took mathematics centuries to isolate — is captured in the epigraph above. By naming the structure, we get to prove things once. A theorem whose only hypotheses are the axioms holds in every system satisfying those axioms, forever, including systems nobody has invented yet.

🚪 Threshold Concept. This is the chapter's first threshold, and it reframes everything after it: a theorem proved from axioms alone is true in every model of those axioms. When we later prove "in any finite group, raising an element to the size of the group gives the identity," that single sentence will simultaneously prove Fermat's little theorem (about remainders), a fact about shuffles of a deck (permutations), and the correctness of RSA (about $\mathbb{Z}_n^*$). You stop proving facts about numbers and start proving facts about structure — and structure is reusable.

💡 Intuition: Think of an interface in programming. A sorting routine that takes any object implementing Comparable works on integers, strings, and dates alike, because it depends only on the contract (compareTo), not the concrete type. The group axioms are a mathematical interface. Every theorem about groups is generic code that runs on any type satisfying the interface.

Here is a small program that treats an operation as data — exactly the abstract stance we're taking. It tests the four behaviors above on any set and operation, so we can reuse it for clocks, symmetries, or anything else.

def is_closed(S, op):
    return all(op(a, b) in S for a in S for b in S)

def is_associative(S, op):
    return all(op(op(a, b), c) == op(a, op(b, c))
               for a in S for b in S for c in S)

Z6 = set(range(6))
add6 = lambda a, b: (a + b) % 6
print(is_closed(Z6, add6), is_associative(Z6, add6))
# Expected output:
# True True

We will grow this idea — operation-as-data — into a tiny structure checker by the end of the chapter. For now, notice that nothing in is_closed or is_associative knows or cares that the elements are integers. That ignorance is the abstraction working.

🔄 Check Your Understanding 1. Why is "closure" automatically true for any function $\ast\colon S\times S\to S$ but something you must actually check when someone hands you a set and a formula like "$a\ast b = a + b - ab$ on $\{0,1,2\}$"? 2. Give the "do nothing" element for (a) the integers under addition and (b) the nonzero rationals under multiplication.

Answers

1. If something is given to you as a function into $S$, closure is built into the word "function." But a formula might escape the set — e.g. on $\{0,1,2\}$, $2\ast 2 = 2+2-4 = 0$ stays in, but you must verify every pair lands back in $\{0,1,2\}$ before you may call it an operation on that set. 2. (a) $0$, since $a+0=a$; (b) $1$, since $a\cdot 1 = a$.

24.2 Groups and their properties

Of all algebraic structures, one is so central it deserves its name learned cold: the group. It is the minimal structure in which you can undo operations — and "undoing" is exactly what decryption, subtraction, and running an algorithm backwards all require.

We already saw the four behaviors clock addition has. Promote them to axioms.

Definition (group). A group is a set $G$ with a binary operation $\ast$ satisfying:

1. Closure: for all $a,b \in G$, $a \ast b \in G$.
2. Associativity: for all $a,b,c \in G$, $(a \ast b) \ast c = a \ast (b \ast c)$.
3. Identity: there exists an element $e \in G$ with $e \ast a = a \ast e = a$ for all $a \in G$.
4. Inverses: for every $a \in G$ there exists $a^{-1} \in G$ with $a \ast a^{-1} = a^{-1} \ast a = e$.

We write the group as $(G, \ast)$, or just $G$ when the operation is understood. The number of elements $\lvert G\rvert$ is the order of the group (it may be infinite).

That is the whole definition. Four lines. Everything in this chapter, and a startling amount of cryptography, flows from them.

Definition (abelian group). A group is abelian (or commutative) if it also satisfies, for all $a,b\in G$, $\ a \ast b = b \ast a$.

The name honors Niels Henrik Abel. Commutativity is not a group axiom — plenty of important groups lack it — which is exactly why it gets its own adjective. Clock addition is abelian; the symmetries of a square are not (flip-then-rotate generally differs from rotate-then-flip).

Before any examples, two small but vital facts. They are the kind of thing the axioms force, and proving them shows the axioms at work.

Theorem 24.1 (uniqueness of identity and inverses). In any group, the identity element is unique, and each element has exactly one inverse.

The strategy first. The classic uniqueness move: suppose there were two, then use the defining property of each against the other and watch them collapse into being equal. For the identity, if $e$ and $e'$ are both identities, evaluate the single expression $e \ast e'$ two ways. For inverses, sandwich an element between two of its supposed inverses and let associativity do the work.

Proof. Identity. Suppose $e$ and $e'$ both satisfy the identity axiom. Consider $e \ast e'$. Treating $e$ as an identity, $e \ast e' = e'$. Treating $e'$ as an identity, $e \ast e' = e$. Hence $e = e'$.

Inverses. Fix $a \in G$ and suppose both $b$ and $c$ are inverses of $a$, so $a \ast b = e$ and $c \ast a = e$. Then $$c = c \ast e = c \ast (a \ast b) = (c \ast a) \ast b = e \ast b = b,$$ using the identity axiom, the assumption on $b$, associativity, the assumption on $c$, and the identity axiom again. So $b = c$. $\blacksquare$

Notice we used only the axioms — never which group, never what the elements are. By the threshold concept of 24.1, Theorem 24.1 is now true in every group in existence. That is the whole game.

Worked example: which familiar systems are groups?

Let's audit candidates by checking the four axioms. The discipline of going axiom-by-axiom is the skill; do it even when the answer feels obvious.

$(\mathbb{Z}, +)$ — the integers under addition. Closure ✓ (sum of integers is an integer). Associativity ✓. Identity $0$ ✓. Inverse of $a$ is $-a$ ✓. It is a group, and abelian. Order: infinite.

$(\mathbb{Z}, \cdot)$ — the integers under multiplication. Closure ✓, associativity ✓, identity $1$ ✓. Inverses ✗ — the integer $2$ has no integer multiplicative inverse ($1/2 \notin \mathbb{Z}$). Not a group. The single failed axiom decides it.

$(\mathbb{Z}_n, +)$ — integers mod $n$ under addition. This is clock arithmetic. Closure and associativity inherit from integer addition (then reduce mod $n$). Identity $0$. The inverse of $a$ is $n - a$ (for $a \ne 0$), since $a + (n-a) = n \equiv 0 \pmod n$. A group, abelian, of order $n$. This is the additive structure behind everything in Chapter 23.

$(\mathbb{Z}_n^*, \cdot)$ — the units mod $n$ under multiplication. Here $\mathbb{Z}_n^*$ is the set of residues that have a multiplicative inverse mod $n$. In Chapter 23 you proved $a$ has an inverse mod $n$ exactly when $\gcd(a,n)=1$, so $\mathbb{Z}_n^* = \{a : 1 \le a \le n-1,\ \gcd(a,n)=1\}$, and $\lvert \mathbb{Z}_n^*\rvert = \phi(n)$, Euler's totient. Closure holds because a product of two units is a unit (if $a,b$ are coprime to $n$, so is $ab$). Associativity inherits from multiplication. Identity $1$. Inverses exist by the very definition of the set. A group, abelian, of order $\phi(n)$.

🔗 Connection. That last example is the group at the heart of RSA. RSA works in $\mathbb{Z}_n^*$ where $n = pq$ is a product of two primes, and its order is $\phi(n) = (p-1)(q-1)$. Hold onto $\lvert\mathbb{Z}_n^*\rvert = \phi(n)$ — when we hit 24.3 it will immediately explain why RSA's exponents are chosen mod $\phi(n)$, and Chapter 25 turns that explanation into running code.

Here is $\mathbb{Z}_n^*$ realized from scratch, reusing our coprimality logic from Chapter 22's gcd:

from math import gcd
def units_mod(n):
    return [a for a in range(1, n) if gcd(a, n) == 1]

def mul_table(n, elems):                 # multiplication mod n, restricted to elems
    return {(a, b): (a * b) % n for a in elems for b in elems}

U10 = units_mod(10)                      # 1,3,7,9 are coprime to 10
print(U10, len(U10))
# Expected output:
# [1, 3, 7, 9] 4

The list [1, 3, 7, 9] has 4 elements, matching $\phi(10) = 4$. You can check closure by hand: $3 \cdot 7 = 21 \equiv 1$, $7\cdot 9 = 63\equiv 3$, $9\cdot 9 = 81 \equiv 1$ — every product lands back in the set. The element $9$ is its own inverse; $3$ and $7$ are inverses of each other.

⚠️ Common Pitfall: $(\mathbb{Z}_n, \cdot)$ — all of $\mathbb{Z}_n$ under multiplication — is not a group, because $0$ has no inverse (and when $n$ is composite, other elements fail too: mod 6, the element $2$ has no inverse). You must restrict to the units $\mathbb{Z}_n^*$ to get a group. Forgetting to throw out the non-units is the most common error when people first build multiplicative groups mod $n$.

🔄 Check Your Understanding 1. Is $(\mathbb{N}, +)$ (the naturals, including 0, under addition) a group? Which axiom decides it? 2. List the elements of $\mathbb{Z}_8^*$ and state the group's order. 3. In $(\mathbb{Z}_5^*, \cdot)$, what is the inverse of $2$?

Answers

1. No. Closure, associativity, and identity ($0$) all hold, but inverses fail: $3$ has no natural-number $b$ with $3+b=0$. (You need negative numbers, i.e. $\mathbb{Z}$.) 2. $\mathbb{Z}_8^* = \{1,3,5,7\}$ (the residues coprime to 8); order $\phi(8)=4$. 3. $2\cdot 3 = 6 \equiv 1 \pmod 5$, so $2^{-1} = 3$.

Subgroups: groups living inside groups

Often a subset of a group is, all by itself, a group under the same operation. That is worth a name because it lets us decompose a big group into smaller understood pieces — and because the relationship between a group's size and its subgroups' sizes is about to hand us RSA.

Definition (subgroup). A subset $H \subseteq G$ is a subgroup of a group $(G,\ast)$ if $H$ is itself a group under the same operation $\ast$. Concretely, $H$ must (i) contain the identity, (ii) be closed under $\ast$, and (iii) be closed under taking inverses.

Every group $G$ has two trivial subgroups: $\{e\}$ (just the identity) and $G$ itself. The interesting ones are in between.

Example. Inside $(\mathbb{Z}_6, +)$, the subset $H = \{0, 2, 4\}$ is a subgroup. Check: it contains $0$; it is closed ($2+4 = 6 \equiv 0$, $2+2 = 4$, $4+4 = 8 \equiv 2$ — all in $H$); and inverses stay in ($-2 \equiv 4$, $-4 \equiv 2$, both in $H$). It is a group of order 3 sitting inside a group of order 6. By contrast, $\{0,1,3\}$ is not a subgroup of $\mathbb{Z}_6$: it isn't closed, since $1+3 = 4 \notin \{0,1,3\}$.

Notice the order of the subgroup, $3$, divides the order of the group, $6$. That is not a coincidence. It is the single most important theorem about finite groups, and it is coming in the next section.

24.3 Cyclic groups and generators

Some groups are built entirely by repeating one element. These are the simplest groups, the easiest to reason about — and, conveniently, exactly the kind that crypto uses. To describe them we first need a clean notation for "apply the operation repeatedly."

For an element $a$ of a group, write $a^k$ for $a \ast a \ast \cdots \ast a$ ($k$ copies), with $a^0 = e$ and $a^{-k} = (a^{-1})^k$. (When the operation is addition, the same idea is written $ka$: e.g. in $\mathbb{Z}_6$, "$a^3$" means $a+a+a = 3a$.) These powers obey the laws you'd hope, $a^m \ast a^n = a^{m+n}$, which follow from associativity.

Definition (order of an element). The order of an element $a$ in a group is the smallest positive integer $k$ with $a^k = e$, if such a $k$ exists (otherwise the order is infinite). Do not confuse this with the order of the group, $\lvert G\rvert$; the names collide by tradition, and context disambiguates.

Example. In $(\mathbb{Z}_6, +)$, the element $2$ has order $3$: $2,\ 2+2=4,\ 2+2+2 = 6\equiv 0$. The element $1$ has order $6$. The element $3$ has order $2$.

Definition (cyclic group; generator). A group $G$ is cyclic if there is an element $g \in G$ such that every element of $G$ is a power of $g$ — that is, $G = \{g^k : k \in \mathbb{Z}\}$. Such a $g$ is called a generator of $G$, and we write $G = \langle g\rangle$. A group may have several generators.

💡 Intuition: A generator is a single "step size" that, repeated, visits every element before returning home. On a clock face, stepping by $1$ hour visits all twelve numbers — so $1$ generates $\mathbb{Z}_{12}$. Stepping by $5$ hours also visits all twelve (5, 10, 3, 8, 1, …) — so $5$ is another generator. But stepping by $3$ only ever hits $3,6,9,0$ — it generates a subgroup, not the whole group. A generator is a step whose stride is "coprime to the wrap-around."

Example. $(\mathbb{Z}_6, +)$ is cyclic, generated by $1$: the powers (here, multiples) of $1$ are $1,2,3,4,5,0$ — all of $\mathbb{Z}_6$. It is also generated by $5$: $5, 10\equiv4, 15\equiv3, 20\equiv2, 25\equiv1, 30\equiv0$. But $2$ is not a generator: its powers are only $\{0,2,4\}$ — the subgroup we found in 24.2.

The multiplicative groups are where this gets cryptographically interesting. $(\mathbb{Z}_7^*, \cdot) = \{1,2,3,4,5,6\}$ is cyclic, and $3$ is a generator. Watch the powers of $3$ mod $7$ sweep out the whole group:

def powers_mod(g, n):                    # list distinct powers g^1, g^2, ... mod n
    seen, x = [], g % n
    while x not in seen:
        seen.append(x)
        x = (x * g) % n
    return seen

print(powers_mod(3, 7))                   # is 3 a generator of Z_7^* ?
# Expected output:
# [3, 2, 6, 4, 5, 1]

The list [3, 2, 6, 4, 5, 1] is all six nonzero residues mod 7 — so $3$ generates $\mathbb{Z}_7^*$, confirming the group is cyclic. (Such a generator of $\mathbb{Z}_p^*$ has a special name you'll meet in Chapter 25: a primitive root mod $p$. Diffie–Hellman key exchange is built directly on the difficulty of reversing this sweep — finding $k$ given $g^k$.)

🔗 Connection. Cyclic structure is the backbone of public-key crypto. RSA lives in $\mathbb{Z}_n^*$; Diffie–Hellman and elliptic-curve crypto live in carefully chosen cyclic groups where "step forward $k$ times" is easy but "given the result, recover $k$" (the discrete logarithm) is believed astronomically hard. The asymmetry between those two directions — easy forward, hard backward — is the same trapdoor idea you'll formalize in Chapter 25.

Lagrange's theorem and the payoff for RSA

We noticed twice now that a subgroup's order divides the group's order. Here is the theorem, and it is the structural heart of the chapter.

Theorem 24.2 (Lagrange's theorem). If $G$ is a finite group and $H$ is a subgroup of $G$, then $\lvert H\rvert$ divides $\lvert G\rvert$.

The strategy first. The idea is gorgeous and worth carrying even if you skip the details: the copies of $H$ tile $G$ into equal-sized, non-overlapping pieces. For each $g\in G$, form the coset $gH = \{g\ast h : h\in H\}$. We show (a) every coset has exactly $\lvert H\rvert$ elements, and (b) two cosets are either identical or completely disjoint. Then the cosets partition $G$ into blocks of size $\lvert H\rvert$, so $\lvert G\rvert$ is a whole number times $\lvert H\rvert$ — i.e. $\lvert H\rvert$ divides $\lvert G\rvert$.

Proof. Let $H$ have $m = \lvert H\rvert$ elements. For $g \in G$ define the coset $gH = \{g \ast h : h \in H\}$.

Each coset has $m$ elements. The map $h \mapsto g\ast h$ from $H$ to $gH$ is onto by definition, and it is one-to-one: if $g\ast h_1 = g\ast h_2$, left-multiply by $g^{-1}$ (using associativity and the inverse axiom) to get $h_1 = h_2$. A bijection between $H$ and $gH$ forces $\lvert gH\rvert = m$.

Two cosets are equal or disjoint. Suppose $g_1H$ and $g_2H$ share an element $x$, so $x = g_1 h_1 = g_2 h_2$ for some $h_1,h_2 \in H$. Then $g_1 = g_2 h_2 h_1^{-1}$. Any element of $g_1H$ has the form $g_1 h = g_2 (h_2 h_1^{-1} h)$; since $H$ is a subgroup, $h_2 h_1^{-1} h \in H$, so this element lies in $g_2H$. Thus $g_1H \subseteq g_2H$, and by symmetry $g_2H\subseteq g_1H$, so the cosets are equal.

Conclusion. Every element $g$ lies in its own coset $gH$ (because $e\in H$, so $g = g\ast e \in gH$), so the distinct cosets cover $G$. They are pairwise disjoint and each has size $m$. If there are $t$ distinct cosets, then $\lvert G\rvert = t\cdot m$, so $m = \lvert H\rvert$ divides $\lvert G\rvert$. $\blacksquare$

Lagrange's theorem has a corollary that is, quite literally, the reason RSA works.

Corollary 24.3. In a finite group $G$ of order $N = \lvert G\rvert$, every element $a$ satisfies $a^{N} = e$.

The strategy first. An element's powers form a cyclic subgroup, whose size is the element's order $k$. Lagrange says $k$ divides $N$. So raising to the $N$ is raising to a multiple of $k$ — and raising to a multiple of an element's order always lands on the identity.

Proof. Let $k$ be the order of $a$. The set $\langle a\rangle = \{e, a, a^2,\dots,a^{k-1}\}$ is a subgroup of $G$ (it contains $e$, is closed since $a^i \ast a^j = a^{(i+j)\bmod k}$, and is closed under inverses since $(a^i)^{-1} = a^{k-i}$), and it has exactly $k$ elements. By Lagrange, $k \mid N$, say $N = k\ell$. Then $$a^{N} = a^{k\ell} = (a^{k})^{\ell} = e^{\ell} = e. \qquad \blacksquare$$

Now collect the dividend. Apply Corollary 24.3 to the group $\mathbb{Z}_n^*$, whose order is $\phi(n)$:

$$\text{For every } a \text{ with } \gcd(a,n)=1:\quad a^{\phi(n)} \equiv 1 \pmod{n}.$$

That is Euler's theorem — which you met in Chapter 23 as a standalone result. Here it falls out of pure group structure in two lines. And when $n = p$ is prime, $\phi(p) = p-1$, giving $a^{p-1}\equiv 1 \pmod p$ for $a\not\equiv 0$ — Fermat's little theorem. Two of Chapter 23's headline theorems are the same theorem, Corollary 24.3, viewed in one particular group.

🚪 Threshold Concept. This is the structural punchline of Part IV. RSA encrypts with $c = m^e \bmod n$ and decrypts with $m = c^d \bmod n$, where $d$ is chosen so that $ed \equiv 1 \pmod{\phi(n)}$. Why does decrypting undo encrypting? Because $c^d = m^{ed} = m^{1 + t\phi(n)} = m\cdot (m^{\phi(n)})^{t} \equiv m\cdot 1^{t} = m \pmod n$ — and the step $m^{\phi(n)}\equiv 1$ is exactly Corollary 24.3 in $\mathbb{Z}_n^*$. RSA's correctness is not arithmetic luck; it is the statement "in a finite group, an element raised to the group's order is the identity," wearing a costume. You will turn this paragraph into code in Chapter 25.

🔄 Check Your Understanding 1. The group $\mathbb{Z}_{10}^*$ has order $4$. Without computing all powers, what does Corollary 24.3 guarantee about $7^4 \bmod 10$? 2. A finite group has order $7$ (a prime). What are the only possible orders of its subgroups, and what does that say about its elements? 3. Is $2$ a generator of $\mathbb{Z}_7^*$? (Compute its powers mod 7.)

Answers

1. $7^4 \equiv 1 \pmod{10}$, since $7\in\mathbb{Z}_{10}^*$ and the group has order 4. (Indeed $7^2=49\equiv9$, $7^4\equiv 9^2 = 81\equiv1$.) 2. By Lagrange, subgroup orders divide 7, so only $1$ and $7$. Hence the only subgroups are trivial, and every non-identity element has order 7 — so every non-identity element is a generator. (A group of prime order is always cyclic.) 3. Powers of 2 mod 7: $2,4,1$ — order 3, only hits $\{1,2,4\}$. So no, $2$ generates a subgroup of order 3, not all of $\mathbb{Z}_7^*$.

24.4 Rings and fields

A group has one operation. But the number systems you actually compute in have two — addition and multiplication — that interact through the distributive law. Climbing to two operations gives us rings and, at the top, fields: the structures where ordinary algebra, including division, fully works.

Think about $\mathbb{Z}_n$ again, but now with both $+$ and $\cdot$. We already know $(\mathbb{Z}_n, +)$ is an abelian group. Multiplication mod $n$ is associative, has identity $1$, and distributes over addition. That bundle of properties is a ring.

Definition (ring). A ring is a set $R$ with two operations, addition $+$ and multiplication $\cdot$, such that:

1. $(R, +)$ is an abelian group (identity written $0$, the inverse of $a$ written $-a$).
2. Multiplication is associative: $(a\cdot b)\cdot c = a\cdot(b\cdot c)$.
3. Multiplication distributes over addition: $a\cdot(b+c) = a\cdot b + a\cdot c$ and $(a+b)\cdot c = a\cdot c + b\cdot c$.

If multiplication also has an identity $1\ne 0$, $R$ is a ring with unity; if multiplication is commutative, $R$ is a commutative ring. (In this book "ring" will always mean a commutative ring with unity, which is all CS needs.)

The point of a ring is that you can add, subtract (because $+$ is a group, so inverses exist), and multiply — but not necessarily divide. $(\mathbb{Z}, +, \cdot)$ is the prototype: you can't divide $3$ by $2$ and stay in $\mathbb{Z}$. $(\mathbb{Z}_n, +, \cdot)$ is a ring for every $n$.

To divide, we need every nonzero element to have a multiplicative inverse. That is the top of the hierarchy.

Definition (field). A field is a commutative ring with unity $(F, +, \cdot)$ in which $1\ne 0$ and every nonzero element has a multiplicative inverse — equivalently, $(F\setminus\{0\}, \cdot)$ is an abelian group. In a field you can add, subtract, multiply, and divide by anything nonzero.

The fields you already know are $\mathbb{Q}$ (rationals), $\mathbb{R}$ (reals), and $\mathbb{C}$ (complex numbers). $\mathbb{Z}$ is not a field. The whole hierarchy, from least to most structure:

💡 Intuition: Climb the ladder by gaining the ability to undo. A group lets you undo its one operation. A ring lets you undo addition (subtract) but maybe not multiplication. A field lets you undo both — it is a number system with no arithmetic dead ends except dividing by zero.

The deep question for CS is: when is $\mathbb{Z}_n$ a field? We know it's always a ring. It's a field exactly when every nonzero element is invertible — and Chapter 23 told us precisely which elements are invertible.

Theorem 24.4. $\mathbb{Z}_n$ is a field if and only if $n$ is prime.

The strategy first. An "if and only if" needs both directions. If $n$ is prime: every nonzero residue $a\in\{1,\dots,n-1\}$ satisfies $\gcd(a,n)=1$ (a prime shares no factor with anything below it), so by Chapter 23 every nonzero $a$ has an inverse — field. If $n$ is composite: exhibit a nonzero element with no inverse, killing the field property. The cleanest way is to show a composite modulus has zero divisors — two nonzero things whose product is zero — which no field can have.

Proof. ($\Leftarrow$) Suppose $n = p$ is prime. $\mathbb{Z}_p$ is a commutative ring with unity, and $1 \ne 0$ since $p \ge 2$. Take any nonzero $a \in \{1,\dots,p-1\}$. Because $p$ is prime and $1 \le a < p$, the only common divisor of $a$ and $p$ is $1$, so $\gcd(a,p) = 1$. By the modular-inverse result of Chapter 23, $a$ has a multiplicative inverse mod $p$. Every nonzero element is invertible, so $\mathbb{Z}_p$ is a field.

($\Rightarrow$) Suppose $n$ is composite, say $n = ab$ with $1 < a,b < n$. Then in $\mathbb{Z}_n$, both $a$ and $b$ are nonzero, yet $a\cdot b = n \equiv 0$. We claim $a$ has no inverse. Suppose it did, say $a^{-1}$. Then $$b = 1\cdot b = (a^{-1} a)\, b = a^{-1}(a b) = a^{-1}\cdot 0 = 0,$$ contradicting $b\ne 0$. So $a$ is a nonzero element with no inverse, and $\mathbb{Z}_n$ is not a field. $\blacksquare$

The "$\Rightarrow$" direction quietly proved a general fact worth stating on its own: a field has no zero divisors. If $x\cdot y = 0$ in a field and $x\ne 0$, multiply by $x^{-1}$ to get $y=0$. That property — "a product is zero only if a factor is zero" — is exactly what lets you cancel and solve equations the way you do in $\mathbb{R}$, and it is why polynomial root-finding and error-correcting codes (Chapter 38) demand a field, not just a ring.

A tiny script makes the prime/composite distinction tangible — it asks each nonzero residue whether it has an inverse:

def has_inverse(a, n):
    return any((a * x) % n == 1 for x in range(1, n))

def is_field_Zn(n):                        # every nonzero residue invertible?
    return n >= 2 and all(has_inverse(a, n) for a in range(1, n))

print([n for n in range(2, 13) if is_field_Zn(n)])
# Expected output:
# [2, 3, 5, 7, 11]

The survivors [2, 3, 5, 7, 11] are precisely the primes below 13 — Theorem 24.4 made visible. Mod 4, the element $2$ fails (no $x$ with $2x\equiv1$), because $2\cdot 2 = 4\equiv 0$ makes $2$ a zero divisor.

🔄 Check Your Understanding 1. Is $\mathbb{Z}_9$ a field? If not, name a nonzero element with no inverse and the zero-divisor equation that dooms it. 2. True or false: every field is a ring. Every ring is a field. 3. In the field $\mathbb{Z}_5$, compute $3 - 4$ and $3 \div 4$ (i.e. $3\cdot 4^{-1}$).

Answers

1. Not a field ($9 = 3\cdot 3$ is composite). The element $3$ has no inverse, because $3\cdot 3 = 9\equiv 0$ makes it a zero divisor, and zero divisors can't be invertible. 2. Every field is a ring (true — a field is a ring with extra structure). Not every ring is a field (false — $\mathbb{Z}$ and $\mathbb{Z}_6$ are rings but not fields). 3. $3-4 = -1 \equiv 4 \pmod 5$. For division, $4^{-1}$: $4\cdot 4 = 16\equiv 1$, so $4^{-1}=4$; then $3\cdot 4 = 12 \equiv 2 \pmod 5$.

24.5 Finite fields: $\mathrm{GF}(p)$ and $\mathrm{GF}(2^n)$

Theorem 24.4 just built us an infinite family of finite fields for free: for each prime $p$, $\mathbb{Z}_p$ is a field with exactly $p$ elements. Finite fields are the workhorses of cryptography, coding theory, and hashing, so they get their own name and notation.

Definition (finite field / Galois field). A finite field is a field with finitely many elements. The finite field with $q$ elements is written $\mathrm{GF}(q)$ (for Galois field, after Évariste Galois) or $\mathbb{F}_q$. The field $\mathbb{Z}_p$ for prime $p$ is denoted $\mathrm{GF}(p)$.

A foundational theorem of algebra — which we'll use but not prove — pins down exactly which finite fields exist:

Theorem 24.5 (classification of finite fields, stated). A finite field of order $q$ exists if and only if $q = p^k$ is a prime power ($p$ prime, $k\ge 1$). Moreover, for each prime power there is essentially only one such field (any two are structurally identical). There is no field with, say, $6$ or $10$ elements.

So $\mathrm{GF}(2), \mathrm{GF}(3), \mathrm{GF}(4), \mathrm{GF}(5), \mathrm{GF}(7), \mathrm{GF}(8), \mathrm{GF}(9), \mathrm{GF}(16), \dots$ all exist, but $\mathrm{GF}(6)$ and $\mathrm{GF}(10)$ do not. For prime $q=p$, we already have the field: it's $\mathbb{Z}_p$ with arithmetic mod $p$. But $\mathrm{GF}(p^k)$ for $k>1$ is the puzzle. It is not $\mathbb{Z}_{p^k}$ — we just proved $\mathbb{Z}_{p^k}$ isn't even a field when $k>1$ (it's composite). So where does an 8-element field come from?

⚠️ Common Pitfall: $\mathrm{GF}(8)$ is not $\mathbb{Z}_8$. $\mathbb{Z}_8$ is a ring with zero divisors ($2\cdot 4\equiv 0$), not a field. The field with 8 elements is a different object entirely, built from polynomials, as we're about to see. Conflating "the integers mod $p^k$" with "the field of order $p^k$" is the single biggest stumbling block in this section.

Building $\mathrm{GF}(2^n)$: arithmetic on bit-strings

Here is the construction that powers AES and Reed–Solomon. The idea: take polynomials whose coefficients are bits (elements of $\mathrm{GF}(2)$), and do arithmetic modulo an irreducible polynomial, exactly the way $\mathbb{Z}_p$ does arithmetic with integers modulo a prime.

Concretely, an element of $\mathrm{GF}(2^n)$ is a polynomial of degree less than $n$ with coefficients in $\{0,1\}$. With $n=3$, the elements are $$0,\ 1,\ x,\ x+1,\ x^2,\ x^2+1,\ x^2+x,\ x^2+x+1,$$ which we can write as the 3-bit strings $000, 001, 010, 011, 100, 101, 110, 111$ — there are exactly $2^3 = 8$ of them.

• Addition is coefficient-wise mod 2 — which is just bitwise XOR. For example $(x^2 + x) + (x + 1) = x^2 + 1$, i.e. $110 \oplus 011 = 101$. (Notice addition is its own inverse here: every element is its own negative, because $a\oplus a = 0$. So in $\mathrm{GF}(2^n)$, subtraction equals addition equals XOR.)
• Multiplication multiplies the polynomials, then reduces modulo a fixed irreducible polynomial of degree $n$ — one that doesn't factor over $\mathrm{GF}(2)$. The irreducible polynomial plays the role the prime $p$ played in $\mathbb{Z}_p$: reducing modulo it is what keeps products inside the field and guarantees inverses exist.

For $\mathrm{GF}(2^3)$ we'll fix the irreducible polynomial $m(x) = x^3 + x + 1$. The defining relation is $m(x)\equiv 0$, i.e. $$x^3 \equiv x + 1.$$ Multiply $x^2$ by $x$: that's $x^3$, which we reduce using the relation to $x + 1$. Let's verify multiplication carefully on one product, $(x^2 + x)\cdot(x + 1)$:

$$ (x^2+x)(x+1) = x^3 + x^2 + x^2 + x = x^3 + x \quad(\text{since } x^2+x^2 = 0), $$ then reduce $x^3 \to x+1$: $$ x^3 + x \;\equiv\; (x+1) + x \;=\; 1 \pmod{m(x)}. $$ So in $\mathrm{GF}(2^3)$, $(x^2+x)\cdot(x+1) = 1$ — meaning $x^2+x$ and $x+1$ are multiplicative inverses. Division works; it is a field.

💡 Intuition: $\mathrm{GF}(2^n)$ is "$\mathbb{Z}_p$ for polynomials." Integers mod a prime form a field; polynomials mod an irreducible polynomial form a field. "Prime" and "irreducible" are the same idea — can't be factored — in two different rings. Once you see the analogy, the construction stops feeling exotic: it is the exact same recipe applied to a different set of objects. (Theme three: the right abstraction reveals two constructions to be one.)

The multiplicative group of a finite field is cyclic

Here is the fact that makes finite fields so usable, and it ties this section back to 24.3.

Theorem 24.6 (stated). For any finite field $\mathrm{GF}(q)$, the nonzero elements $\mathrm{GF}(q)^* $ form a cyclic group of order $q - 1$ under multiplication. A generator of this group is called a primitive element of the field.

This means every nonzero element of a finite field is a power of one special element. Let's witness it in $\mathrm{GF}(2^3)$ with the candidate generator $g = x$ (binary $010$). Repeatedly multiply by $x$ and reduce with $x^3 \to x+1$:

The powers $g^1$ through $g^7$ hit all seven nonzero elements before returning to $1$ — so $x$ is a primitive element, and $\mathrm{GF}(2^3)^* $ is cyclic of order $7$, exactly as Theorem 24.6 promised. (Let's sanity-check the row $g^5$: $g^5 = x\cdot g^4 = x(x^2+x) = x^3 + x^2 \equiv (x+1) + x^2 = x^2 + x + 1$ ✓.)

Because every nonzero element is a power of $g$, multiplication in $\mathrm{GF}(2^n)$ can be done with logarithm tables: to multiply, add exponents mod $q-1$. That is precisely how fast finite-field libraries (and Reed–Solomon decoders in your QR-code scanner) actually multiply.

Here is multiplication in $\mathrm{GF}(2^3)$ implemented from scratch — shift-and-XOR with reduction. We show the algorithm rather than calling a library, per the book's rule that concepts are built before they're imported.

def gf8_mul(a, b, mod=0b1011):           # mod = x^3 + x + 1  (binary 1011)
    p = 0
    for _ in range(3):                    # 3 bits in GF(2^3)
        if b & 1:
            p ^= a                        # addition is XOR
        b >>= 1
        a <<= 1
        if a & 0b1000:                    # degree-3 term appeared: reduce
            a ^= mod
    return p

print(gf8_mul(0b110, 0b011))              # (x^2+x) * (x+1)
# Expected output:
# 1

The result 1 matches our hand computation: $(x^2+x)(x+1) = 1$ in $\mathrm{GF}(2^3)$. The if a & 0b1000 line is the polynomial reduction $x^3 \to x+1$ happening in binary — XOR-ing in mod clears the degree-3 bit and adds back $x+1$.

🔗 Connection. $\mathrm{GF}(2^8)$ — the field with 256 elements, built from bytes modulo the irreducible $x^8 + x^4 + x^3 + x + 1$ — is the arithmetic inside AES. Every byte of an AES block is an element of $\mathrm{GF}(2^8)$; the MixColumns step is multiplication in that field, and the S-box uses multiplicative inverses in it. The same field underlies the Reed–Solomon codes (Chapter 38) that repair scratches on CDs, errors in QR codes, and bit-flips in deep-space transmissions. When you compute in $\mathrm{GF}(2^8)$, you are running the same arithmetic as your disk controller and your Wi-Fi chip.

🔄 Check Your Understanding 1. How many elements does $\mathrm{GF}(2^4)$ have, and what are its elements (as objects)? 2. In $\mathrm{GF}(2^3)$ with $x^3\equiv x+1$, compute $x^2 \cdot x^2$ and reduce it to a polynomial of degree $< 3$. 3. Why can't there be a finite field with exactly 6 elements?

Answers

1. $2^4 = 16$ elements; they are all polynomials of degree $<4$ with coefficients in $\{0,1\}$ (equivalently, the 4-bit strings $0000$ through $1111$). 2. $x^2\cdot x^2 = x^4 = x\cdot x^3 \equiv x(x+1) = x^2 + x$ (bits $110$). 3. $6 = 2\cdot 3$ is not a prime power, and by Theorem 24.5 finite fields exist only for prime-power orders. (There is a ring with 6 elements, $\mathbb{Z}_6$, but it has zero divisors and isn't a field.)

24.6 Why CS cares: crypto, coding, and hashing

We've climbed from "set with an operation" to finite fields. Step back and see, in one place, why every rung matters to a working programmer. The recurring theme of the book — discrete math is the language of CS — is nowhere more literal than here: these structures are not applied to the systems below, they are the systems.

Cryptography (Chapters 25, and Diffie–Hellman/ECC beyond this book). RSA is correct because $\mathbb{Z}_n^*$ is a finite group and Corollary 24.3 forces $m^{\phi(n)}\equiv 1$. Diffie–Hellman and elliptic-curve cryptography are secure because certain cyclic groups make "step forward" easy and "step backward" (the discrete logarithm) infeasible. Every public-key system in use is a statement about a group whose structure is easy one way and hard the other.

Coding theory (Chapter 38). Error-correcting codes treat blocks of data as vectors over a finite field and exploit field arithmetic to detect and repair corruption. Reed–Solomon codes — in QR codes, CDs/DVDs, RAID arrays, and the Voyager probes — are built over $\mathrm{GF}(2^8)$. You can only "divide out" errors because a field lets you divide. A ring wouldn't do; the zero divisors would break the algebra.

Hashing and checksums (Chapter 26). CRCs (cyclic redundancy checks), in Ethernet, ZIP files, and disk sectors, are polynomial division in $\mathrm{GF}(2)$. The "magic polynomial" in a CRC spec is exactly a divisor in the polynomial ring over $\mathrm{GF}(2)$. Many fast hash functions reduce modulo a prime precisely to borrow the clean structure of $\mathrm{GF}(p)$.

The unifying lesson. Each application picks the smallest structure that does the job: a group when you only need to undo one operation, a field when you need full arithmetic including division. Choosing the right structure is choosing the right interface — and, as the threshold concept of 24.1 promised, every theorem you proved about the abstract structure ships, for free, with every concrete system that implements it.

🔗 Connection. This section is the hinge of Part IV. Backward, it explains why the modular arithmetic of Chapter 23 behaves so well — it was group and field structure all along. Forward, it splits into the two payoffs the rest of the book collects: Chapter 25 cashes in the group structure to build RSA, and Chapter 38 cashes in the field structure to build error-correcting codes.

Project Checkpoint: starting crypto.py with RSA key generation

Time to begin the module that pays off two chapters of number theory: crypto.py, the RSA piece of the Toolkit. The full picture spans Chapters 24–25 — this chapter contributes rsa_keygen, and Chapter 25 will add rsa_encrypt and rsa_decrypt and prove the whole thing correct. We can build key generation now because everything it needs is structural and already in hand: pick two primes $p,q$; set $n = pq$ and $\phi = (p-1)(q-1) = \lvert\mathbb{Z}_n^*\rvert$; choose a public exponent $e$ coprime to $\phi$; and compute the private exponent $d \equiv e^{-1} \pmod{\phi}$. That last step is exactly the modular inverse from Chapter 23, and the reason we work mod $\phi$ rather than mod $n$ is Corollary 24.3 — the group $\mathbb{Z}_n^*$ has order $\phi(n)$, so exponents live mod $\phi(n)$.

Create dmtoolkit/crypto.py (it imports the number-theory tools you built in Chapters 22–23) and add:

from dmtoolkit.numbertheory import mod_inverse, sieve  # Chapters 22-23
import random

def rsa_keygen(bits=8):
    """Toy RSA key generation. Returns (public, private) = ((e, n), (d, n)).
    Educational scale only — real RSA uses bits >= 2048."""
    primes = [p for p in sieve(2 ** bits) if p > 2 ** (bits - 1)]
    p, q = random.sample(primes, 2)              # two distinct primes
    n = p * q
    phi = (p - 1) * (q - 1)                       # |Z_n^*| = (p-1)(q-1)
    e = 65537 if 65537 < phi and _coprime(65537, phi) else _pick_e(phi)
    d = mod_inverse(e, phi)                       # d * e == 1 (mod phi)
    return (e, n), (d, n)

def _coprime(a, b):
    while b: a, b = b, a % b
    return a == 1

def _pick_e(phi):
    e = 3
    while not _coprime(e, phi): e += 2
    return e

To see what a generated key looks like, here is a hand-traceable instance with the primes fixed (so the output is deterministic): take $p=61$, $q=53$. Then $n = 61\cdot 53 = 3233$ and $\phi = 60\cdot 52 = 3120$. Choose $e = 17$ (coprime to 3120). The private exponent is $d = 17^{-1} \bmod 3120 = 2753$ — you can check $17\cdot 2753 = 46801 = 15\cdot 3120 + 1$, so $17\cdot 2753 \equiv 1 \pmod{3120}$.

# Deterministic illustration with p=61, q=53 (the classic textbook key):
n = 61 * 53; phi = 60 * 52; e = 17
d = mod_inverse(e, phi)           # modular inverse from Chapter 23
print((e, n), (d, n))
# Expected output:
# (17, 3233) (2753, 3233)

These are the public key $(17, 3233)$ and private key $(2753, 3233)$. How this builds toward the capstone: key generation is the foundation of the entire RSA system. In Chapter 25 you'll add rsa_encrypt(m, pub) = pow(m, e, n) and rsa_decrypt(c, priv) = pow(c, d, n), prove via Euler/Corollary 24.3 that decryption inverts encryption, and watch a message survive the round trip — completing capstone Track A's cryptographic core.

Toolkit so far: logic.py (1–3), sets.py (8), relations.py (12–13), combinatorics.py (15–17), recurrences.py (18–19), probability.py (20–21), numbertheory.py (22–23), and now the start of crypto.py (24). Every public key you'll generate is built on the group $\mathbb{Z}_n^*$ this chapter explained.

Summary

This chapter abstracted the arithmetic of Chapters 22–23 into the structures that explain why it works.

The hierarchy of structures.

Key definitions.

• Order of a group $= \lvert G\rvert$; order of an element $a$ = smallest $k>0$ with $a^k = e$.
• Subgroup: a subset that is a group under the same operation (contains $e$, closed under $\ast$ and inverses).
• Cyclic group: $G = \langle g\rangle$ for some generator $g$; every element is a power of $g$.
• Finite field $\mathrm{GF}(q)$: a field with $q$ elements; exists iff $q$ is a prime power.

Key theorems.

A decision aid — "what structure is this?" Given a set $S$ with operation(s):

1. One operation? Check closure → associativity → identity → inverses. All four ⇒ group; add commutativity ⇒ abelian.
2. Two operations? Is $(S,+)$ an abelian group and does $\cdot$ distribute? ⇒ ring. Then: is every nonzero element invertible (equivalently, no zero divisors and finite, or invertibility shown)? ⇒ field.
3. Shortcut for $\mathbb{Z}_n$: ring always; field iff $n$ is prime.

Common pitfalls. $(\mathbb{Z}_n, \cdot)$ is not a group (must restrict to units $\mathbb{Z}_n^*$). $\mathrm{GF}(p^k)\ne \mathbb{Z}_{p^k}$ for $k>1$ (the latter isn't a field). Commutativity is not a group axiom. In $\mathrm{GF}(2^n)$, addition is XOR and is its own inverse.

Toolkit: added rsa_keygen to crypto.py — RSA's structure (work mod $\phi(n) = \lvert\mathbb{Z}_n^*\rvert$) is Corollary 24.3 in disguise.

Spaced Review

Retrieval strengthens memory. Answer from memory before opening the solutions.

1. (Ch. 23) Euler's theorem says $a^{\phi(n)}\equiv 1\pmod n$ when $\gcd(a,n)=1$. In this chapter's language, which group is this a statement about, and which general group theorem is it a special case of?
2. (Ch. 23) Computing the private RSA exponent $d$ requires $e^{-1} \bmod \phi(n)$. Which Chapter-23 algorithm produces a modular inverse, and what condition on $e$ and $\phi(n)$ must hold for it to exist?
3. (Ch. 8) A subgroup $H$ of $G$ is in particular a subset of $G$. Using the cardinality notion from Chapter 8, restate Lagrange's theorem as a relationship between $\lvert H\rvert$ and $\lvert G\rvert$, and say why a group of order 12 can have no subgroup of order 5.
4. (Ch. 8) $\mathbb{Z}_n^*$ is a subset of $\mathbb{Z}_n$ defined by a property. Write $\mathbb{Z}_{12}^*$ in set-builder notation and give its cardinality.

Answers

1. It is a statement about the multiplicative group $\mathbb{Z}_n^*$ (order $\phi(n)$). It is the special case of Corollary 24.3 — "$a^{\lvert G\rvert} = e$ in any finite group" — applied to $G = \mathbb{Z}_n^*$. 2. The extended Euclidean algorithm (it yields Bézout coefficients, one of which is the inverse). The inverse $e^{-1}\bmod\phi(n)$ exists iff $\gcd(e, \phi(n)) = 1$. 3. Lagrange: $\lvert H\rvert$ divides $\lvert G\rvert$. Since $5 \nmid 12$, no subgroup can have order 5. 4. $\mathbb{Z}_{12}^* = \{a \mid 1\le a\le 11,\ \gcd(a,12)=1\} = \{1,5,7,11\}$; cardinality $\phi(12) = 4$.

What's Next

You now hold the abstract "why" behind everything Part IV has been building toward: $\mathbb{Z}_n^*$ is a finite group, so any element raised to the group's order returns to the identity — and that is what makes encryption reversible. Chapter 25 spends that capital. We'll trace cryptography from the Caesar cipher (and why it falls in seconds) through the key-exchange problem to the breakthrough of public-key cryptography, and then build RSA: generate keys (you already started), encrypt, decrypt, and prove with Euler's theorem — Corollary 24.3 in costume — that the message always comes back. The structure is in place; next we make it compute.