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(2^{k}), 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.
(A suspicious mind might note the arbitrary choice of irreducible degree 4 polynomial and wonder if the choice mattered. The answer (up to isomorphism) is no, but proving that would take more work than we are willing to exert.)
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.
(x^{2}+x+1) +
(x^{3}+x^{2}+1) =
Multiplication: Multiply two polynomials in the usual
way, collecting coeffients and reducing them mod 2.
Recall that in our quotient field
x^{4} = x+1
x^{5} = x^{2}+x
x^{6} = x^{3}+x^{2}
x^{7} = x^{4}+x^{3}
= (x+1)+x^{3} = x^{3} + x+1
etc
An Example:
(x^{2}+x+1)
(x^{3}+x^{2}+1)
= x^{5} + 2x^{4}
+ 2x^{3} + 2x^{2}
+ x + 1
= x^{5} + x + 1
= (x^{2}+x) + x + 1
= x^{2} + 2x + 1 = x^{2} + 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)
x^{2}+1 x^{4}+x+1 1 0 0 1
x^{2}+1 x^{4}+x+1-(x^{2}+1)(x^{2}+1)=x 1 0 0-(x^{2}+1)1=x^{2}+1 1-(x^{2}+1)0=1
(x^{2}+1)-(x)(x)=1 x 1-(x)(x^{2}+1)=x^{3}+x+1 0-(x)1=x x^{2}+1 1
Thus the inverse of x^{2}+1 is x^{3}+x+1
Primitive Elements: In this particular case we see that
the element represented by x is primitive, having
multiplicative order 15:
x^{0} = 1
x^{1} = x
x^{2} = x^{2}
x^{3} = x^{3}
x^{4} ≡ x+1
x^{5} = xx^{4} ≡ x^{2}+x
x^{6} = xx^{5} ≡ x^{3}+x^{2}
x^{7} = xx^{6} ≡ x^{4}+x^{3} ≡ x^{3}+x+1
x^{8} = xx^{7} ≡ x^{4}+x^{2}+x ≡ x^{2}+1
x^{9} = xx^{8} ≡ x^{3}+x
x^{10} = xx^{9} ≡ x^{4}+x^{2} ≡ x^{2}+x+1
x^{11} = xx^{10} ≡ x^{3}+x^{2}+1
x^{12} = xx^{11} ≡ x^{4}+x^{3}+x^{2} ≡ x^{3}+x^{2}+x+1
x^{13} = xx^{12} ≡ x^{4}+x^{3}+x^{2}+x ≡ x^{3}+x^{2}+1
x^{14} = xx^{13} ≡ x^{4}+x^{3}+x ≡ x^{3}+1
x^{15} = xx^{14} ≡ x^{4}+x ≡ 1
The powers of the element x are often implemented as
the circuit:
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.
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 Z_{p} 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).
Defn: If E is an extension of F, then the Galois group, G is the set of automorphisms of E which fix F, made into a group with the operation of composition of automorphisms.
Defn: If E is an extension of F with Galois group G, then if φ∈G and α∈E, we say that φ(α) is a conjugate of α.
Examples:
Observations:
Thm: (L&N 1.86) F is an extension field of K, and θ∈F is algebraic over K of degree n.
GF(2^{6}) = Z_{2}[α]/⟨α^{6}+α+1⟩
Example:
GF(2^{3}) is an embedded subfield of GF(2^{6})
As (2^{6}-1)/(2^{3}-1)=9 we have
GF(2^{3})=⟨α^{9}⟩. Let β=α^{9}
Note that m_{β}(x) = x^{3}+x^{2}+1
Thus GF(2^{3})= Z_{2}[β]/⟨β^{3}+β^{2}+1⟩
(Also note the relative minimum polynomial: m_{α}[GF(2^{6}):GF(2^{3})](x) = x^{2}+β^{3}x+β, as α^{2}+β^{3}α+β=0.
Thus GF(2^{6}) = GF(2^{3})[α]/⟨α^{2}+β^{3}α+β⟩
(Not to self: This should be easy to compute - need to figure out efficient algorithm)
GF(2^{2}) is an embedded subfield of GF(2^{6})
As (2^{6}-1)/(2^{2}-1)=21 we have
GF(2^{3})=⟨α^{21}⟩. Let γ=α^{21}
Note that m_{γ}(x) = x^{2}+x+1
Thus GF(2^{2})= Z_{2}[γ]/⟨γ^{2}+γ+1⟩
Texts: [LN83, Sects 2.1]
Thm: (L&N, 2.2) A Finite Field has order
p^{n}, for some prime p
and some integer n.
proof: (outline) Prime field is Z_{p}
for some prime p
The extension is finited, hence algebraic
FF is a vector field over Z_{p} of some
degree/dimension n
Hence the FF has p^{n} 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) x^{q}-x factors over GF(q)[x] as ∏_{α∈GF}(x-a) and GF(q) is the splitting field for x^{q}-x
Thm: (L&N 2.5) For p prime and n>0
there is a unique field with p^{n}
elements.
proof: Existence: see construction above
Uniqueness: Consider a field F with
p^{n} elements
The characteristic of F is p, so
A_{p} is a subfield of F
Thus F is the (unique) splitting field of
x^{q}-x
(need a better proof - perhaps something allowing an
explicit isomorphism - minimal polynomials.
Thm: If F has characteristic p, then
proof: Properties of Binomial Coefficients
Frobenius Automorphism: Consider the map
φ:GF(p^{n})
→ GF(p^{n})
given by φ:α → α^{p}
We note that
We call φ the Frobenius Automorphism.
(Note [beyond the scope of the course]:
We see that φ is an element in the relative Galois
group
Thm: (L&N 2.6) (Subfield Criterion)
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
(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(2^{6}) with minimal polynomial
x^{21} ≡ 1
x^{7} ≡ x^{5}+x^{3}+x^{2}+x
So the order of x divides 21. As x^{3} is
obviously not 1, and we have already checked x^{7}, 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(2^{6}).
Defn: If GF(p^{n}) is considered as a extension of GF(p) and α∈GF(p^{n}), then the conjugates of α are the elements {α^{pi} | i=0,...,n}.
[Actually, this is simply the application of the earlier general definition of conjugate to the case of finite fields.]
Defn: The trace of α, denoted tr(α), is the sum of its conjugates. [If α∈GF(p^{n}), considered as an extension of GF(p), then the trace of α is ∑_{i=0,...,n-1}α^{pn}.]
Defn: The norm of α, denoted N(α), is the product of its conjugates. [If α∈GF(p^{n}), considered as an extension of GF(p), then the norm of α is ∏_{i=0,...,n-1}α^{pn}.]
Note that the conjugates of α all have the same trace and norm as α.
Thm: tr(α+β) = tr(α) + tr(β)
proof: Freshman's Dream (see above)
Thm: N(αβ) = N(α)N(β)
proof: Properties of exponents
Example: Recall the construction
GF(2)[x]/⟨x^{4}+x+1⟩.
Compute tr(1) = ∑1^{2i}
= 1^{20}+1^{21}
+1^{22}+1^{23}=1+1+1+1=0
Compute tr(x) = ∑x^{2i}
= x^{20}
+x^{21}
+x^{22}
+x^{23}
=x+x^{2}+(x+1)+(x^{2}+1) = 0
Compute tr(x^{3}) = ∑(x^{3})^{2i}
= (x^{3})^{20}
+(x^{3})^{21}
+(x^{3})^{22}
+(x^{3})^{23}
=(x^{3})+(x^{6})+(x^{12})+(x^{24}=x^{9}) =(x^{3})+(x^{3}+x^{2})+(x^{3}+x^{2}+x+1)+(x^{3}+x) = 1
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)
http://www.sagemath.org
sage: FF16.<a> = GF(2^4,'a') sage: a^4 a + 1
http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html
]