# 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 pq, 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.n2 + d.n3 + ... + k.nq-1
where n is a meaningless "variable" and q is the exponent in pq, the order of the field. In the examples below, we use p=3 and q=4, so the field has 81 elements.

Adding these elements is easy. We just add the polynomials modulo p, so that
1 + 2n + 2n3
plus
2 + 2n + 2n2 + 2n3
is
n + 2n2 + n3 .

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
n4 = 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
n4 = 1 + n
we can deduce
n5 = n + n2,
n6 = n2 + n3,
n7 = n3 + n4 = 1 + n + n3,
etc.

### Building the multiplicative group

The multiplicative group of a finite field is always the cyclic group of order pq-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 34=81 elements. The elements all look like a + b.n + c.n2 + d.n3.
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 n4 by 1 + n,
and the "seed" that then generates the multiplicative group, specified by "1 2 0 0", is 1 + 2n.