An overview of finite fields
Modern cryptography and information theory relies heavily on
the mathematical notion of a finite field. The basic
principles of finite fields are not difficult to understand, but
the subject is not widely taught, except in
degree-level math courses. Textbooks on communications and coding
theory often contain an introduction to finite fields, but this is
usually so condensed as to be more-or-less incomprehensible.
In this article I attempt to describe the concepts of finite fields, from the ground up, to a level at which it is possible to understand modern encryption algorithms. I assume only a high-school understanding of math -- everything else I will attempt to explain from first principles.
The article begins with an outline of the abstract algebraic concepts of groups, rings, and fields. I then explain some of the background and terminology associated with modular arithmetic -- fairly briefly, as I would expect that most people working in computing would have already encountered these ideas.
I then go on to explain the basic principles of prime fields, and how these can be used to construct polynomial extension fields. It is the extension fields that are particularly relevant in cryptography. We can go a log way in coding theory knowing only the properties of prime fields.
I wrote this article to be read from the start to the end. Each section builds on the previous one, and refers to the same examples. I think it would be very difficult to read a specific section without reading the preceding material.
Groups, rings, and fields
Groups, rings, and fields are all sets of thingies, accompanied by specific operations on those thingies. Whether the thingies form a group, ring, or field, or nothing at all, depends on the thingies themselves, and on whether it's possible to formulate suitable operations between the thingies. The "thingies" in question are very often numbers, but they need not be. This is important -- the members of the set need not be even vaguely numeric: it's entirely possible to define a field of colours, or even sandwich fillings, with careful choice of operations.
For now, however, I'm going to assume that the thingies in questions are numbers. If they are, then groups, rings, and fields, are simply abstractions of ordinary number operations like addition and multiplication. When we define these constructs, we'll see that it takes a lot of words to say something which seems intuitively obvious. It's really not obvious what all the fuss is about -- we all know how to do basic arithmetic, after all. However, we need this complexity so we can define precisely the behaviour of sets that are not of numbers, and operations that are not everyday arithmetic. As we'll see, we can't define a finite field using regular arithmetic.
A group specifies the loosest kind of structure. If you're a ring or a field, you're also automatically a group, but not all groups are rings or fields. To form a group, a set of numbers must have associated concepts of addition and of zero with the following properties:
Addition is closed. That is, adding any members of the set results in something that is also in the set.
Addition is associative. That is, it doesn't matter in what order successive additions are carried out.
Adding zero to any number does not change its value.
Every number has an additive inverse, that is, a number to which it can be added to give zero.
This is all very abstract, but there is a very simple, concrete example: the integer numbers and everyday arithmetic addition. Even though the integers are unbounded, the set of integers is closed in the sense required for a group: adding any two integers gives another integer -- it never gives a fraction or a cheese sandwich.
Of course, it's kind of peculiar to think of something that is unbounded also being "closed"; but the word has a specific meaning in this context. "Closed" doesn't mean 'limited' or 'restricted' -- it means that you can't use the group's addition operation to create something that isn't in the original set.
The other group properties are easily demonstrated for integer addition, if not so easily proved rigorously. They are associative: 2 + (3 + 4) = (2 + 3) + 4. The number zero is the zero element: 2 + 0 = 0. The additive inverse is just the negation of the number: 2 + (-2) = 0.
There is no requirement that the group's additive operation behave in any way like regular addition, or even apply to numbers. Of course, it's easiest to understand if the additive operator have some similarity with regular addition and, in this article, it always will.
Note:
To be a group does not require that the addition operation be commutative. That is, it need not be the case that A+B = B+A. This is the case for regular numbers, of course, but it isn't part of the definition of a group. A group that does have a commutative addition operation is referred to as abelian. All rings, as we shall see, are also abelian groups
A ring is an abelian group with concepts of multiplication and (usually) one, with the following properties (in addition to the properties of a group):
The multiplication operation, like the addition operation, is associative: the sequence in which successive multiplications are applied does not affect the result
Multiplication distributes over addition. Technically, it is both left distributive (meaning that a x (b + c) = (a x b) + (a x c) ) and right distributive ((b + c) x a = (b x a) + (c x a)).
Multiplying any number by zero gives a result of zero
Most, but not all, mathematicians take a ring to require a concept of 'one', or 'multiplicative identity'. Any number multiplied by the identity keeps the same value.
We've seen that the integer numbers and regular addition form a group; supplemented by regular multiplication they also form a ring.
Just as the definition of a group did not require addition to be commutative, so the definition of a ring does not require multiplication to be commutative. Integer numbers multiply in a commutative way: 2 x 3 = 3 x 2. However, matrices (the kind you probably learned about in high school) form a ring that is non-commutative.
Note:
The set of odd integers forms a ring. Whether the set of even integers forms a ring is contested -- it depends on whether you think that a multiplicative identify is a defining characteristic of a ring or not. The ordinary number 1 is not included in the set of even numbers.
And so we come, at last, to fields. A field is simply a ring with a multiplicative inverse. That is, for any number in the set, other than zero, there will be a number it can be multiplied by to get the identity ('one') element. The integers do not form a field.. There is no integer we can multiply, say, 32 by to get one. The real numbers do form a field -- the inverse of N is simply 1/N. Although it's less obvious, the rational numbers (fractions) also form a field: the inverse of a/b is simply b/a.
Integers, rational numbers, and real numbers are unbounded sets of numbers. This is why our ordinary notions of addition and multiplication apply: however large the numbers we add or multiply, they aren't going to change into non-numbers. A finite field is simply a field with a bounded number of elements. Being bounded, of course, precludes the use of ordinary arithmetic operations. We need the field's addition, multiplication, and inverse operations to have at least a passing resemblance to their everyday counterparts; but clearly they can't be exactly the same same.
A digression into modular arithmetic
Modular (or modulo) arithmetic is a concept that will feature strongly in any discussion of finite fields. It's important to have an understanding of modular arithmetic -- both the basic principle, which is simple, and some of the implications, which aren't.
Modular arithmetic is arithmetic in which results are constrained to be within the range 0 ... M, where M is the modulus. I don't like to use this term, because it's so overloaded in mathematics, and I won't use it again in this article.
In modular arithmetic, calculations "wrap around" so they lie within the specified range. So, to take a trivial example,
13 mod 3 = 1
The mod 3 indicates that the result must be less than 3, that is, in the range 0 ... 2. The result is 1 because 13 is 10 greater than 3, 10 is 7 greater than 3, 7 is 4 greater than 3, and 4 is 1 greater than three. So we have to "wrap around" 3 several times to get a value in the range 0 ... 2.
Modular arithmetic as division with remainder
It's customary to express modular arithmetic in terms of remainders. We can read 13 mod 3 as "the remainder when 13 is divided by 3". For any integer A we can write
A = aM + r.
where r, the remainder, is some integer in the range 0 ... M, and a is some other integer. With this formulation
A mod M = r.
Note:
There are subtleties involved in doing modular arithmetic with negative numbers. In general, the idea of a "negative remainder" is an uncomfortable one. I don't have space to go into these matters here, and I don't have to, because none of my examples use negative numbers.
By formulating numbers this way, with a remainder, we can derive many useful relationships such as
(A * B) mod M = (A mod M) (B mod M) mod M.
The derivations are usually long and tedious, and not particularly illustrative.
The relationship shown above is particularly important for pragmatic purposes. In cryptography, where we might be dealing with vast numbers with hundreds of digits, it's useful to know that multiplication can be carried out on numbers that have already been reduced modulo M. This makes the computation much more manageable.
Modular congruence
A term that is frequently encountered in modular arithmetic is modular congruence. Broadly speaking, to say two mathematical entities are congruent is to say that they are in the same class, where class is defined by the result of some operation. The expression
A ≡ B (mod M)
says that A is in the same class as B, under the operation mod M. This relationship is usually read as "A is congruent to B, modulo M". There's no new mathematics here -- just different terminology. The expression above is exactly equivalent to
A mod M = B mod M,
just a little more compact. Another way of expressing the relationship between A and B is:
M | A-B
This expression is usually read "M divides A minus B". "Divides" in this context means "divides with no remainder". Because the congruence relationship is symmetric, it must also be the case that M | B-A although, of course, A-B and B-A have opposite signs.
I do want to stress, however, that these various formulations of modulo arithmetic differ only in notation -- one might express an idea better than another in some circumstances. The underlying arithmetic is the same, regardless of notation.
Modular inverse
The last concept I want to introduce is that of modular inverse. Addition, subtraction, and multiplication of integers all yield integer results, but division might not. Division might yield a result that can only be expressed in terms of a remainder. 3/2, for example, has no integer representation other than '1 remainder 1'. So modular arithmetic can express a result that has no representation in regular integer division.
Division can be expressed in terms of 'multiplication by an inverse' (strictly, a multiplicative inverse, since there are other kinds of inverse as well). The (multiplicative) inverse of a number is what it must be multiplied by to give 1. In real numbers, the (multiplicative) inverse of 4 is 0.25, because 4 x 0.25 = 1. Division by X amounts to multiplication by the inverse of X.
In real-number mathematics it's customary to use the "power of minus one" notation to represent an inverse. So
4-1 = 0.25, and
4-1 x 4 = 1
I'm not going to use that notation, because using negative powers on sets of integers is an odd notion. Instead I will denote the (multiplicative) inverse of X as inv(X). In a system of integer arithmetic, inv(X) only exists modulo some number (unless X=1).
Here's a trivial example:
inv(3) mod 5 = 2
Why? Because
(2 x 3) mod 5 = 1
In modulo 5 arithmetic, multiplying by 2 -- the inverse of 5 -- is equivalent to dividing by five.
When numbers are small, it's easy enough to figure out a modular inverse just by trial and error. After all, with modulo 5 arithmetic, there's only four possible values of the inverse. In fact, when the multiplication table can be fully written out, we don't even need the trial-and-error: it's just a matter of reading off the "1" values in the multiplication table. With larger numbers, we can use something called the extended Euclidean method, which I'm not going to describe here (and won't need to, as I'll always be dealing with small numbers).
In real-number arithmetic, every number except zero has a multiplicative inverse. In modulo arithmetic, that isn't the case. For example, what is inv(4) mod 6?
If this result exists at all, it will be a number in the range 1 ... 5. However, it shouldn't take long to convince yourself that no number in that range, multiplied by 4 modulo 6, gives 1.
What can we say about whether inv(X) mod M exists or not? It turns out that the inverse only exists if X and M are coprime. That is, X and M must have no common factors. It's easy to verify this fact using various selections of numbers, but it's remarkably fiddly to prove.
A digression into polynomials
A polynomial is a function of the form
f(x) = 2 x3 + 3 x2 + 4 x + 5
That is, a polynomial consists of a sum of powers of some variable, weighted by a set of numbers. The highest power -- 3 in this case -- is called the order of the polynomial. The weighting values -- 2, 3, 4, and 5 here -- are called the coefficients. A polynomial whose coefficients are all 1 is called monic.
Broadly, a polynomial is irreducible if it cannot be expressed as a product of polynomials of smaller order. Whether a polynomial is irreducible or not depends on how we interpret the coefficients. For example, the polynomial
x2 + 5 x + 6
can be expressed as (or 'reduced to', or 'factored to'):(x + 2)(x + 3)
whether we interpret the coefficients as integers or real numbers. However, this polynomial:
x2 + 5 x - 7
is irreducible over the integers. That is, there is no reduced form in which the numeric values are integers. Whether a polynomial is irreducible or not will always depend on the field it is associated with, and I will show later that this applies to finite fields as well.
The roots of polynomial are the values of its variable that make the polynomial evaluate to zero. In general, we take the number of roots to be the same as the order, although some of the roots might be the same. The roots of x2 + 5 x + 6 are x = -2, x = -3, but this is more obvious when looking at the factored form.
Polynomials can be added, subtracted, and multiplied using methods you probably learned in high school, although you may not have realized that was what you were doing. They can also be divided and, if you're as old as me, you might even have learned to do 'long division' on polynomials at school. I won't be describing how to divide polynomials, although it will be an essential factor in the construction of finite fields later. Life's too short -- use a computer program for this.
Basics of Finite fields
A finite field is simply a field with a limited number of members. How limited? Well, the limit can in principle be arbitrarily large, but it must be finite. We'll see that it's not possible to construct a finite field with just any old number of members.
The bounded size of the field means that the additive and multiplicative operators cannot be ordinary numerical addition and multiplication. However, they can make use of modulo arithmetic. If the number of elements in the field is M then, in the simplest case, we will do arithmetic modulo M.
A simple example
The simplest numeric finite field is one whose members are 0 ... M - 1 for some number M. That is, a field of size M = 5 has elements 0, 1, 2, 3, 4. A numeric finite field must contain 0 and 1, in order to meet the requirements of a field. If the other elements are not sequential integers, defining the rules for addition and multiplication would be very fiddly. Conventionally a set of integers of this type is denoted as ZM. So the set with elements 0 ... 4 is written Z5.
For a field of this basic numeric type we can define the addition operator as addition modulo M, and the multiplication operation as multiplication modulo M. This modulo arithmetic ensures that no addition or subtraction can exceed the range 0 ... M - 1. The field is therefore closed, as the definition requires.
The tables below show the addition table (left) and the multiplication table (right) for this simple finite field. Notice that all values are in the range 0 ... 4.
+ 0 1 2 3 4 x 0 1 2 3 4 0 0 1 2 3 4 0 0 0 0 0 0 1 1 2 3 4 0 1 0 1 2 3 4 2 2 3 4 0 1 2 0 1 4 1 3 3 3 4 0 1 2 3 0 2 1 4 2 4 4 0 1 2 3 4 0 3 3 2 1
We also need a multiplicative inverse for each number in the field, apart from zero. Regular arithmetic does not require us to be able to divide by zero -- this is rather frowned-on -- so field algebra does not require it either. The following table shows suitable values. You should be able to verify that each non-zero number, multiplied by its inverse (modulo 5) gives 1. In everyday arithmetic the only number that is its own inverse is 1. Here, however, the number 4 is also its own inverse, because 4 x 4 (mod 5) = 1.
N inverse 0 n/a 1 1 2 3 3 2 4 4
A failed example
Let's try to construct Z4. We'll do addition and multiplication as modulo 4. Here are the addition and multiplication tables:
+ 0 1 2 3 x 0 1 2 3 0 0 1 2 3 0 0 0 0 0 1 1 2 3 0 1 0 1 2 3 2 2 3 0 1 2 0 2 0 2 3 3 0 1 2 3 0 3 2 1
On the face of it these tables look fine: the values are in the correct range, and none of the values are missing. There is, however, a rather dodgy zero in the middle of the multiplication table (shown in red).
In ordinary arithmetic it's self-evident that we can't multiply two numbers and get zero, unless one or both of them is itself zero. In modular arithmetic, however, it's pretty clear that we can get zero by multiplying two non-zero numbers. (2 * 2) mod 4 = 0, for example. Does that prevent these numbers being members of a finite field?
There are various ways to answer this question, with various degrees of mathematical rigour. Intuitively, fields are intended to be abstractions of the regular arithmetic operations into wider domains. If we can multiply two non-zero numbers and get zero, it's pretty obvious that we've strayed considerably from recognizable arithmetic. Nothing in the definition of a field directly forbids non-zero numbers that multiply to zero, but it would mock the whole notion of multiplication.
Another way to look at the problem is to ask what the inverse of 2 is, in the case of modulo-4 arithmetic. It is a fundamental feature of a field that every element other than zero has a multiplicative inverse. Is that true in this case? Is there a number we can multiply 2 by, modulo 4, that gives 1?
I've already explained that a multiplicative inverse of A mod M only exists when A and M have no common factors. But 2 and 4 both divide by 2, so 2 is a common factor. So 2 mod 4 does not exist.
In fact, if a field consists of integers 0 ... M-1, and arithmetic modulo M, there's really only one way that we can arrange things that M never has any common factors with any number in the range of the field. You can probably figure it out, but I'll return to this point later.
Notwithstanding the previous discussion, there is a standard, textbook proof that a field cannot contain non-zero members that multiply to zero. It goes like this ('x' here denotes modular multiplication):
Assume that there are numbers a and b, such that a x b = 0, and a ≠ 0. Since a is not zero, it has a multiplicative inverse, denoted inv(a) such that inv(a) x a = 1. Since multiplying any number by 1 does not change its value, we can say b = 1 x b. But inv(a) x a = 1, so b = (inv(a) x a) x b. As multiplication is associative (this is one of the defining features of a field), we can write this last expression b = inv(a) x (a x b). But a x b = 0, so b = inv(a) x 0 = 0. So if a is non-zero, b must be zero.
This is a long-winded and rather tedious way to express something that is intuitively obvious: we can't have a valid field whose members multiply to zero.
Note:
Although two non-zero elements of the field can't multiply to zero, two non-zero elements can add to zero. This is true in regular arithmetic as well: -1 + -1 = 0, for example
Prime fields
As discussed above, it's a defining feature of a field that all elements other than zero have a multiplicative inverse. But this inverse won't always exist in a set of numbers. It didn't exist in Z4, so this set of numbers is not a field.
For every member of the field to have a multiplicative inverse, no member can have a common factor with the size of the field. That's another way of saying that the size of the field cannot be a multiple of any number in the field. And that's a way of saying that the size of the field must be a prime number. In short
The set of numbers ZM is a field only if M is prime.
Non-numeric finite fields
Of course it's easy to create a finite field of non-numbers simply by assigning numbers to other things. We can define a field of colours by setting blue=0, red=1, ... However, this isn't very interesting; by non-numeric I mean entities that do not map onto numbers.
Let's consider the simplest, non-trivial polynomial finite field. Such a field will need at least four elements, despite the problems I described above in trying to create a four-element numeric finite field. Why this works for polynomials, and not for numbers, is something I'll return to later.
The simplest non-trivial polynomial field contains the elements
0, 1, a, and a2.
Note:
I'm using 'a' rather than the more conventional 'x' because on many web browsers the letter 'x' looks too much like the multiplication sign 'x'. I will use a to indicate a variable from this point on.
To construct the addition, multiplication, and inversion operations, we will work in modulo-2 arithmetic, and we'll have to define some other relationships between the elements as well. After all, in everyday algebra a x a2 = a3, and a3 isn't an element in the set.
Because we're working modulo-2, the following relationship holds, which probably seem very odd compared to the way '+' and '-' work in regular arithmetic. But remember that we're free to define these operations however we like, so long as they are consistent with the rules of fields.
a + a = 2 x a = 0
Even stranger, perhaps, is the following relationship which, for now, we define to hold:
a2 = 1 + a
With these relationships in hand, we can construct an addition table for our four-element polynomial field, like this:
+ 0 1 a a2 0 0 1 a a2 1 1 0 a2 a a a a2 0 1 a2 a2 a 1 0
Even accepting that a2 = 1 + a, how did I arrive at the fact that -- as the table shows -- a + a2 = 1? Well, by definition, a2 = 1 + a, so a + a2 = a + 1 + a = 2 x a + 1 = 1. The other elements in the table can be derived in the same way, bearing in mind that all arithmetic is modulo-2.
Notice that the addition operation is closed, as the rules require: every addition result is another member of the field (using the definition of addition we've created). Adding zero does not change the value, as required. The other properties of addition can also be verified easily.
What about multiplication? We can construct the multiplication table in the same way as for addition:
+ 0 1 a a2 0 0 0 0 0 1 0 1 a a2 a 0 a a2 1 a2 0 a2 1 a
Again, this table has some non-intuitive entries. How, for example, is a2 x a = 1? As before, we apply the defined relationship a2 = 1 + a. So: a2 x a = (1 + a) x a = a + a2 = a + a + 1 = 2 x a + 1 = 1.
Finally, what about inversion? In this simple case, it's easy enough simply to pick the relevant values out of the multiplication table.
x inv(x) 0 n/a 1 1 a a2 a2 a
So we can see that the simple set { 0, 1, a, a2 } forms a finite field of size 4, and with a particular definitions of the addition operation. Arithmetic on this set has to be modulo-2 for the properties of a field to be satisfied. This modulo value is referred to as the characteristic of a field. Fields of characteristic 2 are particularly relevant in computing applications, because their operations can be expressed neatly using binary arithmetic.
I'll show later how a field that is equivalent to this one can be generated using a single, more complicated, arithmetic rule, rather than a bunch of arbitrary-seeming rules.
Recap
Here's a short recap of what I've explained so far.
A finite field is a bounded set of mathematical entities -- not necessarily numbers -- to which operations can be applied that are abstractions of the familiar addition, multiplication, subtraction, and division.
As in any field, a finite field must have members that represent 'one' and 'zero'. Often these are the everyday numbers 1 and 0.
A set of integers 0 ... M - 1 forms a finite field of size M, if arithmetic is defined modulo M, and if M is a prime number.
A set of polynomial expressions can form a finite field, with careful selection of the addition and multiplication operations.
For finite fields that do not consist simply of integer numbers, the characteristic is an important feature. This is (broadly) the modulo value in which arithmetic is carried out, and need not be the same value as the size of the field. I'll have more to say about this later.
Some properties of finite fields
Characteristic
By definition, the characteristic is the number of times one can be added to zero, before the result wraps around to zero. In fields where this never happens -- like the field of real numbers -- the characteristic is defined to be zero. That's a definition of convenience, rather than of logic.
It's not too difficult to prove that the characteristic of any field, if it is not zero, must be a prime number. In outline, if the characteristic were not prime, it would lead to the situation discussed previously, where non-zero members could multiply to zero.
Characteristic is not a particularly useful feature of a prime field -- we know that the arithmetic modulo value is the same as the field size, and is a prime number. But in the simple polynomial example above, the characteristic was 2 -- it was based on modulo-2 arithmetic -- but the size of the field was 4.
Characteristic-size relationship
The size of a field is simply the number of elements it contains. By definition, a finite field has a finite size. It can be shown -- in a variety of ways, all of them tedious -- that the size of a finite field must be a whole-number power of the characteristic. We often write the field size in this form: pm, p prime, m > 0. In the example above, p=2, m=2.
Uniqueness
There is only one field of size pm. This is an important result, but it's important to understand what it doesn't say. It doesn't prevent two fields existing that are isomorphic to one another. Fields are isomorphic if there is a one-to-one, reversible mapping between their elements. Trivially, the fact that { 0, 1, a, a2 } exists does not mean that { 0, 1, b, b2 } can't exist. We'll see a more subtle isomorphism later.
Moreover, the elements in the field do not fix the arithmetic operations between them. The same elements can have different addition and multiplication tables.
Subfields
Both finite and unbounded fields can have subfields. A subfield is some subset of the members of the field, which forms a field in its on right, using the arithmetic of the whole field.
For example, rational numbers (fractions) are a sub-set of real numbers, and they form a field with the same addition, etc., operations as apply to real numbers. So the rational numbers are a subfield of the real numbers.
A more interesting example, for present purposes, is that the simple polynomial finite field described above, { 0, 1, a, a2 } has elements of Z2 as a subfield. These elements { 0, 1 } form a field under the same rules of the larger field. Look at the top-left corners of the addition and multiplication tables to see that this is the case.
The field that consists of the numbers in the set Zp, where p is a prime number, is often denoted GF(p), where "GF" is an abbreviation for "Galois Field". The field that consists of the integers in Z5, for example, is written GF(5). So we can say that the polynomial field { 0, 1, a, a2 } has GF(2) as a subfield. A more common description, however, is that the polynomial field is an extension of the corresponding prime field.
Power identity
In any finite field of size q, any element raised to the power q, using the arithmetic rules of the field, is unchanged. That is, for any element A,
Aq = A
Consider the four-element field derived previously, { 0, 1, a, a2 }. It's easy enough to see that the power identity applies to 0 and 1. For the element a it takes a bit of arithmetic (and application of the rule a2 = a + 1). So: a4 = ((a2)2) = (a + 1)2 = a2 + 2a + 1 = a + 1 + 2a + 1 = 3a + 2 = a. As ever, we have to add the coefficients of the polynomials modulo the characteristic -- 2 in this case.
It's not conceptually any more difficult to verify that (a2)4 = a2 (with the same arithmetic rules), but it takes a lot more symbol-wrangling, so I'll ask you to take it on trust.
Generators
For any finite field, there is a specific generator element, which can be raised to a power to produce any non-zero element. For example, GF(5) has 3 as a generator. Powers of three, modulo 5, form all the elements of the field. That is:
31 mod 3 = 3
32 mod 3 = 4
33 mod 3 = 2
34 mod 3 = 1
Although it's not so obvious, polynomial fields also have generators; these are, of course, polynomial.
Extension fields of a prime field
In a sense, the prime fields we've been discussing are the simplest kind of finite field. However, I also gave a simple example of a polynomial finite field. A field of size 4 can be constructed by hand, by careful selection of arithmetic rules and a bit of trial-and-error. However, for pragmatic purposes we really need a systematic way to generate more complex fields based on much larger prime fields. Fields based on the prime fields are usually called extension fields.
In this section I'll elaborate on the concept of polynomials over a field, and show how a field of polynomials can be derived from any prime field.
The concept of polynomials over a field
If F is a field, then a polynomial over F is a polynomial whose coefficients are taken from the field in question. For example,
2 a2 + 3 a + 1
is a polynomial in variable a of order 2 over the field GF(5), because all coefficients are integers less than 5. This polynomial is irreducible over GF(5): it cannot be expressed as a product of two lower-order terms using coefficients which are integers in GF(5). The polynomial does factor in everyday arithmetic, but the factors are a + 1 and a + 1/2, and 1/2 is not an integer, so it does not factor in GF(5).
Note:
We must be very careful here -- it won't always be so obvious whether a polynomial is reducible or not. This is because, when we consider potential factors of a polynomial, we have to bear in mind that we will multiply them using modulo arithmetic on their coefficients. More on this later.
For a finite field F, there is an unlimited number of polynomials over F because, although the range of values of the coefficient is limited, the order of the polynomials is not. However, there will only be a specific number of polynomials for a given order. The coefficients must fall in the range 0 ... char(F), where char(F) is the characteristic of the field F. The characteristic is the value at which numbers "wrap around", so no coefficients this large or larger are allowed.
The set of polynomials over a field
We write the set of polynomials over F using the notation F[a]. For example, the set of polynomials over field GF(2) (which contains only 0 and 1) is written GF(2)[a]. All polynomials in this set are monic -- they have no coefficient greater than 1, because 1 is the largest value in GF(2).
GF(2)[a] is sometimes referred to as the polynomial ring on GF(2). Provided we confine ourselves to modulo-2 addition, GF(2)[a] is indeed a ring -- it embodies the properties of addition and multiplication. However, this is the case because GF2[a] is unbounded -- there is no limit on the order of the polynomials that are included. Constructing a finite field from polynomials won't be so easy.
Here is the complete set of polynomials of order 2 from GF(2)[a]. I've arranged them with the orders in distinct columns, in the hope that this makes it clearer how the set is constructed.
0
1
a
a + 1
a2
a2 + 1
a2 + a
a2 + a + 1
There are three possible powers (0, 1, and 2) in an order-2 polynomial, and two possible values for each coefficient (0, 1). So the total size of the list of coefficients is 23 = 8. To understand how we can turn this list into a field, we must first revisit the notion of reducibility.
Note:
In case it isn't obvious, a "zero order" polynomial is, in fact, just a number. That's why "0" and "1" are members of GF2[a], even though they don't contain any a terms.
Reducibility of polynomials in F[x]
Which of the polynomials in the list above are reducible? Remember that to be reducible means that the polynomial can be factored into a product of two polynomials of lower order. We don't need to consider the first four entries on the list as they have order zero or one. a2 is reducible in the trivial sense that it's just a multiplied by itself. a2 + a reduces to a(a+1).
Although it might not be immediately obvious, a2+1 is reducible -- not in conventional (real or integer) arithmetic, but in modulo-2 arithmetic. Its factors are both (a+1).
Why? Because in modulo-2: (a + 1)(a + 1) = a2 + 2 a + 1 = a2 + 1.
a2 + a + 1 is irreducible in GF(2). In fact, it is the only polynomial in the set above that is. How can we tell? Well, if a polynomial is reducible, it can (by definition) be expressed as two factors of lower order. Over GF(2) the only polynomials of lower order than order 2 are a and a+1. So, if the polynomial were reducible, it could be written as either of these two products: a(...) or (a+1)(...). But that means that either a(0) = 0 or a(1) = 0. We can say the polynomial must have a root a = 0 or a = 1. In fact, a2 + a + 1 is 1 when a=0 or a=1, so neither 0 nor 1 is a root, so the polynomial has no factors of order 1.
The same kind of reasoning can be used with higher-order polynomials, but the arithmetic gets much more complicated.
We've seen that there is a set of polynomials over a specific field -- in this case, GF(2). The $64,000 question is: do these polynomials form a field?
In the form I listed, they don't even form a ring. Addition (modulo-2) works out, but multiplication does not: multiplying two order-2 polynomials gives an order-4 polynomial, and there are no order-4 polynomials in the set.
Constructing an extension field using division modulo a polynomial
To get around this problem, we need another notion: modulo arithmetic in polynomials. I'm not talking about modulo arithmetic in the coefficients of polynomials, but in actual polynomials. To create a field from the set of polynomials over a field, we will take the remainder when each polynomial is divided by an irreducible polynomial.
An irreducible polynomial is the analogue of a prime number: just as a prime number does not divide by anything except itself and 1, an irreducible polynomial does not divide by a polynomial of any order but one. So modulo-polynomial arithmetic will play the same role in extension fields that modulo-prime arithmetic plays in prime fields.
In the example above -- the set of all polynomials of order 2 over GF(2) -- only one non-trivial polynomial was irreducible: a2 + a + 1. To construct a field from this set of polynomials, we must divide each by this irreducible polynomial, and take the remainder. We must do arithmetic on the field in the same manner. That is, we must reduce each polynomial modulo the irreducible polynomial. That gives us these mappings:
Original Reduced mod a2 + a + 1 0 0 1 1 a a a + 1 a + 1 a2 a + 1 a2 + 1 a + 1 a2 + a 1 a2 + a + 1 1
If we remove the duplicates, we're left with this set of polynomials: { 0, 1, a, a + 1 }. Because of the way it was constructed, the customary symbol for this set of polynomials is
GF(2)[a]/(a2 + a + 1)
Notice that there is no indication of the order of the polynomials in this formulation. Why? Because it's irrelevant. If we apply division modulo a2 + a + 1 to the polynomials, and division module 2 to their coefficients, then a polynomial of any order, however large, will be reduced to one of the values in GF(2)[a]/(a2 + a + 1). So we don't need to specify the order in this formulation.
Alternative formulations of the same extension field
We have now seen two polynomial fields that can be considered extensions of GF(2):
{ 0, 1, a, a2 } with multiplication rule a2 = 1 + a
{ 0, 1, a, a + 1 } with arithmetic modulo a2 + a + 1
In both cases arithmetic is modulo-2, because these fields have characteristic 2. As they have four members, they can be described as variants of GF(22).
As I mentioned before in the section on 'uniqueness', these two fields must be isomorphic. Clearly they are, because the first representation has a multiplication rule that turns it into the second.
Choice of polynomial divisor
We've seen that for a given F[x], that is, a set of polynomials over (based on) field F, we can divide "modulo a polynomial" to create a finite field of polynomials. The previous section demonstrated how GF(2)[a]/(a2 + a + 1) was a finite field of size 4, based on the prime field of size 2. To generate this field we used an irreducible polynomial in the set of polynomials of order 2.
However, there's no requirement to choose as the divisor a polynomial of the same order as those in the field. All it matters is that the divisor is capable of reducing polynomials to the same order as those in the field. So, for example, with polynomials of order 2, we need a divisor that will constrain the product of two polynomials of order 2 to a polynomial of order 2 or less (remember that if we multiply two order-2 polynomials in everyday arithmetic, we can get a polynomial of order 4).
One such polynomial, that can be applied to the order-2 polynomials over GF(2), is a3 + a + 1. If we reduce the set of eight polynomials modulo this order-3 polynomial, we end up with a modified set of distinct polynomials, which form a field which we can call GF(2)[x]/(a3 + a + 1), or just GF(23). This is not easy to prove formally, but it can be seen easily enough by constructing a multiplication table.
x 0 1 a a+1 a2 a2+1 a2+a a2+a+1 0 0 0 0 0 0 0 0 0 1 0 1 a a+1 a2 a2+1 a2+a a2+a+1 a 0 a a2 a2+a a+1 1 a2+a+1 a+1 a+1 0 a+1 a2+a a2 a2+a+1 a2 1 a a2 0 a2 a+1 a2+a+1 a2+a a a2+1 1 a2+1 0 a2+1 1 a2 a a2+a+1 a+1 a2+a a2+a 0 a2+a a2+a+1 1 a2+1 a+1 a a2 a2+a+1 0 a2+a+1 a+1 a 1 a2+a a2 a+1
Each row and column of the multiplication table is made up of distinct values, and each value equates to one of the members field. It is easy to see that each element has a multiplicative inverse, just by noting that there is a single '1' in each row and column.
Summary
This is a far as I want to go in this article. It has, in fact, covered all the fundamental considerations of finite fields that are relevant for communications theory and cryptography. You'll notice, I imagine, that I've chosen very simple examples, in which it's easy to see just by inspection that the rules of fields are followed. In fact, it's relatively easy to construct fields with particular properties just by pencil-and-paper arithmetic and a measure of head-scratching, when they are this small.
Much of the complexity of real-world applications follows from the fact that the finite fields in these applications are often enormous. Once we get beyond the back-of-an-envelope calculation stage, the problems tend to become computational, rather than theoretical.