EE 229B ERROR CONTROL CODING Spring 2005

Lecture notes on finite fields

Venkat Anantharam
(based on scribe notes by Rohit Puri, Aaron Wagner, Anand Raghavan, Payam Pakzad, and Marc
Ibanez)

Warning : Use at your own risk ! These notes have not been sufficiently carefully screened.

1 Characteristic and size of a finite field

We first prove the following :
Fact : For a finite field F, there is a prime p and an integer m ≥ 1 such that |F | = pm .
Subsequently, we will focus on the case p = 2.
Definition: Characteristic of F : Consider (1, 1+1, 1+1+1, . . .). Since F is finite, we must have,

1| + 1 +{z. . . + 1} = |1 + 1{z
. . . + 1} (1)
k l

for some l > k. This means |1 + 1 +{z. . . + 1} = 0, and l − k > 0. There must therefore be a
l−k
smallest m > 0 s.t. |1 + 1 +{z. . . + 1} = 0.
m
Lemma: m must be a prime number ≥ 2.
Proof: Since 1 6= 0 we have m ≥ 2. Suppose m = m1 · m2 where m1 > 1, m2 > 1.
Then, |1 + 1 +{z. . . + 1} = (1
|
+ 1 +{z. . . + 1}) · (1
|
+ 1 +{z. . . + 1}). But L.H.S equals 0 which implies that
m m1 m2
at least one of the R.H.S terms equals 0, which is a contradiction. Hence m must be a prime
number. This is called the characteristic of the field. We denote it by p from now on.
Note that the set {1, 1 + 1, 1 + 1 + 1, . . . 1| + 1 +{z. . . + 1}, 0}, which is a subset of F, is itself a
p−1
field with the operations of F, and in fact is just a copy of GF(p). This is because the product of
two sums of 1’s is also a sum of 1’s. We can view the set F as a vector space over GF(p) as follows:
Vector Addition: To define the vector addition we need to describe how to add elements of F. We
take this addition operation to be the same as one already defined for F when it is viewed as a
field.
Scalar Multiplication: Given k  GF (p), x  F , we want to define k · x  F . k · x is defined as
(1
|
+ 1 +{z. . . + 1}) · x, where the operation on the R.H.S. is just the field multiplication, which is
k
already defined in F.
It is straightforward to verify that the properties required of vector addition and scalar multipli-
cation are satisfied by the definitions we just made and so we have indeed described F as a vector
space over GF (p). Now note that we have proved that |F | = pm for some m ≥ 1 ! Indeed, m here
is the dimension of F viewed as a vector space over GF(p). F must have such a dimension and
since pm is the total number of distinct linear combinations of m linearly independent basis vectors
in a vector space over the field GF(p), it follows that F must have exactly pm elements.

1
 . 0 1 α α2
0 0 0 0 0
1 0 1 α α2
α 0 α α2 1
α2 0 α2 1 α

+ 0 1 α α2
0 0 1 α α2
1 1 0 α2 α
α α α2 0 1
α2 α2 α 1 0

2 Field of characteristic 2
From now on we restrict ourselves to fields of characteristic 2. So far we have learned that if there
exists a field of characteristic 2, then we must have |F | = 2m for some m ≥ 1. We will construct
such a field for every m. This is of importance in coding theory.
For m = 1, we know an F exists, namely GF(2) = {0, 1}. Let us try to construct such a field
for m = 2. Here the set F is {0, 1, α, }. Consider α · α. Now α · α 6= 0 (else α = 0), α · α 6= α (else
α = 1). α · α = 1 is possible. But in this case, let the fourth element be β. Then β · α 6= 0 (else
β = 0 or α = 0). Moreover β · α 6= 1 (else β = α, because we already assumed that α · α = 1),
β · α 6= α (else β = 1) and β · α 6= β (else α = 1). Thus α · α = 1 is not possible. Hence α · α must
be the fourth element of the field. Denote it by α2 . We can verify that addition and multiplication
tables for this field are as above.
In coming up with the above tables we used the identity α2 = 1 + α. This identity must hold
because 1 + α 6= 0 (else α = 1), 1 + α 6= 1 (else α = 0), and 1 + α 6= α (else 1 = 0). The only
remaining choice is 1 + α = α2 .
The calculations done above involve powers of α. This is like dealing with polynomials in α.
Indeed, all that is going on is that any power of α bigger than 2 can be replaced by a polynomial in α
of degree at most 1, using the identity α2 = 1+α. Using this observation, it can be verified that the
addition and multiplication tables are consistent with addition and multiplication of polynomials in
α and so all the necessary properties of a field, including the less obvious ones such as distributivity
of multiplication over addition can be seen to hold.
Note that if the elements {0, 1, α, α2 } are mapped respectively to two bit symbols {00,01,10,11}
then the addition tables just correspond to bitwise addition. The multiplication tables are somewhat
more strange, but the thing to focus on is that they come from using the relation 1 + α = α2 .

3 Finite Fields through polynomials

The set of polynomials over GF(2) is denoted GF(2)[X] :

2
 {a0 + a1 · X . . . + ad · X d ; d ≥ 0; a0 , a1 , . . . ad  {0, 1}}
We can add and multiply as usual with coefficients added and multiplied as in GF(2).
e.g, (X 2 + X + 1) · (X 4 + X 2 + 1) = X 6 + X 5 + X 3 + X + 1.
Definition: A polynomial over GF(2) is called irreducible over GF (2) if it has no non-trivial fac-
tors, e.g,
Reducible : X 2 + 1 = (X + 1)(X + 1) so X 2 + 1 is reducible.
Irreducible : X 2 + X + 1 is irreducible (because neither 0 nor 1 is a root). X 3 + X + 1 and also
X 3 + X + 1 are irreducible (in each case, at least one of the factors would have degree 1 but these
polynomials have no roots in GF(2)).
Also consider X 4 + X + 1. It has no roots, so any nontrivial factorization would be into two factors
each of degree 2, and each of these factors would have leading coefficient 1 and constant coefficient
1. Suppose we had X 4 + X + 1 = (X 2 + a · X + 1) · (X 2 + b · X + 1)
= X 4 + (a + b) · X 3 + ab · X 2 + (a + b) · X + 1. This would require a + b = 1 and a + b = 0 which is
impossible. Hence X 4 + X + 1 is irreducible over GF (2).

Theorem: Given an irreducible polynomial over GF(2), m(x), of degree d, we can construct a
field of characteristic 2 and size 2d .
Define F to be the set of polynomials with GF(2) coefficients with degree ≤ d − 1 with the usual
addition, and with multiplication defined modulo m(x). I.e, p(x)·q(x) is defined to be the remainder
of the usual product when divided by m(x). This field is denoted
GF (2)[X]/ < m(X) >.
Example : d = 3, m(X) = X 3 + X + 1, F = {a0 + a1 · X + a2 · X 2 : a0 , a1 , a2  GF (2)}.
Multiplication : We know that

(1 + X 2 ) × (1 + X + X 2 ) = (X 3 + X + 1) × (X + 1) + (X 2 + X) (2)

in case of regular multiplication with coefficients from GF(2). Hence, under the field multiplication
operation ‘.’,

(1 + X 2 ) · (1 + X + X 2 ) = (X 2 + X) (3)
For d = 2, with m(X) = X 2 + X + 1, GF (2)[X]/ < m(X) > is just the example we constructed
by hand (of GF(4)) with X being written for what we called α. You can check this from the addition
and multiplication tables.
Note that, given an irreducible polynomial m(X) of degree d over GF(2),
GF (2)[X]/ < m(X) > is a set of 2d elements. As mentioned, addition is defined coordinate-wise,
and multiplication is modulo m(X).
Claim : This is a field.
Proof: The additive identity is zero polynomial (0 + 0 · X + . . . 0 · X d−1 ).
The additive inverse of p(X) is just p(X) (coefficients are from GF(2) !).
Commutativity and associativity of addition are obvious.
The multiplicative Identity is 1 (1 + 0 · X + . . . + 0 · X d−1 )
Commutativity and associativity of multiplication are obvious.
Multiplication distributes over addition : this is because, to find the remainder of p(X)q(X) when
divided by m(X) we can first find the remainders of p(X) and q(X) when divided by m(X) (this is
3
not necessary if p(X) and q(X) are already of degree at most d-1), and then find the remainder of
the product of these remainders, when divided by m(X).
What about the existence of a multiplicative inverses for non-zero elements ?
To show the existence of a multiplicative inverse for a nonzero element p(x) ∈ F , we make use
of the Euclidean Division Algorithm, which provides us with an a(x), b(x) ∈ F such that

a(x)p(x) + b(x)m(x) = GCD(p(x), m(x)) = 1 (Bezout Identity)

and degree(a(x)) ≤ d − 1.
a(x) is then the multiplicative inverse of p(x) in F . Note that GCD(p(x), m(x)) = 1 since m(x)
is irreducible.

Example: Find the inverse of 1 + x in GF(2)[x]/< x2 + x + 1 >.

x2 + x + 1 = x(x + 1) + 1
(x + 1) = (x + 1)1 + 0

Then working backward:

1 · (x2 + x + 1) + x(x + 1) = 1
so x(x + 1) = 1 mod x2 + x + 1, so x is the multiplicative inverse of x + 1.

Example: What is (1 + x + x2 )−1 in GF(2)[x]/< x3 + x2 + 1 > ?

x3 + x2 + 1 = x(1 + x + x2 ) + (x + 1)
x2 + x + 1 = x(x + 1) + 1
(x + 1) = 1(x + 1) + 0

Then working backward, we replace (x + 1) in the second equation using the first equation:

x2 + x + 1 = x(x3 + x2 + 1) + x2 (1 + x + x2 ) + 1
(1 + x2 )(x2 + x + 1) + x(x3 + x2 + 1) = 1

So (x2 + x + 1)−1 = 1 + x2 mod x3 + x2 + 1.

A large number of practical codes are based on these finite fields.

We will presently show:

I. Every field F of size 2m must be “of this kind.”

II. For every m ≥ 1, there is an irreducible polynomial of degree m, hence there is a field of size
2m . Of course, this polynomial may not be unique, however,

III. Irrespective of which irreducible polynomial of degree m is used, the resulting field is the
same up to relabeling of the elements.
4
 We note an analogy between the construction of these finite fields and the construction of the
complex numbers from the reals. In the latter case, the polynomial x2 + 1 is irreducible over <,
and we form the field of complex numbers using <[x]/ < x2 + 1 >. By creating the symbol i to
represent the solution to x2 + 1 = 0, we force the complete factorization: x2 + 1 = (x + i)(x − i).

Analogously, GF(2m ) is the unique finite field of size 2m obtained by forcing the complete
m
factorization of x2 −1 − 1 (i.e. regardless of how we choose m(x), the nonzero elements will be
m
precisely the 2m − 1 solutions of x2 −1 = 1).

Definition 1 Let F be a finite field of size n. Let α ∈ F, α 6= 0. Consider α, α2 , α3 , . . . . Since the

field is finite, we must have αl = αk for some l 6= k, so we must have αj = 1 from some j 6= 0.
The smallest such j is called the order of α, denoted ord(α).

Lemma 1 (Lagrange) For every α ∈ F , ord(α) divides n − 1.

Proof: The n − 1 nonzero elements of F form a group under field multiplication. The set
{1, α, α2 , . . . , αj−1 } is a subgroup of this group. The disjoint union of the cosets of this subgroup
gives F . Thus j divides n − 1, which we denote j|(n − 1).

This shows that every nonzero element α of a finite field F of size n must solve the equation
m
xn−1 − 1 = 0 (since αj = 1 and j|(n + 1)). We will take n = 2m giving x2 −1 − 1 = 0. Our field
will consist of the 2m − 1 solutions to this equation and the zero element.

Definition 2 A nonzero element of a finite field whose order is n − 1 is called primitive.

Example: If there is a primitive element in a field of size 16, then there must be a nonprimitive
element, namely the primitive element cubed. Some fields have only the zero, unity, and primitive
elements, like the field with cardinality eight.
Consider a nonzero, nonunity element of GF(8), α. Since α is primitive (because n − 1 = 7 is
a prime), the elements of GF(8) can be written as {0, 1, α, α2 , . . . , α6 }. We will construct a field of
size 8 in 2 ways and see that they are the same up to a renaming of the elements.

One way to construct this field is to use GF(2)[x]/< x3 + x + 1 >. We will denote ax2 + bx + c
by abc. Addition over this field is done coordinate-wise in GF(2). To specify the multiplication
rule, we could multiply all elements of GF(2)[x] and then divide by x3 + x + 1 and take the
remainder. However, a more intelligent method is to remember that the elements can be written
as {0, 1, x, x2 , . . . , x6 }. We then find the representations of the various powers of x as polynomials
of x of degree ≤ 2. Since x3 mod (x3 + x + 1) = x + 1, we can obtain the following:

1 = 1
x = x
x2 = x2
x3 = x + 1

5
 x4 = x3 · x = (x + 1)x = x2 + x
x5 = x3 · x2 = (x + 1)x2 = x2 + x + 1
x6 = x5 · x = x3 + x2 + x = x2 + 1

Then

110 · 101 = (x2 + x) · (x2 + 1)

= x4 · x6 = x10 = x3
= x + 1 = 011

This allows us to fill in the entire multiplication table for our field:

· 000 001 010 011 100 101 110 111

000 000 000 000 000 000 000 000 000
001 000 001 010 011 100 101 110 111
010 000 010 100 110 011 001 111 101
011 000 011 110 101 111 100 001 010
100 000 100 011 111 110 010 101 001
101 000 101 001 100 010 111 011 110
110 000 110 111 001 101 011 010 100
111 000 111 101 010 001 110 001 011

Note that 010 (x), 100 (x2 ), and 110 (x4 ) solve the equation m(x) = x3 + x + 1 = 0. It is easily
verified that the other three nonzero, nonunity elements, 011 (x3 ), 101 (x6 ), 111 (x12 = x5 ) solve
the other third–order irreducible polynomial, m̂(y) = y 3 + y 2 + 1 = 0. If we constructed the field
using m̂(y) in place of m(x), then y would replace x3 , giving the one-to-one mapping:

000 001 010 100 011 110 111 101

0 1 x x2 x3 x4 x5 x6
0 1 y5 y3 y y6 y4 y2
000 001 011 101 010 110 111 100

(Here we used the rule y 3 = y 2 + 1 to derive the binary expansion in the bottom row). This
verifies that these two ways of construction GF(8) are identical up to element relabeling. In the
sequel we will see that
m YY
x2 − x = m(x),
d|m

where the inner product is over all irreducible polynomials m(x) of degree d. For m = 3 we
have
x8 − x = x(x − 1)(x3 + x + 1)(x3 + x2 + 1)
from which we conclude that x3 + x + 1 and x3 + x2 + 1 are the only irreducible polynomials of
degree 3 (you could have also verified this directly, case by case). Thus, if you believe the claim (I)
6
that every finite field of characteristic 2 and size 2d has to be of the form GF (2)[x]/ < m(X) >
for some irreducible polynomial m(x) of degree d, then the two constructions of GF (8) described
above exhaust all possible constructions, and, since they are identical, we conclude that GF(8) is
unique. Note that the elements of GF(8) are precisely the solutions of x8 −x. The nonzero elements
of GF(8) are precisely the solutions x7 − 1.
We will see:

I. Given a finite field F of characteristic 2 and size 2m , it must be of the type GF (2)[X]/ <
m(X) > for some irreducible polynomial m(X) of degree m.

II. For every m ≥ 1 there exists at least one irreducible polynomial (over GF(2)) of degree m.

III. All constructions of the type GF (2)[X]/ < m(X) >, m(X) irreducible, degree m, result in
the same field, up to renaming of the elements.

Defn: Euler φ Function: This is a function defined on {1, 2, . . .} with φ(1) = 1, and for n ≥ 2 φ(n) =
number of integers in {1, 2, . . . , n − 1} that are relatively prime to n. (i.e. gcd(k, n) = 1 ⇐⇒ k is
counted.)
Ex: φ(15) = 14− | {3, 6, 9, 12, 5, 10} |= 14 − 6 = 8.

Defn: Mobius Function(µ): This is a function defined on{1, 2, . . . , } with µ(1) = 1. For n ≥ 2, n =
a
Πli=1 pi i .

(
(−1)l , if n = pa11 pa22 . . . pal l and ai = 1, 1 ≤ i ≤ l
µ(n) =
0, otherwise

Ex: 75 = 31 .52 , µ(75) = 0. 210 = 2.3.5.7, µ(210) = (−1)4 = 1.

Defn: Dirichlet Product: Given two functions f and g defined on {1, 2, . . .}, their Dirichlet product,
denoted f og, is defined as
X n
f o g(n) = f (d)g( ).
d|n
d

Ex: f o g(72) = f (1)g(72) + f (2)g(36) + f (3)g(24) + f (4)g(18) + f (6)g(12) + f (8)g(9) + f (9)g(8) +

f (12)g(6) + f (18)g(4) + f (24)g(3) + f (36)g(2) + f (72)g(1)

Fact: The Dirichlet product is commutative and associative.

Notation:
1̂ is the function 1̂(n)=1 for all n > 1.
δ is the function δ(1) = 1, δ(n) = 0 f or n > 1.

Fact: δ is the identity for the Dirichlet product. ⇒ f o δ = δo f = f

7
 X n
[(f o δ(n) = f (d)δ( ) = f (n)δ(1) = f (n)].
d|n
d

Theorem: For the Dirichlet product µ is the inverse of 1̂ i.e. µo 1̂=1̂o µ = δ.

Pf: µo 1̂(1)=µ(1)1̂(1)=1=δ(1). (by defn.)

X X X
For n > 1, µo 1̂(n)= µ(d)1̂( nd ) = µ(d). Now we need to show that µ(d) = 0.
d|n d|n d|n
Suppose n = pa11 pa22 . . . pal l . d|n iff d = pb11 pb22 . . . pbl l for some 0 ≤ bi ≤ ai . If any bi ≥ 2 then µ(d) = 0
by definition.
The number of divisors d for which exactly j of the bi are 1 and none are ≥ 2 is jl .


! !
X l l
So, µ(d) = 1 + (−1) + (+1) + . . . + (−1)l = (1 + (−1))l = 0.
d|n
1 2
Thus µo 1̂(n) = δ(n) for n ≥ 2 also. Hence µo 1̂ = δ.

X Möbius Inversion Formula: Suppose g and f are functions on {1, 2, . . .} satisfying

Theorem:
g(n) = f (d), then we have
d|n
X n
f (n) = µ(d)g( ) . (4)
d|n
d
X X
Pf: The hypothesis is that g = f o 1̂= f (d)1̂( nd ) = f (d). So, go µ = (f o 1̂)o µ = f o(1̂o µ) =
d|n d|n
f o δ = f . This is precisely equation(4).

Now we are ready to prove Claim I. We need two more lemmas for that.
X
Lemma: φ(d) = n, for any n ≥ 1.
d|n
Pf: Consider all the fractions n1 , n2 , . . . , nn . Reduce each of these to lowest terms. For each d|n
exactly
X φ(d) of these fractions will end up getting reduced to a fraction whose denominator is d.
So, φ(d) = n.
d|n
X n
This implies that φ(n) = µ(d)( ) (by the Möbius Inversion Formula.)
d|n
d
If n = pa11 pa22 . . . pal l , then
l l l
X 1 X X 1 1
φ(n) = n[1 − + − . . .]= n Πli=1 (1 − 1
pi ).
i=1
pi i=1 j=1,j6=i
pi pj

8
Therefore,
l 1
φ(n) = n Π (1 − ). (5)
i=1 pi
Note: φ(n) > 0. (This can also be seen by simply noting that 1 is relatively prime to n.) The
formula (5) can be interpreted as an inclusion-exclusion formula. First subtract 1 from n =|
{0, 1, . . . , n − 1} | pni times, 1 ≤ i ≤ l. This is to remove all the integers in {0, 1, . . . , n − 1} that are
divisible by pi . However, integers that are divisible by pi pj for some i 6= j have been overcounted,
so we throw them back in, and so on.

Lemma: If α ∈ F (finite field of characteristic 2) and ord(α) = t (i.e. αt = 1 and t is the smallest
such), and if β = αi , then
t
ord(β) = gcd(t,i) .

Ex: Consider F = GF (16), i.e. F = {0, 1, α, α2 , α3 , . . . , α14 }, t = 15. (α3 )5 = 1, and we have
15 15
5 = gcd(3,15) . Similarly, (α10 )3 = 1, 3 = gcd(10,15) .

Pf: Let u denote ord(β). β = αi , i.e. (αi )u = 1 and u is the smallest such.
t i t
t
Note: (αi ) gcd(i,t) = (αt ) gcd(i,t) = (1) gcd(i,t) = 1 ⇒ u| gcd(i,t) .
t i t t
Also, since αt = 1 and (αi )u = αiu = 1, we have t|iu. So, gcd(i,t) | gcd(i,t) u ⇒ gcd(i,t) |u since gcd(i,t)
i t
and gcd(i,t) have no common factors. So, u| gcd(i,t) .
t
Putting these together, we have u = gcd(i,t) .

Theorem: If F is a finite field of size 2m , there are exactly φ(t) elements in F of order t for each
t dividing 2m − 1.
m
Corollary: Any finite field of size 2m can be written as {0, 1, α, α2 , . . . , α2 −2 } where α is a
primitive element.
Pf: φ(2m − 1) > 0 ⇒ F has an element of order 2m − 1, i.e. a primitive element.

Defn: In a finite field F , given β ∈ F, β 6= 0, the polynomial with coefficients in GF (2) of least
degree satisfied by β is called the minimal polynomial of β.
Ex: In GF (8) = {0, 1, α, α2 , . . . , α6 }, where α represents X in GF (2)[X]/ < X 3 +X +1 >, α, α2 , α4
have minimal polynomial X 3 + X + 1 and α3 , α5 , α6 have minimal polynomial X 3 + X 2 + 1.

Claim: Given F , a finite field of size 2m and β, a primitive element in F , its minimal polynomial

9
has to have degree m. Call this minimal polynomial m(X). Then F can be viewed as GF (2)[X]/ <
m(X) > .

Pf. of claim (claim I): If β is a primitive element and β satisfies b0 + b1 X + . . . + bk X k = 0

with k < m, then every power of β is a nonzero linear combination with GF(2) coefficients
of 1, β, β 2 , . . . , β k−1 ⇒ can have at most (2k − 1) distinct powers and we know that there are
(2m − 1) distinct powers ⇒ k ≥ m, which is a contradiction. Conversely, since F has dimen-
sion m over GF (2), β m should be expressible as a linear combination with GF (2) coefficients of
1, β, β 2 , . . . , β m−1 .

Pf. of Theorem: Let α ∈ F, α 6= 0, α 6= 1. Let t = ord(α). Then t|(2m − 1).

Consider 1, α, α2 , . . . , αt−1 . Each of these solves X t − 1 = 0, and any element of F that solves
X t − 1 = 0 must be one of these, because this equation can have at most t solutions. In particular,
any element of F of order t must be one of these (since any element of order t satisfies X t − 1 = 0).
Now, exactly φ(t) of these have order t since αi has order t precisely if gcd(i, t) = 1 and there are
exactlyXφ(t) such i. This means there are exactly φ(t) elements of F that have order t.
But, φ(t) = 2m − 1. This means that for each t|2m − 1 we have exactly φ(t) elements of F
t|2m −1
of order t (by counting).

We now prove Claim II. We will need the following

Theorem 1 For each m ≥ 1,
m Y Y
x2 − x = p(x)
d|m p(x) irreducible
of degree d

Lemma 2 (xl − 1)|(xk − 1) iff l|k

Proof: Suppose k = q · l + r where q and r are the quotient and remainder after dividing k by l,
so that 0 ≤ r ≤ l − 1. Then:
xk − 1 (xq l − 1)xr xr − 1 l (q−1)l r xr − 1
= + = (1 + x + · · · + x )x +
xl − 1 xl − 1 xl − 1 xl − 1
The second term on the right cannot be a polynomial since r ≤ l − 1, so if xl − 1 divides xk − 1,
r −1
we must have xxl −1 = 0, i.e. r = 0, so l divides k.
The converse is trivial from the above representation. 2

Lemma 3 (2l − 1)|(2k − 1) iff l|k

10
Proof: Same as above. Write 2 instead of x everywhere in the preceding proof. 2

m
Lemma 4 Let g(x) be an irreducible polynomial dividing x2 − x. Then degree of g(x) divides m.

Proof: Let d be the degree of g(x). Let F̂ be the quotient field GF (2)[y]/ < g(y) >. We saw before
d
that the elements of F̂ are precisely the 2d roots of x2 − x.
Take any element a(y) ∈ F̂ , a(y) = a0 + a1 y + · · · + ad−1 y d−1 with ai ∈ GF (2). Note that each
d
such element is a root of x2 − x, and since there are 2d such elements, all distinct, these are all the
d
roots of x2 − x (in F̂). Then, using the fact that in a field of characteristic 2, (u + v)2 = u2 + v 2
(Freshman’s dream!), and squaring consecutively we get, in the field F̂,

(a(y))2 = a0 + a1 y 2 + · · · + ad−1 y 2(d−1) = a(y 2 )

..
.
m m (a)
(a(y))2 = a(y 2 ) = a(y) ,
m m
where (a) is because y 2 = y modulo g(y), from the hypothesis that g(x) divides x2 − x, and
m
g(y) = 0 in F̂. Thus a(y) also solves x2 − x = 0.
d m d m
So, in F̂, the roots of x2 − x also solve x2 − x. This means (x2 − x)|(x2 − x). Then by Lemma
1, d | m. 2

m
Lemma 5 Let g(x) be any (irreducible) polynomial dividing x2 − x. Then g(x)2 does not divide
m
x2 − x.
d
Definition: The formal derivative, dx (·) of a polynomial in GF (2)[x] is the linear operator defined
by:
∆
(
d 2m )
dx (x =0
d 2m+1 ) ∆
dx (x = x2m
It is easy to verify that the formal derivative has the chain rule property,
d d d
i.e. dx (p(x)q(x)) = p(x) dx (q(x)) + q(x) dx (p(x)).
m
Proof of Lemma 4: Suppose we can write x2 − x = (g(x))2 f (x). Then, taking derivatives of
both sides, we get:
d
1 = (g(x))2 (f (x))
dx
d
(using the chain rule and since dx (g(x)2 ) = 0 in GF (2)[x].)
but this is impossible unless g(x) = 1. 2

Lemma 6 Let d be a divisor of m. Then every irreducible polynomial, g(x) of degree d divides
m
x2 − x.

11
Proof: Let F̂ = GF (2)[y]/ < g(y) >. Then F̂ is a field of size 2d . We claim that the minimal
polynomial of y (viewed as a member of F̂) is g(x). To see this, first notice that g(y) = 0 in F̂,
so y solves g(x) = 0. Further, no polynomial of degree less than d can be solved by y, or else the
dimension of F̂ would be less than d.
d
All the elements of F̂ are roots of x2 − x. In particular y is a root, and so its minimal
d d
polynomial, g(x), must divide x2 − x. This is because, if it didn’t divide x2 − x it would have to
be relatively prime to it (as polynomials in GF (2)[x]), so it would be possible to find polynomials
d
a(x), b(x) ∈ GF (2)[x] such that a(x)g(x)+b(x)(x2 −x) = 1, but this would lead to a contradiction,
because, when this equation is applied to y (in the field F̂) we get the equation 0 = 1. Now, by
Lemma 2 we have (2d − 1) | (2m − 1), because we assumed that d | m. Then by Lemma 1,
d m d m m
(x2 −1 − 1) | (x2 −1 − 1), so (x2 − x) | (x2 − x). So g(x) divides x2 − x. 2

Proof of Theorem 1: Follows directly from Lemmas 3, 4 and 5. 2

Proof of Claim II: Let Nd denote the number of irreducible polynomials of degree d. Then,
equating the degrees of polynomials in Theorem 1, we get:
X
2m = d · Nd
d|m

Then from Möbius Inversion Formula:

X m d
m · Nm = µ( )2
d|m
d

The right-hand side is nonzero, since it is the sum of distinct powers of 2 with coefficients in
{−1, 0, 1}, with at least one nonzero coefficient corresponding to d = m. Thus Nm > 0. 2

We will prove Claim III in the sequel using the following concept :

Definition: A polynomial, m(x) of degree m is called primitive if it is irreducible, and

min{t > 0 : m(x)|xt − 1} = 2m − 1,

and the following two lemmas :

Lemma 7 The minimal polynomial of a primitive element is primitive.

Lemma 8 All the roots of a primitive polynomial are primitive.

Then we will use all the results we have proved so far to get a deep understanding of the minimal
polynomial of any element in any finite field of characteristic 2. This will be provided by the
following :
i
Theorem 2 Let F be a field of size 2m . Given α ∈ F, α 6= 0, 1, consider {α, α2 , · · · , α2 }:
12
 d
• There exists a smallest integer d > 0 such that α = α2 .

• d divides m.
d−1
• The roots of the minimal polynomial of α are precisely {α, α2 , · · · , α2 }, i.e. the minimal
polynomial of α is precisely
d−1
(x − α)(x − α2 ) . . . (x − α2 ).

Note that this is a polynomial of degree d so one consequence is that the degree of the minimal
polynomial of any element must divide m. Note also that when we claim that this polynomial
is the minimal polynomial of α we are also claiming that its coefficients are in GF (2) (which
is not obvious at first sight).

Lemma 1 Let F be a finite field, |F | = 2m , and char(F ) = 2. If α ∈ F is primitive (i.e. ord(α) =

2m − 1) its minimal polynomial m(x) is primitive (i.e. the smallest t for which m(x) divides xt − 1
is t = 2m − 1).

Proof:
m m
1. m(x) must divide x2 −1 −1 because if not, since m(x) is irreducible we have gcd(m(x), x2 −1 −
1) = 1, as polynomials in GF (2)[x]. So there exist a(x) and b(x) in GF (2)[x] such that
m
a(x)m(x) + b(x)(x2 −1 − 1) = 1. Apply this to α, get 0 = 1. This is a contradiction.

2. m(x) cannot divide xt − 1 for any t < 2m − 1 because if it did, i.e. xt − 1 = m(x)g(x) for
some g(x) ∈ GF (2)[x], plug in α and get αt − 1 = 0, but this means α is not primitive.

Lemma 2 Let p(x) be a primitive polynomial. Then all its roots in F are primitive.

Proof: Note that p(x) is irreducible, because this is part of the definition of being primitive.
Suppose p(x) had a root β which was not primitive, i.e. β t = 1 for some t < 2m − 1, then either
gcd(p(x), xt − 1) is some nontrivial divisor of p(x) or it equals p(x). If the former, then p(x) is
not irreducible, and this is a contradiction. If the latter, then p(x) divides xt − 1, and we have
t < 2m − 1, so this is a contradiction to Lemma 1.

φ(2m −1)
Corollary 1 The number of primitive polynomials in GF (2)[x] of degree m is exactly m .

Proof: Every primitive polynomials in GF (2)[x] of degree m shows up exactly once as a factor
m
of x(x2 −1 −1). There are exactly φ(2m −1) primitive elements in a field of size 2m and the nonzero
m m
elements of F are all roots of x2 −1 − 1, so their minimal polynomials are factors of x2 −1 − 1. The
minimal polynomials of the primitive elements must be primitive and of degree m, and each of the

13
 φ(2m −1)
m roots of a primitive polynomial is primitive, so there are exactly m primitive polynomials
in GF (2)[x] of degree m.

Corollary 2 In particular, for each m ≥ 2 there is at least one primitive polynomial in GF (2)[x]
of degree m.

Proof: Since φ(2m − 1) > 0, the result follows from the preceding corollary. Alternately, as we
have already proved that a field of size 2m exists for each m ≥ 1, and we have already proved that
such a field has at least one primitive element, and we have proved that the minimal polynomial
of a primitive element is primitive and of degree m, this proves the corollary.

4 Proof of III
Given F , |F | = 2m , we saw it has at least one primitive element and, for any primitive element
α ∈ F , F can be viewed as GF (2)[x]/hm(x)i where m(x) is the minimal polynomial of α (which
has degree m, as we saw).
Recall that:
m −1
• the nonzero elements of F are all roots of x2 −1
•
m −1 Y Y
x(x2 − 1) = p(x)
d|m irreducible polynomials p(x) of degree d

• there are φ(t) elements of degree t in the field

This means that for any primitive polynomial m̃(x) of degree m, F contains some β (β is
primitive) which has m̃(x) as its minimum polynomial. So F can also be viewed as GF (2)[x]/hm̃(x)i.
So for any F of size 2m , it can be viewed as GF (2)[x]/hm̃(x)i for any primitive m̃(x) of degree
m. So all such F are “the same” (i.e. isomorphic).

5 Final Claim
Given F , |F | = 2m , and given α ∈ F , consider α, α2 , α4 , . . .
d
1. there will be a smallest d such that α2 = α

2. this d | m

14
 d−1
3. the minimum polynomial of α, say m(x), is precisely (x − α)(x − α2 ) · · · (x − α2 ) (it has
degree d and its coefficients are in GF (2)). The roots of a given minimal polynomial are said
to be conjugate. The corresponding powers of the primitive element, thought of as a subset
of 0, 1, . . . , 2m − 2, form what is called a cyclotomic coset modulo 2m − 1.
Proof:
k l
1. Given α with ord(α) = n, consider α, α2 , α4 , . . . There must be some k < l with α2 = α2 . So
k l−k l−k
α2 (2 −1) = 1 and n divides 2k (2l−k − 1). But n is odd, so n divides 2l−k − 1. So α2 = α
d
and there is a smallest d such that α2 = α.
2. Write m = qd + r where 0 ≤ r ≤ d − 1.
q times
z }| {
m qd ·2r d d d r
α = α2 = α2 = ((((((α2 )2 )··· )2 )2 )··· )2 = α2
| {z }
r outer braces
Since r < d, this is a contradiction unless r = 0.
3. Let α have minimum polynomial m(x) = xj +aj−1 xj−1 +· · ·+a0 where a0 , . . . , aj−1 ∈ GF (2).
d−1
We claim α2 , α4 , . . . , α2 are also roots of m(x) (because (u + v)2 = u2 + v 2 in char 2). To
see this
m(α2 ) = (α2 )j + aj−1 (α2 )j−1 + · · · + a0 = (m(α))2 = 0
d−1
But we see that (x − α)(x − α2 ) · · · (x − α2 ) is in GF (2)[x]. So this must be the minimum
polynomial.
Why? Its coefficients are the elementary symmetric functions in α0 = α, α1 = α2 , · · · , αd−1 =
d−1
α2 .
i.e.
α0 + α1 + · · · + αd−1 (coef of x)
X
αi αj (coef of x2 )
1≤i<j≤d
X
αi1 αi2 αi3 (coef of x3 )
1≤i1 <i2 <i3 ≤d
etc.

But
(α0 + α1 + · · · + αd−1 )2 = α02 + · · · + αd−1
2

= α1 + α2 + · · · + αd−1 + α0
etc.

So the coefficients solve x2 = x. So they must be 0 or 1, i.e. in GF (2).

15
6 Examples
In the following, the appendices, page numbers etc. refer to the book of Wicker.
Note that in the text we have :

• Appendix A: primitive polynomials of different degrees

• Appendix C: structure of the minimal polynomials of the element in the fields up to GF (210 )

Recall the formulas we have proved :

1 X m d
 
Nm = no. of irreducible polynomials of degree m = µ 2
m d|m d

φ(2m − 1)
no. of primitive polynomials of degree m =
m
• m = 2:
N2 = 12 [µ(2) · 2 + µ(1) · 22 ] = 12 [−2 + 4] = 1
2 ·2=1
φ(3) 2
2 = 2 =1
So there is one irreducible polynomial of degree 2 and this is primitive. This is x2 + x + 1.

• m = 3:
N3 = 13 [µ(3) · 2 + µ(1) · 23 ] = 13 [−2 + 8] = 1
3 ·6=2
φ(7) 6
3 = 3 =2
So there are two irreducible polynomials of degree 3 and both are primitive. These are
x3 + x + 1 and x3 + x2 + 1.
To construct GF (8) just write {0, 1, α, α2 , α3 , α4 , α5 , α6 }.
Appendix C (on pg. 476) lists under “modulo 7”

{0},
{1, 2, 4}, {3, 5, 6}

This is telling you that the factors of x7 − 1 are

(x − α0 ) = (x − 1)
(x − α)(x − α2 )(x − α4 ) = x3 + (α + α2 + α4 )x2 + (α3 + α5 + α6 )x + 1
(x − α3 )(x − α5 )(x − α6 ) = x3 + (α3 + α5 + α6 )x2 + (α + α2 + α4 )x + 1

If we choose to interpret α as a root of the primitive polynomial x3 + x + 1, this corresponds

to setting α + α2 + α4 = 0 and α3 + α5 + α6 = 1, and this tells you how to add : α3 = α + 1.
Alternatively, we could choose to interpret α as a root of the primitive polynomial x3 + x2 + 1,
which would mean setting α + α2 + α4 = 1 and α3 + α5 + α6 = 1 and now we add using
α3 = α2 + 1
16
• m = 4:
N4 = 14 [µ(4) · 2 + µ(2) · 22 + µ(1) · 24 ] = 14 [0 − 4 + 16] = 1
4 · 12 = 3
φ(15) 8
4 = 4 =2
So there are three irreducible polynomials of degree 3, only two of which are primitive. GF (16)
can be constructed as GF (2)[x]/hm(x)i for any one of the three irreducible polynomials, but
if we want to think of GF (16) as {0, 1, α, α2 , . . . , α14 }, then α has to be primitive, so the
minimal polynomial of α must be one of the two primitive polynomials.

x4 + x + 1 and x4 + x3 + 1 are irreducible and primitive

4 3 2
x +x +x +x+1 is irreducible but not primitive

Here is how we see that x4 +x3 +x2 +x+1 is irreducible. It has no roots in GF (2), so if it were
reducible we could write it as (x2 + ax + 1)(x2 + bx + 1) = x4 + (a + b)x3 + (ab)x2 + (a + b)x + 1.
This means ab = 1 and a + b = 1. This is impossible.
x4 + x3 + x2 + x + 1 is not primitive because it divides x5 − 1 (i.e. xt − 1 for t < 15).
Appendix A (on pg. 445) lists under “4”

10011
11001

This tells us the primitive polynomials of degree 4 : x4 + x + 1 and x4 + x3 + 1

Appendix C (on pg. 477) lists under “modulo 15”

{0},
{5, 10}
{1, 2, 4, 8}, {3, 6, 9, 12}, {7, 11, 13, 14}

Where do these come from? We can actually construct them by hand. For example, in which
list does α7 belong? We can just write {α7 , α14 , α13 (= α28 ), α11 (= α26 )}.
This means for GF (16) = {0, 1, α, α2 , . . . , α14 } the factors of x15 − 1 are

(x − 1)
(x − α )(x − α10 ) ⇒ corresponds to x2 + x + 1
5

(x − α)(x − α2 )(x − α4 )(x − α8 ) ⇒ corresponds to x4 + x + 1 or x4 + x3 + 1

(x − α3 )(x − α6 )(x − α9 )(x − α12 ) ⇒ corresponds to x4 + x3 + x2 + x + 1
(x − α7 )(x − α11 )(x − α13 )(x − α14 ) ⇒ corresponds to the other irreducible polynomial of degree 4.

• m = 5:
N5 = 15 [µ(5) · 2 + µ(1) · 25 ] = 15 [−2 + 32] = 1
5 · 30 = 6

17
φ(31) 30
5 = 5 =6
Thus there are 6 irreducible polynomials of degree 5, and they are all primitive. These are
listed in Appendix A on page 445 of the text, where one reads, under “5”,

100101
101001
101111
110111
111011
111101

This tells us the primitive polynomials of degree 5 : x5 +x2 +1, x5 +x3 +1, x5 +x3 +x2 +x+1,
x5 + x4 + x2 + x + 1, x5 + x4 + x3 + x + 1, and x5 + x4 + x3 + x2 + 1.
Appendix C (on pg. 477) lists under “modulo 31”

{0},
{1, 2, 4, 8, 16}
{3, 6, 12, 17, 24}
{5, 9, 10, 18, 20}
{7, 14, 19, 25, 28}
{11, 13, 21, 22, 26}
{15, 23, 27, 29, 30}

This is a list that you could have generated yourself, as discussed earlier. This tells us the
factorization of x31 − 1 : the factors are x − 1 and the six irreducible polynomials of degree
5. GF (32) can be viewed as :

{0, 1, α, α2 , . . . , α30 } ,

and any root of any of the six irreducible polynomials of degree 5 could be taken to be α.
How to add depends on this choice.

18