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
                              x  + 2x + 2

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
                 2x  + 2x + 1

                 2x  + 0x + 2
                       2x + 2

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
               x  +  x
                    2x + 1

                    2x + 2

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