Lectures 12 & 13: Finite Fields, Math 413 (Number Theory)

Lectures 12 & 13: Finite Fields

Number Theory, Math 413, Spring 2003


  1. An Example: GF(24)
  2. Field Extensions
  3. Properties of Finite Fields
  4. Primitive Elements & Polynomials
  5. Trace, Norm & Bases
  6. Applications
  1. References
  2. Computational Tools

In Galois Fields, full of flowers
primitive elements dance for hours
climbing sequentially through the trees
and shouting occasional parities.

The syndromes like ghosts in the misty damp
feed the smoldering fires of the Berlekamp
and high flying exponents sometimes are downed
on the jagged peaks of the Gilbert bound.

- S.B. Weinstein (IEEE Transactions on Information Theory, March 1971)


Find out about the wonderful world of GF(2k), where two is zero, plus is minus, and squaring is a linear operator. - Rick Schroeppel

Why study Finite Fields, otherwise known as Galois Fields? The subject is not commonly viewed as central to introductory number theory, and until the last 40 years was viewed as more than a little obscure.

We study finite fields first because of their practical applications. Modern communications and cryptography depend on them. The reliable generation of random numbers, public key cryptography and error correcting codes are all dependent on the theory of finite fields.

Finally, we study finite fields as a simple example of an extension field. We will eventually face more complex extensions in the guise of algebraic number fields and (time permitting) elliptic curves in the guise of function fields, but finite fields illustrate most of the features of algebraic extensions in a small and easily computable arena.

1. An Example: GF(24)

First Perspective: Theory

Consider the field GF(2)=Z2
Consider the polynomial ring GF(2)[x]
Consider the (irreducible) polynomial x4+x+1
(For convenience we may occasionally refer to this polynomial as p(x).)
Consider the ideal in the polynomial ring consisting of all multiples of our polynomial, x4+x+1⟩.
Finally, we construct the quotient ring GF(2)[x]/⟨x4+x+1⟩.
As our polynomial was irreducible this is not just a ring, but is a field. As each coset has a unique representative as a polynomial of degree less than 4, there are a total of 16=24 unique elements. Call this field GF(16), the Galois Field with 16 elements.

Second Perspective: Computation

The elements of GF(16) can be represented by the 16 polynomials with coefficients in the set {0,1} and of degree less than 4. Let's see how the usual field operations can be implemented in this representation.

Addition: Add two polynomials term by term, reducing each sum mod 2. If the two summands had degree less than 4, the result will have degree less than 4.
(a3x3 +a2x2 +a1x+a0) + (b3x3 +b2x2 +b1x+b0) = ((a3+b3)x3 +(a2+b2)x2 +(a1+b1)x +(a0+b0))
(x2+x+1) + (x3+x2+1) = ((0+1)x3+(1+1)x2+(1+0)x+(1+1)1) = (x3+x)

Multiplication: Multiply two polynomials in the usual way, collecting coeffients and reducing them mod 2. Recall that in our quotient field p(x) = x4+x+1 = 0. Thus x4 = -x-1 = x+1 (as coefficients are mod 2 plus and minus are the same). If any terms have degree 4 or greater, replace them with sums of lower degree terms using the following rules:
x4 = x+1
x5 = x2+x
x6 = x3+x2
x7 = x4+x3 = (x+1)+x3 = x3 + x+1
etc
An Example:
(x2+x+1) (x3+x2+1)
= x5 + 2x4 + 2x3 + 2x2 + x + 1
= x5 + x + 1
= (x2+x) + x + 1 = x2 + 2x + 1 = x2 + 1

Inverse: We can compute inverses using the extended Euclidean Algorithm in the polynomial ring. If we want to find the inverse of an element a(x) we want to find some element b(x) such that:
a(x)b(x) ≡ 1 (mod p(x))
a(x)b(x) = 1 + k(x)p(x) (for some k(x))
a(x)b(x) - k(x)p(x) = 1
Given values for a(x) and p(x) the extended Euclidean Algorithm will compute values for b(x) (which will be the desired inverse of a(x)) and k(x) (a probably irrelevant by-product).
An Example:
a(x) p(x) x2+1 x4+x+1 1 0 0 1
x2+1 x4+x+1-(x2+1)(x2+1)=x 1 0 0-(x2+1)1=x2+1 1-(x2+1)0=1
(x2+1)-(x)(x)=1 x 1-(x)(x2+1)=x3+x+1 0-(x)1=x x2+1 1
Thus the inverse of x2+1 is x3+x+1

Primitive Elements: In this particular case we see that the element represented by x is primitive, having multiplicative order 15:
x0 = 1
x1 = x
x2 = x2
x3 = x3
x4x+1
x5 = xx4x2+x
x6 = xx5x3+x2
x7 = xx6x4+x3x3+x+1
x8 = xx7x4+x2+xx2+1
x9 = xx8x3+x
x10 = xx9x4+x2x2+x+1
x11 = xx10x3+x2+1
x12 = xx11x4+x3+x2x3+x2+x+1
x13 = xx12x4+x3+x2+xx3+x2+1
x14 = xx13x4+x3+xx3+1
x15 = xx14x4+x ≡ 1

The powers of the element x are often implemented as the circuit:
Circuit implementing x^4+x+1
The sequence produced by this generator is the same as the sequence of constant terms in the powers of x and is often used as a pseudo-random sequence of bits.

2. Field Extensions

Defn: If E and F are fields and F is a subfield of E, then E is an extension of F. F is called the base field of the extension.

Defn: A prime field is a field which contains no subfields except itself (i.e. no proper subfields). Given a field F, the prime subfield of F is the intersection of all subfields of F.

Defn: The characteristic of a field is the additive order of 1 in that field. In other words, the characteristic is the smallest positive integer n such that the sume of n copies of 1 is zero: 1+...+1=0.

Thm: The prime subfield of any field F is isomorphic to either Zp or Q, depending on whether the characteristic of F is finite or infinite. (L&N,1.78)

Defn: A simple extension of a field F is field all of whose elements are polynomial expressions of elements of F and some new element, α, called the defining element. A simple extension is denoted F[α].

Examples:

Defn: An algebraic extension of a field F is an extension such that for every element α in the extension there is a polynomial p(x)∈F[x], such that p(α)=0. The monic polynomial of least degree having α as a zero is called the minimal polynomial of α, and is denoted mα(x). The degree of α is the degree of mα(x), and the degree of an extension is this maximum (if any) of the degrees of the elements. A finite extension is an extension of finite degree (not, as one would naturally think, an extension which is a finite field).

Examples:

Observations:

  1. All extensions are vector spaces over their base field.
  2. A finite extension, viewed as a vector spaces over its base field, has a dimension equal to its degree as an extension.
  3. All finite extensions are algebraic.

Thm: (L&N 1.86) F is an extension field of K, and θ∈F is algebraic over K of degree n.

  1. K[θ] ≅ K[x]/⟨mθ(x)⟩
  2. The dimension of K[θ] over K (as a vector space) is n, and {1,θ,...,θn-1} is a basis.
  3. If α∈K[θ] then α is algebraic over K and the degree of α divides n

GF(26) = Z2[α]/⟨α6+α+1⟩

Example:
GF64 as extensions of GF2, GF4 and GF8

GF(23) is an embedded subfield of GF(26)
As (26-1)/(23-1)=9 we have GF(23)=⟨α9⟩. Let β=α9
Note that mβ(x) = x3+x2+1
Thus GF(23)= Z2[β]/⟨β32+1⟩
(Also note the relative minimum polynomial: mα[GF(26):GF(23)](x) = x23x+β, as α23α+β=0.
Thus GF(26) = GF(23)[α]/⟨α23α+β⟩
(Not to self: This should be easy to compute - need to figure out efficient algorithm)

GF(22) is an embedded subfield of GF(26)
As (26-1)/(22-1)=21 we have GF(23)=⟨α21⟩. Let γ=α21
Note that mγ(x) = x2+x+1
Thus GF(22)= Z2[γ]/⟨γ2+γ+1⟩

3. Properties of Finite Fields

Texts: [LN97, Sects 2.1]

Thm: (L&N, 2.2) A Finite Field has order pn, for some prime p and some integer n.
proof: (outline) Prime field is Zp for some prime p
The extension is finited, hence algebraic
FF is a vector field over Zp of some degree/dimension n
Hence the FF has pn elements.

Lemma: (L&N 2.3) If α∈GF(q) then αq ≡ α (Fermat's Little Thm for finite fields)
proof: (outline) If α=0 the result is immediate.
If α≠0, then we can either note that GF\0 is a group of order q and cite Lagrange's Thm, or use the same mechanism as we used to prove Fermat's Little Thm.

Lemma: (L&N 2.4) xq-x factors over GF(q)[x] as ∏α∈GF(x-a) and GF(q) is the splitting field for xq-x

Thm: (L&N 2.5) For p prime and n>0 there is a unique field with pn elements.
proof: Existence: see construction above
Uniqueness: Consider a field F with pn elements
The characteristic of F is p, so Ap is a subfield of F
Thus F is the (unique) splitting field of xq-x
(need a better proof - perhaps something allowing an explicit isomorphism - minimal polynomials.

Thm: If F has characteristic p, then (α+β)p = αpp (aka Freshman's Dream)
proof: Properties of Binomial Coefficients

Frobenius Automorphism: Consider the map φ:GF(pn) → GF(pn) given by φ:α → αp
We note that φ(αβ) = (αβ)p = αpβp = φ(α)φ(β) and φ(α+β) = (α+β)p = αpp = φ(α)+φ(β). Thus φ is an automorphism of the field GF(pn). We also note that φ is the identity on the prime field GF(p) (Fermat's Little Thm for FF).
We call φ the Frobenius Automorphism.
(Note [beyond the scope of the course]: We see that φ is an element in the relative Galois group Gal(GF(pn)/GF(p)). In fact, this Galois group (and all the relative Galois groups of finite fields) is cyclic, and is generated by the Frobenius Automorphism: Zp ≅ Gal = ⟨φ⟩.)

Thm: (L&N 2.6) (Subfield Criterion)

  1. Every subfield of GF(pn) has form GF(pk), where k is a divisor of n
  2. If k is a divisor of n there is one subfield of GF(pn) which is isomorphic to GF(pk)

4. Primitive Elements & Polynomials

Thm: (L&N 2.8) The multiplicative group of units of GF(q) (i.e. all non-zero elements, also denoted GF(p)*) is cyclic.

Defn: A degree n polynomial q(x) ∈ Zp[x] is said to be primitive if x generates the group of units in GF(pn) ≅ Zp/⟨q(x)⟩.
(This definition comes from the coding theory and communications engineering worlds. Thus q(x) is primitive in this sense iff x is primitive in the conventional number theoretic sense.)

Example: Consider the representation of GF(26) with minimal polynomial x6+x4+x2+x+1 Compute the order of the element represented by x in this field. We could do this the hard way, running out the powers of x, as far as 63=26-1, or we could do the same thing as we do when looking for powers of numbers modulo some number N. Our approach is to consider the possible orders as divisors of 63, and use our binary exponentiation techniques to check them. Note that 63 = 327, so we first check the powers 21=63/3 and 9=63/7.
x21 ≡ 1
x7x5+x3+x2+x
So the order of x divides 21. As x3 is obviously not 1, and we have already checked x7, we know that the multiplicative order of x is 21. Thus x does not represent a primitive element in the cyclic group of units in this representation of GF(26).

5. Trace, Norm & Bases

[LN97, Sect 2.3]

6. Applications

LRS, Random Number Sequences

[Schr97, Sects 25.3 & 25.5] [LN97, Chap 8]

Cyclic Linear Codes

[LN97, Sects 9.1-9.2] [Chil95, Sects 29.B-29.C]

A. References

[Schr97] Number Theory in Science and Communication, 3rd Ed, M. Schroeder, Springer, 1997 (also in earlier editions)

B. Computational Tools

Maple

GF package: readlib(GF); http://euler.slu.edu/courseware/AbstractAlgebra/AlgebraOverviewR4.html

Mathematica

The package FinFld.ma allows simple computations in finite fields.

% math
In[1]:= <<FinFlds.ma
In[2]:= gf16=CreateFinFld[x^4+x+1,x,2]
Out[2]= GF(2^4)
In[6]:= a=ElementFinFld[x,gf16]
Out[6]= (x)
           GF(2^4)
In[7]:= (a^2+a)+(a^2+a+1)
Out[7]= (1)
           GF(2^4)
In[8]:= (a^2+1)*(a^2+a+1)
          3
Out[8]= (x )
            GF(2^4)
In[9]:= (a^2+1)^(-1)
                  3
Out[9]= (1 + x + x )
                    GF(2^4)
In[10]:= a^15
Out[10]= (1)
            GF(2^4)
In[15]:= (a^2+a)^3
Out[15]= (1)
            GF(2^4)

Magma

Very good FF functionality, but not free, not available at UMBC.

NTL

C++ Library with class for char 2 FF (GF2E), char p FF (ZZ_pE)

PARI/GP

http://www.parigp-home.de/lists/200012/20aab Some ability to do FF, but not ready for prime time.
Robert Campbell, campbell@math.umbc.edu
26 Jan, 2003