Week 20 — Polynomial Rings, Extension Fields, and Finite Fields

Overview

The polynomial ring \(F[x]\) over a field \(F\) behaves like the integers: there is a division algorithm, a notion of irreducibility analogous to primality, and unique factorization. When you mod out by an irreducible polynomial \(p(x)\) — forming the quotient ring \(F[x]/(p(x))\) — you get a new field, an extension of \(F\). This single construction, applied to \(\mathbb{F}_p[x]\) with an irreducible polynomial of degree \(k\), produces the field \(\mathbb{F}_{p^k}\) of order \(p^k\). The structure theorem for finite fields says every finite field arises this way and any two fields of the same order are isomorphic. These are the fields in which RSA, elliptic curve cryptography, and algebraic error correcting codes operate.

Readings

Pinter Ch 22–23 — Polynomial rings and factoring. The ring \(F[x]\); the division algorithm for polynomials; GCD; irreducible polynomials; unique factorization in \(F[x]\).
Pinter Ch 24, 26 — Extension fields and degree. Adjoining a root; \(F[x]/(p(x))\) as a field when \(p(x)\) is irreducible; the degree \([K:F]\) of an extension; the tower law \([L:F] = [L:K][K:F]\).
Pinter Ch 28–29 — Roots of polynomials and finite fields. Splitting fields; the structure theorem for finite fields; classification of \(\mathbb{F}_{p^k}\); the Frobenius automorphism.

Key Concepts

Polynomial rings and the division algorithm

\(F[x]\) is the ring of polynomials over a field \(F\). It mirrors \(\mathbb{Z}\) almost exactly because it carries a division algorithm: for \(f, g \in F[x]\) with \(g \neq 0\) there are unique \(q, r\) with

\[f = qg + r, \qquad \deg r < \deg g.\]

A degree function plus division makes \(F[x]\) a Euclidean domain, so the Euclidean algorithm computes GCDs and Bézout coefficients, every ideal is principal (a PID), and unique factorization holds. This is the structural reason polynomials behave like integers.

Irreducibility and unique factorization

A polynomial of positive degree is irreducible over \(F\) if it admits no factorization into two factors of smaller positive degree over \(F\) (irreducibility is relative to the field). Irreducibles are the primes of \(F[x]\), and every polynomial factors uniquely into them. Whether a given \(p(x)\) is irreducible is the practical crux; the standard tests are:

\[\underbrace{\text{rational root test}}_{\deg \le 3 \text{ over } \mathbb{Q}}, \qquad \underbrace{\text{reduction mod } p}_{\text{lift from } \mathbb{F}_p}, \qquad \underbrace{\text{Eisenstein's criterion}}_{\text{prime divides all but leading}}.\]

Extension fields via quotient rings

If \(p(x) \in F[x]\) is irreducible of degree \(k\), then \((p(x))\) is maximal and the quotient

\[K = F[x]/(p(x))\]

is a field of degree \([K:F] = k\). Every element has a unique representative \(a_0 + a_1\alpha + \cdots + a_{k-1}\alpha^{k-1}\) with \(a_i \in F\), where \(\alpha = x + (p(x))\) is a manufactured root of \(p\) inside \(K\). The prototype is \(\mathbb{R}[x]/(x^2+1) \cong \mathbb{C}\): adjoining \(i\) is nothing more than this quotient with \(x^2 + 1\). When \(F = \mathbb{F}_p\), counting representatives gives \(|K| = p^k\).

Worked construction: building \(\mathbb{F}_8\)

Take \(F = \mathbb{F}_2\) and the irreducible \(p(x) = x^3 + x + 1\) (it has no root in \(\mathbb{F}_2\), so it is irreducible in degree 3). Then \(\mathbb{F}_8 = \mathbb{F}_2[x]/(x^3+x+1)\) has the eight elements

\[\{\,0,\,1,\,\alpha,\,\alpha+1,\,\alpha^2,\,\alpha^2+1,\,\alpha^2+\alpha,\,\alpha^2+\alpha+1\,\},\]

i.e. all degree-\(<3\) polynomials in \(\alpha\) over \(\mathbb{F}_2\). Multiplication reduces modulo the relation \(\alpha^3 = \alpha + 1\) (since \(\alpha^3 + \alpha + 1 = 0\) and \(-1 = 1\) in \(\mathbb{F}_2\)). The element \(\alpha\) is a generator of \(\mathbb{F}_8^*\): its powers \(\alpha, \alpha^2, \alpha^3 = \alpha+1, \alpha^4 = \alpha^2+\alpha, \ldots\) cycle through all seven nonzero elements before returning to \(1 = \alpha^7\).

The structure theorem for finite fields

Theorem. For every prime \(p\) and integer \(k \ge 1\) there is a field of order \(p^k\), unique up to isomorphism; conversely every finite field has prime-power order. Concretely \(\mathbb{F}_{p^k}\) (also \(\text{GF}(p^k)\)) is the splitting field of \(x^{p^k} - x\) over \(\mathbb{F}_p\) — its elements are exactly the roots of

\[x^{p^k} - x = 0.\]

Two further facts do most of the downstream work: the multiplicative group \(\mathbb{F}_{p^k}^*\) is cyclic of order \(p^k - 1\) (it has a primitive element, as \(\alpha\) was for \(\mathbb{F}_8\)), and the Frobenius automorphism \(\phi:\alpha \mapsto \alpha^p\) is a field automorphism of order \(k\) generating the Galois group \(\operatorname{Gal}(\mathbb{F}_{p^k}/\mathbb{F}_p) \cong \mathbb{Z}_k\).

Application — RSA

Work in \(\mathbb{Z}_n\) with \(n = pq\) for large primes \(p, q\), so \(\phi(n) = (p-1)(q-1)\). Choose \(e\) coprime to \(\phi(n)\) and set \(d \equiv e^{-1} \pmod{\phi(n)}\). Encryption and decryption are modular exponentiation,

\[c = m^e \bmod n, \qquad m = c^d \bmod n,\]

and correctness is Euler’s theorem (Week 19’s Lagrange corollary on \(\mathbb{Z}_n^*\)): \(m^{ed} = m^{1 + t\phi(n)} \equiv m \pmod n\). Security rests on the hardness of factoring \(n\).

Application — elliptic curve cryptography

An elliptic curve over \(\mathbb{F}_p\) (\(p > 3\)) is \(E: y^2 = x^3 + ax + b\) with \(4a^3 + 27b^2 \ne 0\), together with a point at infinity \(\mathcal{O}\). The points \(E(\mathbb{F}_p)\) form an abelian group under the chord-and-tangent law: to add \(P + Q\), draw the line through them, find the third intersection with the curve, and reflect across the \(x\)-axis. For \(P \ne Q\) the slope and result are

\[\lambda = \frac{y_Q - y_P}{x_Q - x_P}, \quad x_R = \lambda^2 - x_P - x_Q, \quad y_R = \lambda(x_P - x_R) - y_P.\]

Security rests on the elliptic-curve discrete log problem (recover \(k\) from \(kP\)), believed harder than its \(\mathbb{Z}_p^*\) analogue, which is why ECC achieves comparable security at much smaller key sizes.

Application — Reed–Solomon codes

Fix \(\mathbb{F}_q\) (typically \(q = 2^8\), one symbol per byte) and distinct evaluation points \(x_1, \dots, x_n \in \mathbb{F}_q\). Encode a message \((m_0,\dots,m_{k-1})\) as the polynomial \(m(x) = \sum m_i x^i\) of degree \(< k\) and transmit its evaluations:

\[\big(m(x_1),\, m(x_2),\, \dots,\, m(x_n)\big) \in \mathbb{F}_q^{\,n}.\]

Two distinct degree-\(<k\) polynomials agree in at most \(k-1\) points, so any two codewords differ in at least \(n - k + 1\) positions — the code meets the Singleton bound with minimum distance \(d = n - k + 1\) (it is MDS) and corrects up to \(\lfloor (n-k)/2 \rfloor\) symbol errors. The whole scheme is just linear algebra and polynomial evaluation inside the finite field.

Connections

Backward: Week 19 (groups, rings, fields — the full machinery used here). Week 11 (complex analysis — \(\mathbb{C} = \mathbb{R}[x]/(x^2+1)\) is the prototype degree-2 extension). Week 15 (complexity theory — polynomial-time irreducibility testing; discrete logarithm hardness is the cryptographic assumption).
Across courses: Not tied to the applied courses, but the algebraic framework here is foundational for cryptographic systems, forward error correction in communications, and the algebraic coding theory used in storage systems.