Chapter 24 — Key Takeaways

Algebraic Structures: Groups, Rings, and Fields. Reread this before an exam; it is the chapter compressed to one page.

The big idea (read first)

An algebraic structure = a set + operation(s) + axioms. A theorem proved from the axioms alone holds in every system that satisfies them. RSA's correctness, Euler's theorem, and Fermat's little theorem are all one theorem — "in a finite group, $a^{\lvert G\rvert} = e$" — viewed in the group $\mathbb{Z}_n^*$.

The hierarchy at a glance

Structure Ops Must satisfy You can… Canonical example
Group $\ast$ closure, assoc., identity $e$, inverses undo $\ast$ $(\mathbb{Z},+)$, $(\mathbb{Z}_n^*,\cdot)$
Abelian group $\ast$ group + commutativity undo $\ast$ $(\mathbb{Z}_n,+)$
Ring $+,\ \cdot$ $(R,+)$ abelian grp; $\cdot$ assoc. & distributes add, subtract, multiply $(\mathbb{Z},+,\cdot)$, $(\mathbb{Z}_n,+,\cdot)$
Field $+,\ \cdot$ ring + every nonzero elt invertible add, subtract, multiply, divide $\mathbb{Q},\mathbb{R},\ \mathrm{GF}(p),\ \mathrm{GF}(2^n)$

Ladder rule: each rung adds the ability to "undo" one more thing. Field = no arithmetic dead ends except $\div 0$.

Group axioms (memorize the 4 — "CAII")

For $(G,\ast)$, all $a,b,c\in G$:

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

Abelian adds commutativity ($a\ast b=b\ast a$) — not a group axiom on its own.

Definitions to recall cold

Term Definition
Order of a group $\lvert G\rvert$ = number of elements
Order of an element $a$ smallest $k>0$ with $a^k=e$
Subgroup $H\le G$ subset that is a group under the same $\ast$ (has $e$; closed under $\ast$ and inverses)
Cyclic group $G=\langle g\rangle$: every element is a power of one generator $g$
Generator element whose powers produce the whole group
Ring $(R,+,\cdot)$: $+$ abelian group, $\cdot$ associative & distributive
Field ring where every nonzero element is invertible
Finite field $\mathrm{GF}(q)$ field with $q$ elements (Galois field); exists iff $q=p^k$
Zero divisor nonzero $a$ with nonzero $b$ such that $ab=0$ (impossible in a field)
Primitive element generator of $\mathrm{GF}(q)^*$

Theorems / formulas

# Result Formula / statement
24.1 Uniqueness identity and each inverse are unique
24.2 Lagrange $H\le G$ finite $\Rightarrow \lvert H\rvert \mid \lvert G\rvert$
24.3 Corollary finite group order $N$: $\;a^N = e\;$ for all $a$
— Euler (from 24.3) $\gcd(a,n)=1 \Rightarrow a^{\phi(n)}\equiv 1 \pmod n$
— Fermat (from 24.3) $p$ prime, $p\nmid a \Rightarrow a^{p-1}\equiv 1 \pmod p$
24.4 Field criterion $\mathbb{Z}_n$ is a field $\iff n$ is prime
— No zero divisors a field has none; $xy=0,\ x\ne0 \Rightarrow y=0$
24.5 Classification $\mathrm{GF}(q)$ exists $\iff q=p^k$ (prime power); essentially unique
24.6 Cyclic units $\mathrm{GF}(q)^*$ is cyclic of order $q-1$

Key counts: $\lvert\mathbb{Z}_n^*\rvert = \phi(n)$; if $n=pq$ then $\phi(n)=(p-1)(q-1)$.

$\mathrm{GF}(2^n)$ cheat-sheet (the AES / coding field)

  • Elements = polynomials of degree $$n$-bit strings ($2^n$ of them).
  • Addition = bitwise XOR. Self-inverse: $a\oplus a=0$, so subtraction = addition = XOR.
  • Multiplication = multiply polynomials, then reduce mod an irreducible polynomial of degree $n$ (the analogue of a prime).
  • $\mathrm{GF}(2^3)$ with $m(x)=x^3+x+1$: defining relation $\boxed{x^3\equiv x+1}$.
  • $g=x$ is primitive: $g^0..g^6 = 001,010,100,011,110,111,101$, then $g^7=001$.
  • $\mathrm{GF}(2^8)$ (modulus $x^8+x^4+x^3+x+1$) = the field inside AES and Reed–Solomon.

⚠️ $\mathrm{GF}(p^k) \ne \mathbb{Z}_{p^k}$ for $k>1$. $\mathrm{GF}(8)\ne\mathbb{Z}_8$ ($\mathbb{Z}_8$ has zero divisor $2\cdot4\equiv0$).

"What structure is this?" decision tree

How many operations?
├─ ONE (∗):  closed? assoc? identity? inverses?
│      all 4 → GROUP   (+ commutative → ABELIAN)
│      any fails → not a group (name the failed axiom)
└─ TWO (+,·): is (S,+) an abelian group AND does · distribute?
       no  → not even a ring
       yes → RING
             └─ every nonzero element invertible (no zero divisors)?
                   yes → FIELD     no → ring but not a field
Shortcut for Z_n:  always a RING;  FIELD ⇔ n is prime.

Common pitfalls (exam traps)

Trap Reality
"$(\mathbb{Z}_n,\cdot)$ is a group" No — $0$ (and non-units) lack inverses. Restrict to $\mathbb{Z}_n^*$.
"$(\mathbb{Z},\cdot)$ is a group" No — only $\pm1$ have integer inverses.
"Commutativity is a group axiom" No — it's the extra axiom that makes a group abelian.
"$\mathrm{GF}(8)=\mathbb{Z}_8$" No — $\mathbb{Z}_8$ isn't a field; $\mathrm{GF}(8)$ is built from polynomials.
"$\mathrm{GF}(6)$ exists" No — 6 isn't a prime power.
"Order of element = order of group" Different! element order = smallest $k$ with $a^k=e$; it divides group order.
Confusing subtraction in $\mathrm{GF}(2^n)$ There is none separate — it's XOR.

Toolkit addition (crypto.py, built 24–25)

Function Signature This chapter
rsa_keygen rsa_keygen(bits) → ((e,n),(d,n)) added (Ch. 24)
rsa_encrypt rsa_encrypt(m, pub) Chapter 25
rsa_decrypt rsa_decrypt(c, priv) Chapter 25

Keygen recipe: primes $p,q$ → $n=pq$, $\phi=(p-1)(q-1)$ → pick $e$ with $\gcd(e,\phi)=1$ → $d=e^{-1}\bmod\phi$. Why mod $\phi$, not $n$? Because $\lvert\mathbb{Z}_n^*\rvert=\phi(n)$ and Corollary 24.3 says exponents cycle mod the group's order. Classic key: $p=61,q=53 \Rightarrow n=3233,\ \phi=3120$, $e=17 \Rightarrow d=2753$ (since $17\cdot2753\equiv1\pmod{3120}$).

One-line connections

  • ← Ch. 23: modular arithmetic was group/field structure all along; Euler/Fermat = Corollary 24.3.
  • → Ch. 25: RSA = cash in the group structure ($\mathbb{Z}_n^*$).
  • → Ch. 38: error-correcting codes = cash in the field structure ($\mathrm{GF}(2^n)$).