Groups, Rings, and Fields Without the Pain

I used to skip this chapter. Groups, rings, fields. The unsexy stuff. Then RSA showed up and I was lost. Same with elliptic curve crypto. Computational Number Theory and Modern Cryptography by Song Y. Yan (ISBN 978-1-118-18858-3) starts Chapter 2 with this exact trap.

Section 2.1 is Basic Algebraic Structures. Yan writes like a theorem machine. Definition, example, definition, theorem. No pep talk. That is annoying. It is also the right order. If you do not own these words, later chapters feel like noise. I am keeping the axioms and throwing out the intimidation.

I am going to translate. A group is a closed club with an undo button. A field is a place where you can divide, except by zero. Clock arithmetic is the picture that makes the axioms stop hurting. I read this section twice. First as vocabulary. Then as the reason some clocks let you divide and others do not.

Four Rules, Then You Have a Group

Yan’s Definition 2.1 is four axioms on a nonempty set G with one operation, written as a star.

Closure: combine two members, stay in the club. Associativity: grouping does not matter. Identity: there is one do-nothing element e, unique, and e star a equals a. Inverse: every a has a unique partner that returns you to e.

If a star b always equals b star a, the group is commutative. Yan also calls that Abelian, after N. H. Abel.

Change the symbol and the names change. If the operation is plus, the identity is 0 and the inverse of a is minus a. That is an additive group. If the operation is times, the identity is 1 and you talk about multiplicative groups.

The first examples fail. Positive integers with plus have no identity, because 0 is not in the set. Nonnegative integers with plus have 0, but 2 has no inverse. Positive integers with times have 1, but 3 has no inverse.

The sets that work are the ones you already use. Positive rationals and reals under times. Nonzero rationals, reals, and complexes under times. Those are Abelian groups.

Finite versus infinite is a head count. The order of G is |G|, also written #(G). Integers under plus have infinite order. Integers modulo 11 have order 11.

Clock Arithmetic and Cyclic Groups

A subgroup is a nonempty subset that is still a group under the same operation. The useful ones come from repeating one element.

Take a in a multiplicative group. The powers of a form a subgroup, the subgroup generated by a. If those powers fill G, the group is cyclic and a is a generator. Finite cyclic groups look like {e, a, a squared, …, a to the n minus 1} with a to the n equal to e, and n as small as possible. Infinite cyclic groups are all integer powers of a.

Additive cyclic groups are the same idea with plus. The set {0, 1, …, n minus 1} with addition modulo n is cyclic. Ordinary integers under plus are infinite cyclic, generated by 1.

Yan’s running example is the additive group modulo 6. You add and wrap at 6. The table is a six-hour clock.

1 plus 5 is 0. 4 plus 4 is 2. 5 plus 5 is 4. Identity is 0. Inverse of 1 is 5. Inverse of 2 is 4. Inverse of 3 is 3, because 3 plus 3 is 6, which is 0 on this clock.

That table is not decoration. Modular plus and times are the whole vibe of later crypto. If you can read that grid, you can read a toy cipher.

Rings Are Groups With a Second Operation

A ring has two operations. Under plus you already have an Abelian group. Under times you only get closure and associativity. Times also has to distribute over plus, on both sides.

Integers, rationals, reals, and complexes are all rings. Extra adjectives stack on. A commutative ring has a times b equal to b times a. A ring with identity has a 1. An integral domain is a commutative ring with 1 not equal to 0, and no zero divisors. A division ring gives every nonzero element a left inverse and a right inverse.

You do not need all of those names on day one. Integers form a commutative ring with identity. They are not a field. 2 has no multiplicative inverse in Z. The only units, meaning the invertible elements, are 1 and minus 1.

Polynomials over a field K, written K[x], are another ring that is not a field. You can add and multiply them. You cannot invert x plus 1 inside that ring.

Fields: Why You Can Divide Sometimes

A field is a division ring with commutative multiplication. Short version: plus is an Abelian group, the nonzero elements form an Abelian group under times, and times distributes.

That is the divide rule. Every nonzero a has an inverse, so dividing by a means multiplying by that inverse. Zero stays out of the multiplicative club.

Q, R, and C are infinite fields. Z is not.

Theorem 2.1 is the one that matters: Z/nZ is a field if and only if n is prime. When n is prime, Yan writes F_p.

Clock arithmetic again. On a five-hour clock, 2 times 3 is 6, which is 1 modulo 5. So 2 and 3 are inverses. Dividing by 2 is multiplying by 3. On a six-hour clock, 2 never hits 1. You get 0, 2, 4, then it repeats. You cannot divide by 2 there.

Sometimes the clock lets you divide. Sometimes it does not. Prime size is the difference.

Finite fields have finitely many elements. Galois proved there is a field of order q if and only if q is a prime power, q = p^r. And there is only one such field, up to relabelling. People write GF(q) or F_q. Yan’s F_5 tables are the five-hour clock with both operations. Every nonzero times row contains a 1. That is the inverse sitting in public.

Polynomials, Factoring, and Algebraic Integers

Over a field, F[x] still has a division algorithm: f = p q + r, with r zero or of smaller degree than p. Euclid still works. The last nonzero remainder is gcd(f, g), and you can write it as s f + t g.

Irreducible polynomials are the primes of this world. Degree at least one, and not a product of two nonconstant polynomials of lower degree. Over Q, x squared plus 1 is irreducible. So is x squared minus 2. Over the reals, x squared minus 2 splits.

If F is a field, unique factorization holds in F[x]. Leave the field and it gets weird. Yan factors 3x plus 3 in Z_6[x] several ways, because 3 is a zero divisor modulo 6. Over Z_5 it factors cleanly.

Algebraic numbers are complex roots of polynomials with rational coefficients. i and sqrt(2) have degree 2. Every rational is algebraic. Algebraic integers are the ones whose monic polynomial lives in Z[x]. Gaussian integers a + bi form Z[i]. There, 2, 5, 13, and 17 stop being prime. 2 is (1+i)(1-i). A number is an algebraic integer if and only if its minimal polynomial has integer coefficients. Cube root of 5/7 is algebraic, not an algebraic integer.

The algebraic numbers form a field. The algebraic integers form a ring. That is the last theorem of the section.

My honest take: this is the chapter people skip, then they get lost in RSA and ECC. Yan will not hold your hand. He will hand you a table modulo 6 and assume you see a group. See it.

Previous: Computation Theory and Why Hard Problems Matter Next: Divisibility, Primes, and the Euclidean Algorithm