tags:

views:

193

answers:

4

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?

+1  A: 

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.

Pourquoi Litytestdata
+6  A: 

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.

Jason S
It will probably be closed very fast on MO, which is aimed at graduate / pedagogical / research math.
David Lehavi
I disagree. First of all because it's a tool that could be used by research mathematicians; secondly, I asked a question about the spiral of Theodorus and got a very courteous answer. (http://mathoverflow.net/questions/3440/spiral-of-theodorus)
Jason S
+1  A: 

It depends on your needs and on your field.

When you multiply you have to pick a generator of Fx. When you are adding you have to use the fact that F is a vector space over some smaller Fpm. In practice what you do a lot of time is some mixed approach. E.g. if you are working over F256, take a generator X of F256x, and let G be it's minimal polynomial over F16. You now have

(sumi smaller then 16 ai Xi)(sumj smaller then 16 bj Xj)= sum_k sumi+j = k ai bj Xi+j

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

Finanly, in the rare case where pn = 22n, 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.

David Lehavi
A: 

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.

Keith Randall