How could one implement multiplication in finite fields?

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, an开发者_如何学运维d how can I get the equivalence class of an arbitrary polynomial?

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.

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.

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.

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.

Assume this is the question for an algorithm performing multiplication in finite fields, when a monic irreducible polynomial f(X) is identified (else consider Rabin's Test for Irreducibility)

You have two polynomials of degree n-1

A(X) = a_0 + a_1*X + a_2*X^2 + ... + a_(n-1)*X^(n-1) and
B(X) = b_0 + b_1*X + b_2*X^2 + ... + b_(n-1)*X^(n-1)

coefficients a_k, b_k are out of representatives {0,1,...,p-1} of Z/pZ.

The product is defined as

C(X) = A(X)*B(X) % f(X),

where the modulo operator "%" is the remainder of the polynomial division A(X)*B(X) / f(X).

Following is an approach with complexity O(n^2)

1.) By distributive law the product can be decomposed to

  B(X) * X^(n-1) * a_(n-1)
+ B(X) * X^(n-2) * a_(n-2)
+ ...
+ B(X) * a_0

=

  (...(a_(n-1) * B(X)  * X 
   +  a_(n-2)  * B(X)) * X
   +  a_(n-3)  * B(X)) * X
   ...
   +  a_1      * B(X)) * X
   +  a_0      * B(X)

2.) For the %-operator is a ring homomorphism from Z/pZ[X] onto GF(p^n) it can be applied in each step of the iteration above.

 A(X)*B(X) % f(X) =

  (...(a_(n-1) * B(X)  * X % f(X)
   +  a_(n-2)  * B(X)) * X % f(X)
   +  a_(n-3)  * B(X)) * X % f(X)
   ...
   +  a_1      * B(X)) * X % f(X)
   +  a_0      * B(X)

3.) After each multiplication with X, i.e. a shift in the coefficient space, you have a polynomial T_k(X) of degree n with element t_kn * X^n. Reduction modulo f(X) is done by

T_k(X) % f(X) = T_k(X) - t_kn*f(X),

which is a polynomial of degree n-1.

Finally, with reduction polynomial

r(x) := f(x) - X^n  and

T_k(X) =: t_kn * X^n + U_(n-1)(X)

T_k(X) % f(X) = t_kn * X^n + U_(n-1)(X) - t_kn*( r(x) + X^n)
              = U_(n-1)(X) - t_kn*r(x)

i.e. all steps can be done with polynomials of maximum degree n-1.