# How to build a finite field

This page, and its data table, are for the use of people
who know what a finite field
(= Galois field) is, and want to build one, of order less than 100,000, for their
own purposes.

If you're here because your coursework asks you to construct a finite field of order
*p*^{q}, these pages won't help you. You should use the method you've
been taught, which is probably to find an
irreducible polynomial
of degree *q* in the ring of polynomials over the integers modulo *p*, and then
proceed as you were instructed. Don't ask me how to do that, I don't know.

## Description

The elements of the field you build will be polynomials that look like

`a + b.n + c.n`^{2} + d.n^{3} + ... + k.n^{q-1}

where n is a meaningless "variable" and q is the exponent in p^{q}, the
order of the field. In the examples below, we use p=3 and q=4, so the field has
81 elements.

### Addition

Adding these elements is easy. We just add the polynomials modulo p, so that

`1 + 2n + 2n`^{3}

plus

`2 + 2n + 2n`^{2} + 2n^{3}

is

`n + 2n`^{2} + n^{3} .

Note that we don't apply modulo arithmetic to the exponents.

### Multiplication

Multiplication is more difficult. If we just multiply the elements like regular
polynomials, we'll get polynomials of arbitrarily high degree, and we'll have
an infinite field. So, whenever we get a term of exponent q (4, in our examples)
or higher, we'll have to "wrap" it around to a polynomial of lower degree: for
example, we could try

`n`^{4} = 1 + n .

If we just guess how to do this, it probably won't work, we'll get something that
may be some kind of respectable structure, but isn't a finite field. But there's
alway some guess that does yield a finite field, and I've listed one for you, for
every field of order less than 100,000, in the data table
accompanying this page.

If we get a term with exponent even higher than 4, that's not a problem. If we
have

`n`^{4} = 1 + n

we can deduce

`n`^{5} = n + n^{2},

`n`^{6} = n^{2} + n^{3},

`n`^{7} = n^{3} + n^{4} = 1 + n + n^{3},

etc.

### Building the multiplicative group

The multiplicative group of a finite field is always the cyclic group of order
*p*^{q}-1. You'll need a generator for this group, and you'll find
one listed in the "seed" column of the table. Start with the identity, 1, and
multiply it repeatedly by the seed, and you'll get all the elements of the cyclic
group.

### Summary

You want to build the finite field with 3^{4}=81 elements.
The elements all look like `a + b.n + c.n`^{2} + d.n^{3}.

Look up p=3 q=4 order=81 in our data table, and you'll see the line

`3 4 81 1 1 0 0 1 2 0 0`

so the "wrap" rule, specified by "1 1 0 0", is that you replace n^{4} by 1 + n,

and the "seed" that then generates the multiplicative group, specified by "1 2 0 0", is 1 + 2n.