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.
Consider the field GF(2)=Z_{2}
Consider the polynomial ring GF(2)[x]
Consider the (irreducible) polynomial
(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,
Finally, we construct the quotient ring
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=2^{4} unique elements. Call this field
GF(16), the Galois Field with 16 elements.
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).
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: [LN97, 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}).
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.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html
]