Finite Fields

Study Sheet

Finite Fields

Fields with p^n elements: their sizes, cyclic multiplicative groups, subfields and irreducible polynomials

The Size of a Finite Field

Concept
Every finite field has pnp^n elements

A finite field has prime characteristic pp, contains Zp\mathbb Z_p, and is a vector space of some dimension nn over it — so it has exactly pnp^n elements. Conversely, for every prime power q=pnq=p^n there is a field with qq elements, unique up to isomorphism, written Fq\mathbb F_q or GF(q)GF(q).

This is a complete classification: one field for each prime power, none for any other size. To build Fpn\mathbb F_{p^n}, take any irreducible polynomial of degree nn over Zp\mathbb Z_p and form Zp[x]/(p(x))\mathbb Z_p[x]/(p(x)) as in the previous topics. Different irreducible polynomials give the same field up to a relabeling of its elements.

Example
Building F8\mathbb F_8

x3+x+1x^3+x+1 is irreducible over Z2\mathbb Z_2 (no root), so F8=Z2[x]/(x3+x+1)\mathbb F_8=\mathbb Z_2[x]/(x^3+x+1), with α3=α+1\alpha^3=\alpha+1. The powers of α\alpha are α, α2, α3=α+1, α4=α2+α, α5=α2+α+1, α6=α2+1, α7=1\alpha,\ \alpha^2,\ \alpha^3=\alpha+1,\ \alpha^4=\alpha^2+\alpha,\ \alpha^5=\alpha^2+\alpha+1,\ \alpha^6=\alpha^2+1,\ \alpha^7=1: all seven nonzero elements.

Example
No field with 66 elements

6=2⋅36=2\cdot3 is not a prime power, so no field has 66 elements. Indeed, such a field would have characteristic 22 or 33 and would be a vector space over Z2\mathbb Z_2 or Z3\mathbb Z_3, so its size would be a power of 22 or of 33.

Side note
Where it goes wrong

The field with 44 elements is NOT Z4\mathbb Z_4: in Z4\mathbb Z_4, 2⋅2=02\cdot2=0, so Z4\mathbb Z_4 is not even an integral domain. F4\mathbb F_4 is Z2[x]/(x2+x+1)\mathbb Z_2[x]/(x^2+x+1), which has characteristic 22 (1+1=01+1=0) — a completely different ring.

Try it
Try it: possible sizes

Which of 6,7,8,9,10,12,16,276,7,8,9,10,12,16,27 are sizes of finite fields?

Show the answer

The prime powers: 7,8,9,16,277,8,9,16,27 — five of them. (6,10,126,10,12 have two different prime factors.)

The Multiplicative Group Is Cyclic

Concept
Primitive elements

The nonzero elements of Fq\mathbb F_q form a CYCLIC group of order q−1q-1 under multiplication. A generator is called a primitive element; there are exactly φ(q−1)\varphi(q-1) of them. In Zp\mathbb Z_p, primitive elements are the primitive roots mod pp.

This brings the group theory of the first half straight into fields: Fq×≅Zq−1\mathbb F_q^\times\cong\mathbb Z_{q-1}, so everything known about cyclic groups applies — the number of elements of each order, the subgroups, and the powers. Every nonzero element is a power of a primitive element, which makes multiplication in a finite field as easy as adding exponents mod q−1q-1.

Example
33 is a primitive root mod 77

The powers of 33 mod 77 are 3,2,6,4,5,13,2,6,4,5,1: all six nonzero residues. So 33 generates Z7×\mathbb Z_7^\times, and there are φ(6)=2\varphi(6)=2 primitive roots in all (33 and 55).

Example
Counting primitive elements

F8×\mathbb F_8^\times has order 77, a prime, so every element except 11 is primitive: φ(7)=6\varphi(7)=6. F9×\mathbb F_9^\times has order 88, with φ(8)=4\varphi(8)=4 primitive elements. In Z11\mathbb Z_{11} the primitive roots are 2,6,7,82,6,7,8 — φ(10)=4\varphi(10)=4 of them.

Side note
Where it goes wrong

The ADDITIVE group of Fq\mathbb F_q is usually not cyclic: in F4\mathbb F_4, every element satisfies a+a=0a+a=0, so the additive group is Z2×Z2\mathbb Z_2\times\mathbb Z_2. It is the MULTIPLICATIVE group of nonzero elements that is always cyclic.

Try it
Try it: a primitive root

Is 22 a primitive root mod 1111?

Show the answer

Its powers mod 1111: 2,4,8,5,10,9,7,3,6,12,4,8,5,10,9,7,3,6,1 — all ten nonzero residues appear, so yes.

Subfields of a Finite Field

Concept
Subfields correspond to divisors

The subfields of Fpn\mathbb F_{p^n} are exactly the fields Fpm\mathbb F_{p^m} with m∣nm\mid n, one for each divisor mm. So Fpn\mathbb F_{p^n} has d(n)d(n) subfields, where d(n)d(n) is the number of divisors of nn.

This follows from the tower law: if Fpm⊆Fpn\mathbb F_{p^m}\subseteq\mathbb F_{p^n} then n=m⋅[Fpn:Fpm]n=m\cdot[\mathbb F_{p^n}:\mathbb F_{p^m}], so m∣nm\mid n. Conversely the elements with apm=aa^{p^m}=a form a subfield of size pmp^m whenever m∣nm\mid n. The subfield lattice of Fpn\mathbb F_{p^n} is therefore the divisor lattice of nn.

Example
Subfields of F64\mathbb F_{64}

64=2664=2^6, and the divisors of 66 are 1,2,3,61,2,3,6. So F64\mathbb F_{64} has exactly 44 subfields: F2,F4,F8,F64\mathbb F_2,\mathbb F_4,\mathbb F_8,\mathbb F_{64}.

Example
F8\mathbb F_8 is not inside F16\mathbb F_{16}

16=2416=2^4 and 8=238=2^3, but 3∤43\nmid4. So F16\mathbb F_{16} does not contain F8\mathbb F_8, even though both have characteristic 22 and 8<168<16.

Side note
Where it goes wrong

Containment depends on the EXPONENT dividing, not the size: F4⊆F16\mathbb F_4\subseteq\mathbb F_{16} (2∣42\mid4), but F8⊈F16\mathbb F_8\not\subseteq\mathbb F_{16}. And fields of different characteristics never contain one another.

Try it
Try it: count subfields

How many subfields does F312\mathbb F_{3^{12}} have?

Show the answer

One for each divisor of 1212: 1,2,3,4,6,121,2,3,4,6,12 — 6\mathbf6 subfields.

Counting Irreducible Polynomials

Concept
The polynomial xpn−xx^{p^n}-x

Over Zp\mathbb Z_p, xpn−xx^{p^n}-x is the product of ALL monic irreducible polynomials whose degree divides nn, each appearing once. Comparing degrees: if Np(d)N_p(d) is the number of monic irreducible polynomials of degree dd, then ∑d∣nd Np(d)=pn\sum_{d\mid n}d\,N_p(d)=p^n.

The roots of xpn−xx^{p^n}-x are exactly the pnp^n elements of Fpn\mathbb F_{p^n}, each once. Every such element has a minimal polynomial over Zp\mathbb Z_p, irreducible of degree dividing nn, and grouping the roots by minimal polynomial gives the factorization. The degree identity lets you count irreducible polynomials recursively.

Example
x8−xx^8-x over Z2\mathbb Z_2

The divisors of 33 are 11 and 33, so x8−x=x(x+1)(x3+x+1)(x3+x2+1)x^8-x=x(x+1)(x^3+x+1)(x^3+x^2+1): the two irreducibles of degree 11 and the two of degree 33. Degree check: 1+1+3+3=81+1+3+3=8.

Example
Counting irreducible quartics over Z2\mathbb Z_2

For n=4n=4: 1⋅N(1)+2N(2)+4N(4)=161\cdot N(1)+2N(2)+4N(4)=16. With N(1)=2N(1)=2 and N(2)=1N(2)=1: 2+2+4N(4)=162+2+4N(4)=16, so N(4)=3N(4)=3. For n=5n=5: N(1)+5N(5)=32N(1)+5N(5)=32, so N(5)=32−25=6N(5)=\frac{32-2}5=6.

Side note
Where it goes wrong

Do not divide pnp^n by nn directly: the elements of smaller subfields have minimal polynomials of smaller degree and must be removed first. For p=2p=2, n=4n=4: 164=4\frac{16}4=4, but the correct count is 33.

Try it
Try it: irreducible quadratics over Z3\mathbb Z_3

How many monic irreducible quadratics are there over Z3\mathbb Z_3?

Show the answer

N(1)+2N(2)=9N(1)+2N(2)=9 with N(1)=3N(1)=3, so N(2)=3N(2)=\mathbf3 (they are x2+1x^2+1, x2+x+2x^2+x+2, x2+2x+2x^2+2x+2).

Why It Works

A finite field FF has prime characteristic pp (characteristic 00 would make 1,1+1,…1,1+1,\ldots all different). The multiples of 11 form a copy of Zp\mathbb Z_p, and FF is a vector space over it of some finite dimension nn. A basis of nn vectors gives pnp^n possible coefficient choices, one for each element.

Let G=Fq×G=\mathbb F_q^\times, of order m=q−1m=q-1. For each d∣md\mid m, the elements of order dd are roots of xd−1x^d-1, which has at most dd roots; if one element aa of order dd exists, its powers already give dd roots, so the elements of order dd are among ⟨a⟩\langle a\rangle, and there are exactly φ(d)\varphi(d) of them. So the number of elements of order dd is 00 or φ(d)\varphi(d). Since ∑d∣mφ(d)=m\sum_{d\mid m}\varphi(d)=m, every count must be φ(d)\varphi(d) — in particular there are φ(m)>0\varphi(m)>0 elements of order mm.

If K=FpmK=\mathbb F_{p^m} sits inside F=FpnF=\mathbb F_{p^n}, then FF is a vector space over KK of some dimension kk, so pn=(pm)kp^n=(p^m)^k and n=mkn=mk.