Main Page   Reference Manual   Compound List   File List  

Theory: Galois fields with cardinality 2m, the polynomial basis

Introduction

Fields

A Field is a set of elements for which addition, subtraction, multiplication and division are defined, along with a few intuitive axioms like that there must exist a 0 (for which x + 0 = x for every x element of the field) and a 1 (for which 1 $\cdot$x = x for every x element of the field) and the commutative and associative rules.  Note that $\mathbb{N}$, the natural numbers, that our ancestors used for counting similar things, is not a field: There is no solution for 3 + x = 0 in the natural numbers and something is only a field when every element has an 'additive inverse'.  Even if we add all the negative numbers, to get $\mathbb{Z}$, we still don't have a field because a field also must have a multiplicative inverse for every non-zero element, and clearly there is no solution for 3x = 1 that is element of $\mathbb{Z}$, either.  That way we naturally arrive at $\mathbb{Q}$ as the "smallest" field (remember, $\mathbb{Q}$ are the rational numbers and exist of all elements r/s with $r \in \mathbb{Z}$ and $s \in \mathbb{Z}\setminus\{0\}$). 

Finite fields

However all of the above sets are infinite.  We can also define addition and multiplication for finite sets.  First of all we will need a 0 and a 1, and then some more elements.  Consider the set {0, 1, a, b, c, d, e, ..., x} where adding the 0 to any element gives that same element, multiplying 0 with any element gives 0 and multiplying 1 with any element gives that same element, as is required by the axioms.  Another field axiom is that 0 and 1 must differ.  This implies that adding 1 repeatedly must either be a new element, or be equal to 0 (because we have only a finite field we will always have to end up with a previously defined element 'cause we run out of elements!  But setting 1 + 1 + 1 + 1 + 1 equal to some (smaller) non-zero element like say 1 + 1 + 1 has the problem that although 1 + 1 + 1 + 1 and 1 + 1 were different elements, adding 1 to either gives apparently the same element and then we don't have a field anymore).  Let us assume at first that adding 1 repeatedly gives all elements of the set, before returning to 0, then it can be proven that the total number of elements has to be prime (p) for this set to be possibly a field (otherwise one cannot define multiplicative inverses for all elements).

For example, lets consider a set of 5 elements: {0, 1, a, b, c} where 1 + 1 = a, a + 1 = b, b + 1 = c and c + 1 = 0.  Then this defines all possible ways one can add and subtract elements (Ie, b + c = (a + 1) + (b + 1) = ((1 + 1) + 1) + (((1 + 1) + 1) + 1) which is equal to, using the associative rules that allows us to reorder the brackets, = ((((1 + 1) + 1) + 1) + 1) + (1 + 1) = (c + 1) + a = 0 + a = a).  In order to associate multiplication with addition, we have to realize that although these elements are not integers, we still have x + x + x = 3 $\cdot$x (where 3 is an integer).  Replace x with the unity of our to-be-field (1) and we get: b = 1 + 1 + 1 = 3 $\cdot$1.  If we look at '1' as some universal unity that always gives the same thing when multiplying anything with it - than apparently our 1 added three times with itself is the integer 3.  If we go that way however, then we have to realize that working in our field the integer 5 is equivalent with 0 and x + x + x + x + x = 5 $\cdot$x = 0 for any x element of our field (where 5 is the normal integer: there is no element 5 in our original set.  Also note that the smallest positive integer p, for which p $\cdot$x = 0 for every x element of the field, is called the field characteristic.  In the case that the whole field can be generated by adding 1 to itself, this characteristic is equal to the number of elements; later we will see that a field always will have precisely pm elements where p is prime and m some positive integer).  Nevertheless, this is a convenient way of looking at it and we might as well rename our elements into {0, 1, 2, 3, 4}.  Clearly, now we have defined not only addition but also multiplication: for example 3 $\cdot$4 = 3 + 3 + 3 + 3 (= 2).  If the total number of elements in this finite (commutative) ring is prime, then we automatically have a field: then every element (except 0) will have a (unique) multiplicative inverse.  In our case, 1 $\cdot$1 = 1, 2 $\cdot$3 = 3 $\cdot$2 = 1 and 4 $\cdot$4 = 1.  It is left to the reader to check that this is not the case when p is not prime.  Finite fields (Galois fields) are thus a lot easier than infinite fields: the only restriction is that the characteristic of the field is prime after which you get division for free.

Field extension

Our next step is to investigate if we can extend a finite field by stubbornly adding another element that is not an integer, something completely different (and no, that won't be a cow - it will turn out to be some complex number). Lets assume we want to add the element 't', so that our example set becomes: {0, 1, 2, 3, 4, t} This clearly isn't a field anymore.  In order to keep it a field, we will have to add more elements so that the field remains closed under addition and multiplication (closed means that adding/multiplying any two elements gives again an element of the field).  It will not be hard to see that this leads to us having to add every arbitrary polynomial of t with coefficients from {0, 1, 2, 3, 4} = $\mathbb{Z}_5$, by only looking at addition and multiplication.  For example we could repeatedly multiply with elements and add elements until we got the element 3t8 + 2t5 + t4 + 4t + 1.  Please note that the coefficients are elements of $\mathbb{Z}_5$: there will not be a 6t, after all 6t = 5t + t = 0t + t = t.  Also note that the characteristic of the field is still 5: adding any polynomial 5 times to itself will give 0: 5 $\cdot$(3t + 4) = (5 $\cdot$3)t + 5 $\cdot$4 = 0t + 0 = 0. 

There is a nasty problem now: the field isn't finite anymore!  There are an infinite number of polynomials to begin with, and we didn't even take care of division yet: in order to make this a field again we'd have to add all rational expressions r(t)/s(t) where r(t) and s(t) are polynomials over $\mathbb{Z}_5$ and for the (fixed) t, the s(t) are restricted to those unequal 0.

But, this is about finite fields - and we already know that finite fields are a lot easier (under certain restrictions).  First of all we will have to get rid of the larger part of all polynomials by restricting them to some maximum degree; we simply pick some polynomial of degree m say, and state that that is equal to 0 (remember, this is very well possible: t is a complex number and there will exist a polynomial for which r(t) = 0).  As a direct result we will have gotten rid of all polynomials of degree m and higher: for example, suppose that r(t) = t3 + t2 + 1 = 0 (and thus, after adding 4t2 + 4t to both sides: t3 = 4t2 + 4t) then we can write t4 as a polynomial of a lower degree, namely: t4 = t t3 = t (4t2 + 4) = 4t3 + 4t = 4(4t2 + 4) + 4t = t2 + 4t + 1, which has a degree less than 3.  This so called reduction polynomial r(t) = 0 is very much like the characteristic p = 5 that we had before: it works as a modulo.  That is, two elements are equivalent when their difference is a multiple of the modulo (ie, 2 $\equiv$ 17 (pronounce: 2 is congruent to 17) because 17 - 2 = 5 $\cdot$3).  Likewise, when any two polynomials of t have a difference that can be written as r(t)v(t) then they are equivalent.  It will therefore not come as a surprise that the restriction upon our reduction polynomial, in order for the resulting set of polynomials to be a field, is that it has to be 'prime'.  That means, that r(t) cannot be written as the product of two polynomials of lesser degree.  In other words, r(t) must be an irreducible polynomial (the proof of this is given below). 

Galois fields of cardinality 2m

For computational reasons we will restrict ourselfs in libecc to irreducible polynomials with only three terms: tm + tk + 1 = 0.  Moreover, for computational reasons, we will use fields of characteristic 2 and the number of elements of our finite field will be of the form 2m.  Note that this means that tn + tn = 2tn = 0tn = 0.

Example

Let the reduction polynomial be of degree m = 4.
Then the total number of field elements is 24 = 16:

0 $\cdot$t3 + 0 $\cdot$t2 + 0 $\cdot$t1 + 0 $\cdot$t0 = 0
0 $\cdot$t3 + 0 $\cdot$t2 + 0 $\cdot$t1 + 1 $\cdot$t0 = 1
0 $\cdot$t3 + 0 $\cdot$t2 + 1 $\cdot$t1 + 0 $\cdot$t0 = t
0 $\cdot$t3 + 0 $\cdot$t2 + 1 $\cdot$t1 + 1 $\cdot$t0 = t + 1
0 $\cdot$t3 + 1 $\cdot$t2 + 0 $\cdot$t1 + 0 $\cdot$t0 = t2
0 $\cdot$t3 + 1 $\cdot$t2 + 0 $\cdot$t1 + 1 $\cdot$t0 = t2 + 1
0 $\cdot$t3 + 1 $\cdot$t2 + 1 $\cdot$t1 + 0 $\cdot$t0 = t2 + t
0 $\cdot$t3 + 1 $\cdot$t2 + 1 $\cdot$t1 + 1 $\cdot$t0 = t2 + t + 1
1 $\cdot$t3 + 0 $\cdot$t2 + 0 $\cdot$t1 + 0 $\cdot$t0 = t3
1 $\cdot$t3 + 0 $\cdot$t2 + 0 $\cdot$t1 + 1 $\cdot$t0 = t3 + 1
1 $\cdot$t3 + 0 $\cdot$t2 + 1 $\cdot$t1 + 0 $\cdot$t0 = t3 + t
1 $\cdot$t3 + 0 $\cdot$t2 + 1 $\cdot$t1 + 1 $\cdot$t0 = t3 + t + 1
1 $\cdot$t3 + 1 $\cdot$t2 + 0 $\cdot$t1 + 0 $\cdot$t0 = t3 + t2
1 $\cdot$t3 + 1 $\cdot$t2 + 0 $\cdot$t1 + 1 $\cdot$t0 = t3 + t2 + 1
1 $\cdot$t3 + 1 $\cdot$t2 + 1 $\cdot$t1 + 0 $\cdot$t0 = t3 + t2 + t
1 $\cdot$t3 + 1 $\cdot$t2 + 1 $\cdot$t1 + 1 $\cdot$t0 = t3 + t2 + t + 1

Polynomials of a higher degree do not exist because we can always write those as a polynomial of degree 3 or less.  For example, let the (irreducible) reduction polynomial of degree 4 be t4 + t + 1 = 0.  Now suppose t5 would be a field element, then we can simply prove that this polynomial is equivalent with one of the sixteen listed above by using the reduction polynomial: t5 = t $\cdot$t4 = t (t4 + 0) = t (t4 + t4 + t + 1) = t (t + 1) = t2 + t.

The polynomials can thus be represented by a bitset of m bits.  Each bit in turn then represents a coefficient of the polynomial.  This is very convenient for a computer.

Furthermore, because the algebra of the coefficients of the polynomials has to be done modulo two (as per our definition), addition (and substraction) of two polynomials is equivalent to the exclusive-or of those bitsets.  For example, (t2 + t) + (t2 + 1) = t + 1, which is equivalent with 0110 XOR 0101 = 0011.

Also multiplication can be implemented rather easily.  Because tp (t2 + 1) = t2+p + tp it is obvious that multiplication with a single power of t is just a left shift.  We do have to take into account the reduction polynomial though - when the degree of the resulting polynomial becomes too large.

Multiplication of two arbitrary polynomials exists of a few shifts and exclusive-or operations, followed by reduction with the reduction polynomial if needed.

For example,

t4 + t + 1 $\equiv$ 10011 (reduction polynomial)
t3 + t2 + 1 $\equiv$ 1101
t2 + t + 1 $\equiv$ 0111 

    1101
    0111 *
    ------
    1101
   11010
  110100 +  (addition is exclusive-or!)
    ------
  100011
  10011  -  (t * reduction_polynomial)
    ------
     101

And thus (t3 + t2 + 1) (t2 + t + 1) = t2 + 1.

The reduction polynomial could be any irreducible polynomial, but by using a trinomial (a polynomial with only three terms), reduction can be implemented much faster.  The power of the second term (k) should be chosen as small as possible because also that will speed up the process of reduction.  Therefore, for a given m, one should use the smallest k for which tm + tk + 1 is irreducible.

The reason that the reduction polynomial has to be irreducible is to ensure that the elements of the field indeed form a Field. First of all, multiplication of field elements should be commutative, that is ab = ba for any a and b element of the field. Now suppose that we would use a reduction polynomial that could be written as P $\cdot$Q where the (irreducible) polynomials P and Q are of respectively degrees p and q with 0 < p $\leq$ q < p + q = m.  Then P and Q are elements of the "field" (their degree is less than m). Furthermore, there should exist a R such that R $\cdot$P = 1 (R is the multiplicative inverse of P).  Then note that Q = (R $\cdot$P) $\cdot$Q $\neq$R $\cdot$(P $\cdot$Q) = 0, a contradiction!  If the reduction polynomial is not irreducible then we don't have a field thus!

Finding an irreducible trinomial

An irreducible trinomial is a polynomial of three terms, F(t) = tm + tk + 1 which cannot be written as the product of two polynomials of lower degree.  Finding an irreducible polynomial is based on the theorem that t(2m) - t is the product of all irreducible polynomials whose degree divides m.

When m is prime then all we need to do in order to find the smallest k is trying all values of k, starting at 1, until we find that t(2m) - t = 0  mod F(t), or in other words that t(2m-1) = 1  mod F(t).  If it equals 1 then the trinomial F(t) is irreducible.  [ When m is not prime then we also need to check that for each divisor d of m (1 $\leq$ d < m) that gcd(F(t), t(2d) - t) = 1 ].

More in general, let a be a polynomial element of the field, and let n be the smallest positive integer for which an = 1  mod F(t), then n is called the order of a.  All the polynomials aj that can be formed by running j over the values 0 till n - 1: {1, a, a2, a3, ..., an-1} form a group of n polynomials that can be generated by a.

A polynomial of order 2m - 1 is called a generator as it generates all elements of the field except 0.  If t is generator of a given polynomial field over $\mathbb{Z}_2$[t]/F(t), then the reduction polynomial F(t) is called primitive, which is more restrictive than irreducible.  The chance that an arbitrary irreducible polynomial of prime degree is also primitive is very likely (and for large m, even for non-primes), by far most irreducible trinomials of prime degree are also primitive.

This is a nice moment to note the equivalence with the Random Number Generator (see libecc::rng).  What we have there is a shift register with feedback points using exclusive-or; this is exactly equivalent with multiplying with t and using a reduction polynomial!  Consider a RNG with 3 bits and a feedback point to bit 0 and 1:

RNG state   Polynomial   Reduction of tn with t3 + t + 1 = 0
001 $\equiv$ 1 = t0
010 $\equiv$ t = t1
100 $\equiv$ t2 = t2
011 $\equiv$ t + 1 = t3 + (t3 + t + 1) = t + 1
110 $\equiv$ t2 + t = t4 + (t3 + t + 1)t = t4 + (t4 + t2 + t) = t2 + t
111 $\equiv$ t2 + t + 1 = t5 + (t3 + t + 1)(t2 + 1) = t5 + (t5 + t3 + t2) + (t3 + t + 1) = t2 + t + 1
101 $\equiv$ t2 + 1 = t6 + (t3 + t + 1)(t3 + t + 1) = t6 + (t6 + t4 + t3) + (t4 + t2 + t) + (t3 + t + 1) = t2 + 1
001 $\equiv$ 1 = t7 + (t3 + t + 1)(t4 + t2 + t + 1) = 1

The state of the random number generator can be seen as a polynomial over $\mathbb{Z}_2$ with a reduction polynomial that is determined by the feedback points.  Each step then corresponds with multiplying the polynomial with t.  The period of the RNG will be equal to the order of t, having a maximum value of 2m - 1 when the reduction polynomial is primitive.

In order to check if a given irreducible polynomial is primitive, one needs to know the factorization of 2m - 1.  After all, even while t(2m-1) = 1  mod F(t), then 2m - 1 is not necessarily the smallest positive integer n for which tn = 1  mod F(t).  For example, when 2m - 1 = p1 p2 p3 and the order of t is p1 p3 so that tp1p3 = 1  mod F(t), then also t(2m-1) = tp1p2p3 = (tp1p3)p2 = 1p2 = 1  mod F(t). Therefore, one must make sure that every possible fraction of 2m - 1 is not the real order.

Using the factorization tables of the Cunningham Project, we have calculated a list of primitive trinomials.  The program that was used for this can be found in testsuite/polynomial.

Further reading

See also http://www.certicom.com/index.php?action=ecc_tutorial,math8 and chapter 4.5 of The Handbook Of Applied Cryptography.

More information on primitive trinomials and Random Number Generators can be found on Richard Brent's page.  There you can also find links to sites about factorization.

If you want to go deeper into the theory of finite fields, then there is no online substitute for a good book. An excellent book that covers this material from a more mathematical (but also historical) perspective is Galois Theory (Third Edition), by Ian Stewart.

Copyright © 2002-2008 Carlo Wood.  All rights reserved.