How could one implement multiplication in finite fields?

Question

If F := GF(p^n) is the finite field with p^n elements, where p is a prime number and n a natural number, is there any efficient algorithm to work out the product of two elements in F?

Here are my thoughts so far:

I know that the standard construction of F is to take an irreducible polynomial f of degree n in GF(p) and then view elements of F as polynomials in the quotient GF(p)[X]/(f), and I have a feeling that this is probably already the right approach since polynomial multiplication and addition should be easy to implement, but I somehow fail to see how this can be actually done. For example, how would one choose an appropriate f, and how can I get the equivalence class of an arbitrary polynomial?

Answer 1

First pick an irreducible polynomial of degree n over GF[p]. Just generate random ones, a random polynomial is irreducible with probability ~1/n.

To test your random polynomials, you'll need some code to factor polynomials over GF[p], see the wikipedia page for some algorithms.

Then your elements in GF[p^n] are just n-degree polynomials over GF[p]. Just do normal polynomial arithmetic and make sure to compute the remainder modulo your irreducible polynomial.

It's pretty easy to code up simple versions of this scheme. You can get arbitrarily complicated in how you implement, say, the modulo operation. See modular exponentiation, Montgomery multiplication, and multiplication using FFT.

Answer 2

Whether there is an efficient algorithm to multiply elements in GF(p^n) depends on how you are representing the elements of GF(p^n).

As you say, one way is indeed to work in GF(p)(X)/(f). Addition and multiplication is relatively straightforward here. However, determining a suitable irreducible polynomial f is not easy - as far as I know there isn't an efficient algorithm for calculating a suitable f.

Another way is to use what are called Zech's logarithms. Magma uses pre-computed tables of them for working with small finite fields. It is possible that GAP does too, although its documentation is less clear.

Computing with mathematical structures is often quite tricky. You're certainly not missing anything obvious here.

Answer 3

It depends on your needs and on your field.

When you multiply you have to pick a generator of F^x. When you are adding you have to use the fact that F is a vector space over some smaller F_p^m. In practice what you do a lot of time is some mixed approach. E.g. if you are working over F₂₅₆, take a generator X of F₂₅₆^x, and let G be it's minimal polynomial over F₁₆. You now have

(sum_{i smaller then 16} a_i Xⁱ)(sum_{j smaller then 16} b_j X^j)= sum_k sum_{i+j = k} a_i b_j X^i+j

All you have to do to make multiplication efficient, is store a multipication table of F₁₆, and (using G) construct X^m in terms of lower powers of X and elements in F₁₆

Finanly, in the rare case where pⁿ = 2²ⁿ, you get Conways field of nimbers (look in Conways "winning ways", or in Knuth's volume 4A section 7.1.3), for which there are very efficient algorithms.

Answer 4

Galois Field Arithmetic Library (C++, mod 2, doesn't look like it supports other prime elements)

LinBox (C++)

MPFQ (C++)

I have no personal experience w/ these, however (have made my own primitive C++ classes for Galois fields of degree 31 or less, nothing too exotic or worth copying). Like one of the commenters mentioned, you might check mathoverflow.net -- just ask nicely and make sure you've done your homework first. Someone there ought to know what kinds of mathematical software is suitable for manipulation of finite fields, and it's close enough to mathoverflow's area of interest that a well-stated question should not get closed down.