Skip to content
Tutorials Center
My learning

Topics

Lesson 30 of 37 · Fields and Polynomial Rings

Finite Fields

Construct finite fields GF(4), GF(8) and GF(16) as quotients of Z_p[x] by an irreducible polynomial and verify the field axioms and primitive elements in Python.

You know one family of finite fields: ℤₚ for a prime p. Are there others, such as a field with exactly 4 elements? ℤ₄ is not one, because 2 · 2 = 0. Yet a field with 4 elements does exist, and the construction is the same quotient trick you have already seen: take ℤₚ[x] and divide out by an irreducible polynomial.

The construction

Let p be prime and let f be an irreducible polynomial of degree n in ℤₚ[x]. Then ℤₚ[x]/(f) is a field. Its elements are the cosets of polynomials of degree less than n, so it has exactly pⁿ elements:

Text
GF(pⁿ) = ℤₚ[x] / (f)       with  p^n elements

Every coset has a unique representative a₀ + a₁x + ... + aₙ₋₁xⁿ⁻¹ with each aᵢ in ℤₚ, because division with remainder by f leaves a remainder of degree below n. Addition is coefficient-wise (mod p). Multiplication is polynomial multiplication followed by reduction modulo f.

Example: GF(4)

Use p = 2 and f = x² + x + 1, the only irreducible quadratic over ℤ₂. Write α for the class of x. Then α² + α + 1 = 0, so α² = α + 1 (since -1 = 1 in ℤ₂). The four elements are 0, 1, α, α + 1. Because α² = α + 1, we get α³ = α · α² = α² + α = (α + 1) + α = 1. So α has multiplicative order 3, and the nonzero elements are 1, α, α².

Let's code a general finite field class for GF(pⁿ) and print the tables for GF(4).

Python GF(p^n) from scratch, with the GF(4) tables

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The multiplication table has no 0 entries outside the row and column of 0, so there are no zero divisors, and every nonzero element appears once in each row: it is a field.

Example: GF(8) and primitive elements

For GF(8) we need an irreducible cubic over ℤ₂. Two of them exist: x³ + x + 1 and x³ + x² + 1. The multiplicative group GF(8)× has 7 elements. Since 7 is prime, every nonidentity element generates it. Such a generator is called a primitive element.

A deep theorem says that the multiplicative group of every finite field is cyclic. So GF(pⁿ)× is cyclic of order pⁿ - 1, and there are φ(pⁿ - 1) primitive elements.

The program below builds GF(8) and GF(16), lists the powers of α and checks the field axioms exhaustively.

Python GF(8) and GF(16): powers of alpha and the field axioms

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Facts about finite fields

  • Every finite field has pⁿ elements for a prime p (its characteristic) and n ≥ 1.
  • For each prime power pⁿ there is a field with that many elements, and it is unique up to isomorphism. Different irreducible polynomials give isomorphic fields, written GF(pⁿ) or 𝔽_{pⁿ}.
  • GF(pᵐ) is a subfield of GF(pⁿ) exactly when m divides n.
  • Frobenius: a ↦ aᵖ is a field automorphism of GF(pⁿ), and (a + b)ᵖ = aᵖ + bᵖ.
  • Every element satisfies a^(pⁿ) = a.

There is no field of 6 elements, because 6 is not a prime power. There is also none with 10 or 12 elements.

GF(4) and ℤ₄ are completely different rings: in ℤ₄ we have 2 · 2 = 0, but in GF(4) the product of nonzero elements is never zero. The number of elements alone does not tell you the structure.

Finite fields drive modern error-correcting codes and cryptography. Before that, one more tool: field extensions explain why the constructions above are natural.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. How many elements does Z2[x]/(x^3 + x + 1) have?

    Remainders have degree below 3, so there are 2 choices for each of 3 coefficients: 2^3 = 8.
  2. 2. Which of these orders can a finite field have?

    Finite field orders are prime powers; 16 = 2^4. The others are not prime powers.
  3. 3. The multiplicative group of GF(16) is...

    The nonzero elements of any finite field form a cyclic group.
  4. 4. In GF(4) = Z2[x]/(x^2 + x + 1), the class a of x satisfies...

    From a^2 + a + 1 = 0 and -1 = 1 in Z2 we get a^2 = a + 1.

Summary

  • If f is irreducible of degree n over ℤₚ, then ℤₚ[x]/(f) is a field with pⁿ elements.
  • Elements are polynomials of degree below n; addition is coefficient-wise and multiplication is reduced modulo f.
  • The nonzero elements form a cyclic group of order pⁿ - 1; its generators are primitive elements.
  • A field with q elements exists iff q is a prime power, and it is unique up to isomorphism.
  • GF(4) is not ℤ₄.

Next: Field Extensions