go to the appendix
This is an attempt to write
The Great Everythingian Finite Field Writeup
When talking algebra, a ring is a set equipped with two
operations, addition and multiplication, with the property that
addition can be undone. If multiplication by anything except the
additive identity (that is, zero), can also be undone, then we speak
of fields. Undoing addition is known as "subtraction" and
undoing multiplication is known as "division". We usually
write the two operations and their two undoings as if we were working
with ordinary numbers, +, -, *, and /.
Included in this definition is that every field has at least two
elements, the additive identity (zero) and the multiplicative identity
(one). If you know any mathematics, you are already acquainted with
some fields. You will recognise fractions (the rationals) to form a
field and decimal numbers (the real numbers) to form another
field. Without further background, you might be hard-pressed to find
another example of a field. If you do, you will probably come up with
an example of another infinite field, such as the complex
numbers. Just out of sheer curiousity, is there such a thing as a
finite field?
Yes, there is. Finite fields are essential in number theory, useful
in combinatorics, and have found applications in coding theory and
cryptography. There are good reasons to learn about them. The
purpose of this writeup is to show that finite fields exist and to
characterise them. Let us begin with some preliminary investigations.
1. Characteristic of a Finite Field
The number of times that we can add 1 to itself until we reach 0 is
the characteristic of the field. The first thing to observe
is that a finite field F has positive characteristic. That
we have to reach zero eventually is clear. For let 2 denote 1+1, 3 is
2+1, and so on. Then, because we can't keep adding 1 and keep getting
different elements of F forever, (otherwise the field would not
be finite), we must have that for some pair of different integers
m and n, m = n as elements
of F. But then m - n = 0, and there is a positive
integer
p = 1 + 1 + ... + 1 (p times) such that p =
0. Pick p to be smallest positive integer in the field such that
p = 0. This is the characteristic of the field.
Theorem 1: A finite field has positive characteristic.
More can be said about the characteristic. It cannot have any proper
factors. For suppose otherwise, that p = kl for some
integers 1 < k < p and 1 < l <
p. Then kl = 0,
and k and l are divisors of zero. But a field cannot
have zero divisors, because zero divisors are nonzero elements that
cannot have a multiplicative inverse and nonzero elements in a field
must have a multiplicative inverse. Therefore, we cannot factor
p.
Theorem 2: The characteristic of a finite field is
a prime integer.
2. The Prime Fields
The fact that the characteristic of a finite field must be prime gives
us our first clue for hunting for finite fields. By definition, every
field, finite or not, has two elements: good ol' zero and one. Pick a
characteristic, say p, and take 1, and add it to itself
p times until you get the zero of the field. This is a set of
p elements. In fact, it is a ring, because we know how to add
and multiply these elements, and we ask, is it a field?
Yes it is, and it's called a prime field, but stay your
ground. I'm not ready yet to tell you why
it's a field. Let us get first get concrete and look at an example.
Suppose that we chose p = 7. Then
the set we are looking at is {0, 1, 2, 3, 4, 5, 6}, and we are
adding and multiplying modulo 7. So, for example, 2 + 6 = 1 (mod 7),
5 + 4 = 9 = 2 (mod 7) and 2 * 5 = 10 = 3 (mod 7). Just for kicks
and giggles, here is the complete addition and multiplication table:
+ 0 1 2 3 4 5 6
____________________________
0| 0 1 2 3 4 5 6
|
1| 1 2 3 4 5 6 0
|
2| 2 3 4 5 6 0 1
|
3| 3 4 5 6 0 1 2
|
4| 4 5 6 0 1 2 3
|
5| 5 6 0 1 2 3 4
|
6| 6 0 1 2 3 4 5
* 0 1 2 3 4 5 6
____________________________
0| 0 0 0 0 0 0 0
|
1| 0 1 2 3 4 5 6
|
2| 0 2 4 6 1 3 5
|
3| 0 3 6 2 5 1 4
|
4| 0 4 1 5 2 6 3
|
5| 0 5 3 1 6 4 2
|
6| 0 6 5 4 3 2 1
If we lean towards German peculiarities and use Z to denote the
integers ("Zahlen" is German for "numbers"), then we shall denote the
set of integers modulo 7 by Z/7. I pronounce this "zed mod
seven", although you might prefer the pronounciation "zee mod seven"
if you're American; it is the set in the tables above. I claim that
it's clearly a ring, because we can add and multiply just like we
can with the ordinary integers, except that we have to take the
remainder upon division by seven of the result. More interestingly,
the set is also an integral domain, that is to say, it has no zero
divisors.
What does the phrase "no zero divisors" mean in this context? Well,
by definition, a pair of zero divisors is a pair of nonzero elements from
Z/7 that multiplied together get zero. If we look at
the multiplication above, we see that all zeroes are clumped together
in the top row and the left column, and that's proof enough that
Z/7 is an integral domain. In general, it's true that
Z/p is an integral domain precisely because
we chose p to be prime. If we take two nonzero elements of
Z/p, that is to say, two integers not
divisible by p,
then their product is still not divisible by p, because a
prime number, being the building block that it is, must be present in
one of the factors whenever it's in the product (or "if a prime
number divides a product, then it also divides one of the
factors"). That prime numbers are indivisible reflects
on how Z/p is an integral
domain. There is a general theorem lurking here, but we don't need it.
Most interestingly, Z/7 is a field because every
nonzero element has a multiplicative inverse. That is to say, to
every nonzero element a corresponds another element
b such that ab = 1. This can be observed in the
multiplication table of Z/7. In every row or column
of the multiplication table besides those with zero we can find
1. Thus we can divide by
(multiply by the inverse of) every nonzero number in
Z/7 This proves that
I am indeed justified in calling Z/7 a prime
field.
This still leaves the business of proving that there is nothing
special about the number 7 in this respect, and that every
Z/p is a field. We only need to show that
every element has a multiplicative inverse; the other field axioms are
satisfied as an immediate consequence of the status of
Z/p as a ring. Clearly, building multiplication tables
for every Z/p will be an impossible task, seeing how
there are infinitely many primes, so further ingenuity is
required. This necessitates the Euclidean
algorithm. I will not digress to a full discussion of the Euclidean
algorithm; other nodes already provide the details. I merely remind my
readers that the Euclidean algorithm, when applied to the
integers a and b yields their greatest common
divisor d, and also furnishes two integers k
and l such that
ka + lb = d
This is interesting for us in the case that b=p is
our prime characteristic and a is a nonzero element of
Z/p less than p. In such a
situation, we know that a and p have no common
divisor except 1, and if we apply the Euclidean algorithm to this
pair, we discover that
ka + lp = 1,
such that upon reducing modulo p (remainder after division by
p), ka = 1 (mod p). Thus we have found
that k is the multiplicative inverse of a modulo
p, and because nothing was assumed about a except
that it's nonzero, this applies to any nonzero element of
Z/p. Thus,
Theorem 3: The rings of integers modulo a prime are
fields. The Euclidean algorithm yields the multiplicative inverse of a
nonzero element in these fields. These fields are known as prime
fields.
Recall how we formed Z/p. We took the one of
the field, which we know is there by definition of a field, and added
it to itself until we looped back to zero, which we know must happen
because the characteristic of a finite field is a positive prime
number. Thus, in every finite field of characteristic p we
can find a prime field, perhaps best called a prime subfield
in this context.
I have to mention the case when the characteristic of the field is
zero, that is, when no matter how many times we add one to itself, we
will not loop back to zero. Perhaps this would be best called
"infinite characteristic". Nevertheless "characteristic zero" is the
accepted terminology. Go figure. Characteristic zero is not really
interesting for us because then the field is not finite. I mention it
because characteristic zero fields contain the rational numbers
Q ('quotients') instead of containing
Z/p. You can see this by noticing that the
rational numbers are also generated by zero and one and the field
axioms. Take one and add and subtract from itself as much as you want,
and then divide as much as you want by nonzero things; you'll get the
rational numbers in characteristic zero. The point is that every
field, whether finite or not, contains a prime field or the rational
numbers and
because in nonzero characteristic prime numbers arise, we like to call
all these fields prime fields. The rational numbers are a prime
('indivisible') field too. Allow me to rephrase that.
Theorem 4: Every field of prime characteristic
p, such as a finite field, contains the integers modulo
p, denoted
Z/p. Every infinite field of
characteristic zero contains the rational numbers, denoted
Q. In short, every field contains a prime subfield.
Perhaps I have given the impression that only finite fields have prime
characteristic. This is not so, and there are infinite fields of prime
characteristic (if you want an example, consider a field of rational
functions over a prime field), although they are not worthy of
our attention for now. Nor will I say much more about fields of
characteristic zero (which are always infinite). I
only mentioned them to conform with the general definition of "prime
field".
3. Possible Size of a Finite Field
After all that hullaballoo about prime fields (which forthwith shall
refer to Z/p with blithe disregard for
Q), we return to general finite fields and see what
else we can discover now. We still have no idea whether or not we can
form a finite field besides the prime fields. Under the tentative
hypothesis that there do indeed exist other finite fields, there are
other truths about them that we can discover.
As a first result, we're already in a position to determine the
possible sizes of any finite field. Let F be a finite
field of characteristic p; we know this means that
Z/p is a subfield of
F. Then F is a vector space over
Z/p, and since F is a
finite set, F must
have a finite basis of size n. Let {b1,
b2, ..., bn} denote
such a basis. Then any element of F can be written
uniquely by choosing n elements c1,
c2, ..., cn of
Z/p and forming a linear combination such as
c1b1 +
c2b2 + ... +
cnbn.
Because there are p choices for each coefficient c
in Z/p, and there are n times we
have to make this choice, independently of all the others, there are
pn total choices, hence
pn elements in F. Thus,
every finite field has a size equal to some power of a prime.
If that discussion above with vector spaces and bases did not make
sense to you, I will now repeat the same argument without the benefit
of the jargon and standard theorems of linear algebra. We will
slowly build a basis and show that the finite field can be expressed
in terms of this basis.
Pick any finite field
F of characteristic p. There
are two possibilities. Either the field is equal to
Z/p, or it has something besides
Z/p. In the latter case, pick an element
b2 not in Z/p. (Why I am
beginning to index from 2 and not 1 will be apparent momentarily.) Now
form all possible combinations using Z/p and
b2. They are
0, 1, 2, 3, ..., p-1
0 + b2, 1 + b2, 2 + b2, 3 + b2, ..., p-1 + b2
0 + 2b2, 1 + 2b2, 2 + 2b2, 3 + 2b2, ..., p-1 + 2b2
0 + 3b2, 1 + 3b2, 2 + 3b2, 3 + 3b2, ..., p-1 + 3b2
.
.
.
0 + (p-1)b2, 1 + (p-1)b2, 2 + (p-1)b2, 3 + (p-1)b2, ..., p-1 + (p-1)b2
Count them. There are p rows, and each row has p
entries, thus there are p2 elements in this
table. All of the elements in the table are different. For suppose
otherwise. Then we would have two elements in the table equal to each
other, say
r1 + r2b2
=
s1 + s2b2,
or if we rearrange terms,
r1 - s1 =
(s2-r2) b2.
Either the difference s2-r2 is
zero or it is not. If it is zero, then s2 =
r2 and it follows that also
s1=r1 so that we have not
found different elements in the table at all. Otherwise, the
difference s2-r2
is not zero and we can divide by it, because we are working with a
field. In that case, we can solve for b2 to be
r1 - s1
b2 = -------
s2 - r2
so we have succeeded in expressing b2 in terms of
elements of Z/p. But we explicitly
postulated that b2 was not in
Z/p, so this expression for
b2 cannot occur and we are led to conclude that no
two elements of the table are alike. There are therefore
p2 distinct elements.
Again, there are two possibilities. Either this table with
p2 is all of the
finite field F, or there are more elements that do
not appear anywhere in the table above. In the latter case, pick an
element b3 that we haven't listed yet, and
consider all possible combinations
c1 + c2b2 +
c3b3,
where the coefficients c1, c2,
and c3 are allowed to range over all possible
values in Z/p. Since there are p
choices for each coefficient, independently of all the others, and
there are three such choices to make, there are p3
possibilities we can form here. In a similar manner as above, we can
prove that all the p3 possibilities are
different. If two are the same, we do the same of writing down what
those two possibilities are, say
r1 + r2b2
+ r3b3 =
s1 + s2b2
+ s3b3.
If the coefficients r3 and s3
of b3 are the same in those two equal
possibilities, then we can eliminate b3 from the
equation, and conclude that all the other coefficients are the same
too, because we already know that that all expressions involving only
Z/p and
b2 are different if the coefficients are
different (so we have not succeeded in writing an element of
F in two different ways). Otherwise, coefficients
r3 and s3 are different and
we can divide by their difference and express b3
in terms of Z/p and b2;
in other words b3 is in the previous table with
p2, which also cannot happen, as it goes contrary
to what we postulated about b3. So we have
therefore succeeded in listing p3 different elements.
Again we are at a fork in the road. Either these
p3 elements are all of the finite
field, or there are more elements we haven't accounted for yet. In the
latter case, we pick another element b4 that we
have missed, and use it
to form all p4 possible combinations, which will
all be different by the exact same argument. This
procedure is bound to stop,
because each time we are taking into account more and more elements of
F, first p, then p2, and
so on, but F has finitely many elements! At each step
we have a power of a prime, and F must be of this
size. The exponent of the size of a finite field is known as the
degree of the field.
Theorem 5: A finite field of characteristic
p must have size pn for some
natural number n. By degree of the field we mean
the number n.
The mathematical lore dictates that it is fashionable to use the
symbol q =
pn to denote the size of a finite field, and that
instead of using the symbol F to denote finite
fields, we get more specific and use the symbol
Fq. An equally important
tradition tells us that we can optionally also honour the memory
of Evariste Galois, refer to finite fields as Galois fields, and use
the symbol GF(q) or GF(p,n) to denote them.
I can no longer resist the command of tradition and
fashion. Henceforth, q
means "power of a prime". However, with my sincere regrets to Monsieur
Galois, I will opt to continue denoting finite fields by the symbol
Fq
So every finite field, whether it exists or not, must contain a prime
subfield, and must have size a power of a prime. We now turn to the
question of how to build finite fields on top of prime fields.
4. Extending the Field and Kronecker's Konstruction
Modern mathematicians like to tell a creation legend of how numbers expand
into new domains. They see a natural and logical progression from
counting numbers without zero, then counting numbers with zero (the
legends say that the discovery of zero can be compared with the
development of cell walls in the pre-Cambrian mathematical world),
followed by negative
numbers. At this magical moment, the first field was born: the
rational numbers, those wonderful fractions. The story goes on to
narrate the rise of the real numbers and their enfant
terrible, the imaginary unit, which together gave light to the
complex numbers, the miraculous algebraically closed culmination of
many centuries of mathematical evolution.
Like all creation legends, this one is partly true and partly
false. We are
going to take from this legend a very useful idea: that number sets
grow when a mathematician and an equation love each other very much.
According to this story, negative numbers were discovered as a desire
to solve equations similar to x + 6 = 2 and rational numbers
were the fruit of the romance of 3x = 4. A great commentator and
contributor to this legend was Leopold Kronecker, the nutty
constructivist, the very same one who said something resounding of
"God created the natural numbers, and everything else is the work of
Man." Kronecker would find himself in a cozy room with padded walls if
he walked among
us today; he viewed negative numbers with an unhealthy suspicion that
inspired him to fashion very creative ways to get
around them. Fortunately for him, he lived in late nineteenth century
Berlin, and we are not going to be paying much attention to his
philosophy, only to his brilliant ideas.
Back to finite fields. We understand prime fields, and we know that
every finite field is an extension of a prime field. According to the
creation legend, in order to extend the prime fields into other finite
fields, we need to find an equation in the prime field that we would
like to solve, but cannot. For example, we really would like to solve
the irreducible polynomial equation x2 +
x + 1 = 0 over the simplest
field that exists, F2 = Z/2 = {0,
1}, the field with two elements, where 1+1=0. There are only two
things we can try in our search for a solution, but unfortunately,
12 + 1 + 1 = 1
02 + 0 + 1 = 1
so neither works and the polynomial f(x) =
x2 + x + 1 over Z/2
does not have a root (also known as a "zero") in
Z/2. (Polynomials, roots, irreducible;
familiar words, yes? If not, follow the links, and I'll be waiting for
you when you feel ready.)
Here comes now Kronecker's brilliance. In a masterful stroke of
mathematical judo, we are going to use the equation against itself,
and obtain a larger field that contains Z/2 and that
has a root of f(x). The idea is to take the symbol
x, throw it into the field Z/2, and declare
that x is a symbol for another element we can add and
multiply with the sole provision that x satisfies the
equation x2 + x + 1 = 0, which implies
that x2 = x + 1. (Remember that 1 = -1 in
Z/2). This one equation that x must satisfy
completely determines addition and multiplication tables:
+ 0 1 x 1+x
_________________
0| 0 1 x 1+x
|
1| 1 0 1+x x
|
x| x 1+x 0 1
|
1+x|1+x x 1 0
* 0 1 x 1+x
_________________
0| 0 0 0 0
|
1| 0 1 x 1+x
|
x| 0 x 1+x 1
|
1+x| 0 1+x 1 x
Look at the multiplication table. All the zeroes are clumped along the
top row and leftmost column, and every row or column besides those two
has a 1 in it. Ladies and gentlemen, I present to you
F4, a finite field
with 22 elements. Please hold your applause until the end.
Perhaps it is a little mysterious how I obtained some of the entries
in the multiplication table, so allow me to demonstrate. Let us look
at (1 + x)*(1+x) on the bottom
right corner. First we use the distributive law to see that this is
equal to 1 + x + x + x2. We
simplify by noting that x + x = 2x = 0,
since 2=0 in Z/2, and further x2
= x + 1. Thus 1 + (1 + x) = x
is the correct entry on the bottom right corner.
This illustrates how to perform Kronecker's construction. It works in
general for any field, not just the finite ones. If you want to form a
bigger field with the root of a particular polynomial in mind, take
the indeterminate x of that polynomial (of course any other
symbol would do; sometimes people prefer to replace the symbol by some
fancy Greek letter), and declare that x can interact with
the other elements in the field provided that this
symbol x satisfies a polynomial equation. If when multiplying
you ever get a
very high power of x, then use the polynomial equation to
bring the power of the symbol down to a degree lower than the
polynomial equation; the actual procedure involved is polynomial
division with remainder. The remainder will be of lower degree than
the defining polynomial. This construction is so important, that we
shall pause for a moment to ponder it.
Definition 1: Let f(x) be a
polynomial that cannot be factored over some field F
(such as the prime fields). Then Kronecker's construction is
to take the
polynomial's indeterminate symbol x and to allow it to
add and multiply with elements of F, with the sole
restriction that f(x) = 0. This process is also
known as adjoining a root of an irreducible polynomial.
In its modern presentation, Kronecker's construction is usually
couched in the language of rings, ideals, homomorphisms, and
factor rings, also known as quotient rings, the so-called
'abstract algebra'. The reason that so much linguistic machinery is
put into a simple idea stems from the days when people applied
Kronecker's construction without truly realising what they were
doing. The modern language purports to be rigourous in ways that our
mathematical ancestors were not. Our ancestors questioned their own
results, and we can see their prejudices in the modern language. We
call the square root of minus one (the root of x2 +
1) the "imaginary" unit as a reminder of the barbaric days when simple
procedures such as Kronecker's construction were not to be
trusted. Nowadays we realise that there is nothing mystical about
adjoining a root of x2 + 1 to the real numbers to
form the complex numbers.
There remain two orders of business. I want to show you a larger
finite field to exemplify more clearly the mechanics of Kronecker's
construction. We also need to prove that
Kronecker's construction does in fact yield a field! It seems to work
for F4 and for adjoining the imaginary
unit i to the real numbers, but how do we know that we will
obtain fields in general? You might be wondering why I have been
insisting that the polynomial f(x) must be
irreducible, and the reason is similar to why the characteristic of a
finite field must be prime: otherwise we get zero divisors that dash
our hopes of forming a field. The answers again lie in the Euclidean
algorithm, in its polynomial version.
Let us build F27, a field with
33 elements. To this effect, we need to find, by hook or
crook, a degree three irreducible polynomial over Z/3. I
happen to know that f(x) = x3 +
2x2 + 1 is such a polynomial, and you can verify
this by noting that none of the three the elements of
Z/3 are a root. Recall that a polynomial of degree
three is irreducible if and only if it has no roots. The construction
is now simply to throw the indeterminate x into
Z/3 and to reduce by f(x) whenever
a power of x is three or greater. The 27 elements are given
by c0 + c1x +
c2x2 where
c0, c1, and
c2 are allowed to independently take any of
three values in Z/3.
I will not write the full addition table and multiplication table this
time, as they are starting to get big. I only present a sample. Here
is how to multiply x2 by itself in
F27. We perform polynomial division with
remainder over Z/3 to reduce
x2*x2 = x4.
x + 1
__________________________
3 2 ) 4 3 2
x + 2x + 1 ) x + 0x + 0x + 0x + 0 (use zeroes as placeholders)
)
4 3 2
x + 2x + 0x + x (remember that -2 = 1 and
____________________ -1 = 2 in Z/3)
3 2
x + 0x + 2x + 0
3 2
x + 2x + 0x + 1
____________________
2
x + 2x + 2
(remainder)
I do hope polynomial division is fresh in your mind from secondary school
algebra. The only difference now is that we are working over
Z/3 instead of the rational numbers. Reading the
above division, we see that x4 = (x +
1)(x3 + 2x2 + 1) +
x2 + 2x + 2. Because
f(x) = x3 +
2x2 + 1 = 0 in
F27, we can conclude that
x2·x2 =
x2 + 2x + 2.
An alternative way to do this which may or may not be more laborious
is to take the equation that x satisfies in
F27, namely x3 +
2x2 + 1 = 0, and to reinterpret this as
instructions for what to do when x gets to be degree three or
higher: x3 = x2 + 2. Then to
multiply x2·x2, we
rewrite it as x·x3 and
repeatedly use the equation imposed on x to turn this into
x (x2 + 2) = x3 +
2x
= (x2 + 2) + 2x
=
x2 + 2x + 2.
This is thankfully the same
result as we obtained above, and this is usually the procedure used,
for instance, when working with the complex numbers: we impose the
equation i2 = -1, and the rest follows.
Now we ask again if F27 is a field or
not. The real content of this question is whether can divide by
everything nonzero in F27 or not. What is
the multiplicative inverse of, say, x2 + 1? Euclidean
algorithm. We need the polynomial version of the Euclidean algorithm
to answer this.
There is a Euclidean algorithm with polynomials that works exactly the
same way as the one for integers. Let a(x) and
b(x) be a pair of polynomials. The Euclidean
algorithm for polynomials provides their greatest common divisor
d(x) and also furnishes another pair of polynomials
s(x) and t(x) such that
s(x)a(x) +
t(x)b(x) = d(x).
The situation of interest for us is when one of the polynomials is
irreducible and the other is of degree lower than the irreducible one,
so that their greatest common divisor is 1. (Compare with the
situation above with the Euclidean algorithm for the prime fields.)
Let f(x) be such an irreducible polynomial and
a(x) be one of lower degree. Then we can find
polynomials s(x) and t(x) such that
s(x)a(x) +
t(x)f(x) = 1.
If we are working over a prime field where we have adjoined a root of
f(x) (such as with F27
above), then we see that upon setting f(x) = 0, we
have found that s(x) is a multiplicative inverse of
a(x). Because this works for any nonzero polynomial
of degree lower than f(x), meaning for any nonzero
element of an extension obtained from Z/p by
adjoining a root of f(x), we see that Kronecker's
construction does indeed produce a field.
Theorem 6: Let f(x) be an
irreducible polynomial over any field K (such as the prime
fields.) The set
K[x]/<f(x)> obtained
from Kronecker's construction by adjoining a root of f(x) to
K is again a field. The Euclidean algorithm for polynomials
yields the multiplicative inverses of nonzero elements of
K[x]/<f(x)>.
You might be wondering about the notation
'K[x]/<f(x)>'. This refers to
"the polynomial ring over K, quotiented or
factored by the ideal generated by the
polynomial f(x)". It is not essential to understand what
this notation really means; it simply refers to the field K to
which we have adjoined a root of f(x). But if your
curiousity cannot be denied, I suggest you follow the hardlinks. In
the meantime, I will exemplify division (finding multiplicative
inverses) in
K[x]/<f(x)>.
I will now carry out the Euclidean algorithm for
x2 + 1 in F27.
First we need to divide f(x) =
x3 + 2x2 + 1 by
a(x) = x2 + 1.
x + 2
______________________________
2 ) 3 2
x +1 ) x + 2x + 0x + 1
)
3 2
x + 0x + 1x
_____________
2
2x + 2x + 1
2
2x + 0x + 2
____________
2x + 2
(remainder)
This reads as x3 + 2x2
+ 1 =
(x + 2)(x2 + 1) +
2x + 2, (highlighting the interesting polynomials) or
x3 + 2x2 + 1 -
(x + 2)(x2 + 1) = 2x + 2
The
remainder is still not of degree zero (constant polynomial), so we must
divide by it again.
2x + 1
__________________
) 2
2x + 2 ) x + 0x + 1
)
2
x + x
_____________
2x + 1
2x + 2
______
2
(remainder)
This division tells us that x2 +
1 = (2x + 1)(2x + 2) + 2, and the Euclidean
algorithm has stopped;
the two polynomials are relatively prime with greatest common divisor
equal to 2. If we rewrite this result as
x2 + 1 - (2x +
1)(2x + 2) = 2,
and replace the expression for 2x + 2 obtained from the
previous division into this one, we see that
x2 + 1 - (2x + 1)[
x3 + 2x2 + 1
-
(x + 2)(x2 + 1)] = 2,
-(2x + 1)(x3 + 2x +
1 ) + [(2x + 1)(x +
2) + 1](x2+ 1) = 2,
-(2x + 1)(x3 + 2x +
1 ) + (2x2 + x + x
+ 2 + 1)(x2+ 1) = 2,
-(2x + 1)(x3 + 2x +
1 ) + (2x2 +
2x)(x2+ 1) = 2.
If we divide throughout by 2 (or multiply by its inverse, which
happens to be 2 as well), and remove the minus signs according to the
rules of Z/3, we conclude that
(2x + 1)(x3 + 2x +
1 ) + (x2 + x)(x2+ 1) = 1.
Therefore, the inverse of x2 + 1 in
F27 is
x2 + x. I suggest you verify this
yourself by multiplying together and reducing with the defining
equation f(x) = x3 +
2x2 + 1 = 0.
5. Existence of Finite Fields
It should now be clear how to build a finite field of any of the
allowable sizes. Let q = pn be a power of
a prime. If we wish to build Fq,
the first thing to do is to look in Z/p for
an irreducible polynomial of degree n. Once we find such a
polynomial, we use it in Kronecker's construction and voilà, a
field with q elements.
Hence now the existence of a field with q elements depends on
finding irreducible polynomials over a prime field of degree
n. "By hook or crook", I said before, but here is a procedure
that, albeit slow, will produce irreducible polynomials over
Z/p. It is a sieve method, and you might be
familiar with the same idea for finding prime numbers.
The first thing to remark is that since Z/p
is finite, there are only finitely many polynomials of a given degree
n. By definition, none of the degree 1 linear polynomials are
reducible, so we begin there. Write down a list of all degree 2
polynomials. Next form all different possible products of degree 1
polynomials, and cross out each product from the list of degree
2. After this is done, whatever is not crossed out is an irreducible
polynomial of degree 2. Let the irreducibles aerate in a warm and
moisture-free corner. Now repeat. List all degree 3 polynomials. Form
all possible products between all degree 2 and all degree
1 polynomials, crossing out the degree 3 polynomials that arise. After
this step is done, whatever degree 3 polynomial that is not crossed
out is irreducible. And so on, for degree 4, we form all possible
products with irreducible degree 3 polynomials and degree 1, plus all
possible products with an irreducible degree 2 polynomial and any
other degree 2 polynomial, plus all degree 1 polynomials times any
other degree 3 polynomial. Whatever is left over is a degree 4
irreducible polynomial.
It is a lengthy procedure. If we are looking for a degree 42
irreducible polynomial (and we just might, if we are doing
cryptography), then we would have to first find all the irreducibles
of lower degree. Perhaps a better method would be to randomly guess
degree 42 polynomials and test them individually for
irreducibility. Even so, we are still left with the question as to
whether this procedure has any guarantee to work or not. Perhaps there
just simply isn't a degree 42 irreducible polynomial over
Z/163. The prince of mathematics was the first to
prove that this is not the case.
Technical Lemma 1: There exist irreducible
polynomials of every degree over every prime field
Z/p.
This technical lemma is a promise that the sieve method for finding
irreducible polynomials will succeed. Its proof relies on some
advanced techniques from number theory in an essential way. We
therefore banish the proof to an appendix for the hardcore mathematician and
number theorist. This proof is equivalent to the existence
of Fq for any power of a prime q. This
is why Gauss can be credited as a discoverer of finite fields,
although he did not explicitly ever work with them. Armed with this
lemma and even a procedure for finding irreducible polynomials, we
finally can declare that
Theorem 7: For any power of a prime q, there
exists a field with q elements.
The astute reader might question exactly why are irreducible polynomials
so important. I could be accused of bullying my readers into believing
that this is the only way to build a finite field. There also is
the possibility of there being more than one finite field of a given
size, although I have been acting all along as if the symbol
Fq denotes a uniquely defined
field. Let us remember that when building
F27, I boldly pulled the irreducible
polynomial x3 + 2x2 + 1 out of
thin air. I could have also chosen the polynomial
x3 + 2x + 1 as a defining polynomial, and
although it at first looks very similar to the first, the fact remains
that the computations in F27
will appear different if we use a different
polynomial. With the first polynomial, we calculate
x*x2 = x2 + 2,
and with the second this instead looks like
x*x2 = x + 2. Does this
mean that we have two different finite fields of size 27?
These concerns and others you didn't know you had are the content of
the next section.
6. Uniqueness of Finite Fields
In this section we will prove that all finite fields of the same size
are isomorphic. This will simultaneously address the question of
whether fields can only be built by adjoining roots of polynomials and
how the choice of irreducible polynomial affects the structure of the
finite field.
First, we need to understand isomorphism. Roughly speaking, it means
that two fields are essentially the same, that their structure is the
same and that the only difference is that we are calling them by
different names. "A rose" and "une rose" are the same thing on different
sides of the English channel. More formally, an isomorphism between
fields (finite or not) is a correspondence between its elements that
preserves the field structure. Most formally,
Definition 2: Let F and
K be two fields, finite or not. An
isomorphism between F and K
is a one-to-one correspondence φ from F to
K such that for any a and b in
F the following equations hold:
φ(a + b) = φ(a) +
φ(b)
φ(ab) =
φ(a)φ(b)
In case that an isomorphism exists between two fields, we say that
these fields are isomorphic.
The way to think about an isomorphism is that once we set up the
appropriate correspondence between the two fields, then adding and
multiplying in one field is the same as adding and multiplying in the
other field. This is the idea that the above equations involving φ
are trying to capture.
Isomorphism in general is an important concept of modern
mathematics. Sometimes isomorphisms are easy to spot, sometimes
not. For example, the familiar rules that even+even = even, odd+even =
odd, and so on, can be expressed as an isomorphism between the set
(actually, the field)
{even, odd} and the prime field Z/2; the isomorphism is
given by φ(even) = 0 and φ(odd) = 1.
The purpose of this section is to show that all finite fields of
the same size are isomorphic. In this way, the symbol
Fq does indeed represent a
uniquely defined field, up to isomorphism. There may be more than one
way to represent a finite field, and we will see that all such ways
are essentially the same. This will take a little bit of work.
For this section, let q = pn be a fixed
power of a prime. We shall denote by the symbols
Fq and
Kq finite fields of size
q, supposing momentarily that there is more than one field of
size q.
The key to showing that all finite fields of size
q are isomorphic is the equation
tq = t,
over the prime field Z/p. This equation is
known as Fermat's Little Theorem for finite fields. It
holds if we substitute any element of
Fq (or
Kq) for t. I can think
of two ways to prove it. One involves knowledge of group theory and
the other does not.
If you know group theory, Fermat's Little Theorem is
obvious. Consider the multiplicative group of nonzero elements of
Fq. It has order q -
1. Let t denote an arbitrary element of the multiplicative
group. By Lagrange's Theorem, an element of a group raised to the
order of the group equals the identity, that is,
tq - 1 = 1. This equation is valid
for any nonzero t. Multiplying through by t yields
the desired result, which is still valid for nonzero elements and now
also valid for zero.
If you do not know group theory, there is also a relatively clean way
to prove Fermat's Little Theorem. Suppose that a1,
a2, ..., aq-1 are all
the nonzero elements of Fq. Let
t denote any nonzero element of
Fq. Now consider the elements
ta1, ta2, ...,
taq-1. These are again all
nonzero, and they are all different, for if any two are the same, say
tai =
taj, then we can divide by
nonzero t to see that ai =
aj, and thus they were the same element
of the list to begin with. Therefore, the list with t is the
same as the list without t except that it's possibly in a
different order. We can thus multiply together all elements of both
lists to obtain the equality
a1a2***aq-1
=
(ta1)(ta2)***(taq-1).
If we rearrange things a bit,
a1a2···aq-1
=
a1a2···aq-1tq-1,
and we can divide by all the nonzero ai
to conclude that
tq-1 = 1,
for nonzero t. If we multiply through by t, we have
established for the second time
Theorem 8 (Fermat's Little Theorem for finite
fields): For any element t of a finite field with
q elements,
tq - t = 0.
Fermat's Little Theorem was first proven for prime fields by a
slightly different method involving some polynomial gymnastics. It is
a theorem of classical number theory. Beware that I am breaking some
traditions in labelling this result as "Fermat's Little Theorem"; all
modern expositions of finite fields I have read consider the result to
be too routine to deserve a special name. Nevertheless, I find its
importance for proving uniqueness of finite fields and for other tasks
to be tantamount. Those who read the appendix with the proof of
Technical Lemma 1 will also witness an appearance of Fermat's Little
Theorem.
The course to follow now is to analyse the polynomial
m(t) = tq -
t. We see that this is a polynomial of degree q, so
it cannot have more than q roots. Fermat's Little Theorem
says that it has q distinct roots in
Fq, that is,
m(t) factors completely into linear factors in
Fq. The terminology for factoring
completely into linear factors is
that the polynomial splits. If
you know enough
about general field theory, then you will be satisfied at this point:
Fq is the splitting field of
m(t), and all splitting fields are isomorphic,
QED. Those who are not satisfied please read on.
The polynomial m(t) of degree q =
pn is important because every irreducible
polynomial of degree n over Z/p is
a factor of m(t). Suppose that
f(t) is such an irreducible polynomial of degree
n over Z/p. This polynomial
f(t) does not have any roots in
Z/p, but Kronecker's construction allows us
to construct an extension field
Fq in which
f(t) does have a root.
We know that in
Fq the polynomial
m(t) = tq - t
has all elements of the field as roots, so therefore it must have a
root in common with f(t). It follows that if we
apply the Euclidean algorithm for polynomials to
f(t) and m(t) over
Z/p (and therefore also over
Fq, because it contains
Z/p), that f(t) and
m(t) must have a nontrivial common factor. But the
only things that divide f(t) in
Z/p are the polynomial 1,
and f(t) itself, because f(t) was
presumed irreducible. Since the greatest common divisor of these two
polynomials must be greater than 1 (otherwise they would not have a
common root), then the greatest common factor must be
f(t) itself. Consequently,
Theorem 9: Let q =
pn be a power of a prime. Then over the prime
field Z/p every irreducible polynomial of
degree n divides (or is a factor of) the polynomial
m(t) =
tq - t.
This has an important corollary. We will prove that looking for
irreducible polynomials is indeed the right way to look for finite
fields. Suppose that Fq is any
finite field of characteristic p, defined by whatever means
possible, not necessarily Kronecker's construction. We will show that
we might as well have defined it by Kronecker's construction. Let
f(t) be any irreducible polynomial of
degree n over Z/p. Because
f(t) divides m(t), and
m(t) splits in
Fq, then f(t)
also splits in
Fq. Let x denote any
root of f(t) in
Fq. Consider then the set
Z/p together with the element
x, and let x add and multiply freely with the
elements of Z/p. This is the prime field
together with some element that
satisfies an irreducible polynomial equation of degree n over
the prime field. We know by Kronecker's construction that this set is
a field with exactly q elements, so it must be equal to
Fq itself. To summarise,
Corollary 9.1: Every finite field is isomorphic to a
finite field obtained by adjoining the root of an irreducible
polynomial to a prime field.
If you know about the general theory of fields, you will recognise
this to be essentially a statement of the theorem of the primitive
element for finite fields. Most proofs of the general theorem of the
primitive element first deal with the finite case and then proceed to
the infinite case, so I do not think we have been wasting our time
with the hard work of proving the finite case first. If you do not
know about general field theory, my apologies and please ignore this
paragraph.
A more important corollary is the fact that every irreducible
polynomial of degree n over Z/p
splits in Fq. This is
now easy to see. Because such an irreducible polynomial
f(t) divides m(t), and
m(t) splits in
Fq by Fermat's Little Theorem,
then so does f(t). Let us record this.
Corollary 9.2: Let f(t) be any
irreducible polynomial of degree n over
Z/p. Then f(t) factors
completely into linear factors in any field with q
=pn elements.
This corollary furnishes us with a method for finding the isomorphism
between two finite fields of the same size. Let
Fq be the finite field obtained
by adjoining a root of f(x) to
Z/p, and let
Kq be the field obtained by
adjoining a root of g(y), where the polynomials are
irreducible over Z/p. By definition this
says, according to Kronecker's construction, that
Fq is
Z/p together with some element x
that satisfies the polynomial equation f(x) = 0 and
similarly Kq is
Z/p together with some element y
that satisfies the polynomial equation g(y) = 0.
The corollary tells us that not only does f(t) have
a root in Fq (changing from the
variable x to t for clarity), which we arranged
by construction, but also f(t) factors completely in
both Fq and
Kq, and similarly for
g(t). Thus, under an isomorphism from
Fq to
Kq, the element x
must maintain its defining feature of being a root of
f(t). So to find such an isomorphism, we factor
f(t) in Kq and
send x to a root of f(t) in.
Kq. There are n such
roots, and hence there are n different ways that
Fq can be isomorphic to
Kq. Of course, we can also do
this the other way around and send y to any of n
roots of g(t) in
Fq. Because of the way
Kronecker's construction defines a finite field as "prime field
together with something that satisfies this equation", we have twice
proven
Theorem 10: Let f(x) and
g(y) be two irreducible polynomials of degree
n over Z/p. Then the fields
Fq and
Kq obtained by adjoining a root
of f(x) and g(y) respectively are
isomorphic. The isomorphism is given by sending x into a root
of f(t) in Kq
or symmetrically by sending y into a root of
g(t) in Fq.
So because any finite field can be obtained by Kronecker's
construction, and because any two finite fields of the same size
obtained by Kronecker's construction are isomorphic, we finally have
Theorem 11: All finite fields of the same size are
isomorphic.
This concludes the bulk of our work. We finally know that for every
power of a prime there exists up to a isomorphism a unique finite
field of this size. I will spend the remainder of this section with explicit
calculations necessary to find an isomorphism between two finite
fields of size 33 = 27, as an example and application of
the theorems we have developed. Relax, the toil is over.
Let F27 denote the field obtained by
adjoining a root of f(x) = x3 +
2x2 + 1 to Z/3 and let
K27 be the field obtained by adjoining a
root of g(y) = y3 + 2y
+ 1. To find an
isomorphism from F27 to
K27, we must factor the polynomial
f(t) = t3 +
2t2 + 1 in K27.
Ordinarily polynomial factorisation is a difficult problem in
general. In this case, however, we have theorems at our disposal to
make the problem easier. We know that f(t)
must factor completely in K27 by Corollary
9.2. So to factor f(t) we need to only look for its
three roots in K27, and there are only 27
elements to try (actually, 27 - 3 = 24, because we know that none of the
elements of Z/3 are a root, as f(t)
is irreducible over the prime field). In fact, there is a theorem that
once a root is found, the others can be found easily via the Frobenius
automorphism described in the appendix, a useful technicality for
finding all the isomorphisms between one field and the other.
I admit that I cheated and that I used the Maple software package to
factor f(t) in K27. The
result was
f(t) =
(t + y2 + 2)(t +
y2 + y)(t +
y2 + 2y),
from which we can read that the three roots are
2y2 + 1, 2y2 + 2y,
and 2y2 + y, the negatives of the expressions.
appearing in the factorisation of f(t). The
isomorphism is now given by sending x into any of the roots
of f(t) in K27.
go to the appendix