How can multiplication be realized in finite fields?

Question

If F: = GF (p ^ n) is a finite field with p ^ n elements, where p is a prime and na is a natural number, is there an effective algorithm for generating the product of two elements in F?

Here are my thoughts:

I know that the standard construction of F is to take an irreducible polynomial f of degree n in GF (p), and then consider the elements of F as polynomials in the factor GF (p) [X] / (f) and I have a feeling that this is probably the right approach, since polynomial multiplication and addition should be easily implemented, but somehow I don’t understand how this can actually be done. For example, how to choose the appropriate f and how can I get the equivalence class of an arbitrary polynomial?

Answer 1

First, choose an irreducible polynomial of degree n over GF [p]. Just create a random, random polynomial irreducible with a probability of ~ 1 / n .

To check your random polynomials, you will need code to compute 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 you compute the remainder modulo your irreducible polynomial.

It is very easy to code simple versions of this circuit. You can be arbitrarily complex in how you implement, say, a modulo operation. See modular exponentiation , Montgomery multiplication, and FFT multiplication.

Answer 2

Whether there is an effective algorithm for multiplying elements in GF (p ^ n) depends on how you represent the elements of GF (p ^ n).

As you say, one way to really work in GF (p) (X) / (f). Addition and multiplication are relatively simple here. However, defining a suitable irreducible polynomial f is not easy - as far as I know, there is no efficient algorithm for calculating a suitable f.

Another way is to use what is called the Zech logarithms . Magma uses pre-computed tables to work with small leaf fields. It is possible that GAP does too, although its documentation is less clear.

Computing using mathematical structures is often quite complicated. Of course, you did not miss anything obvious here.

Answer 3

It depends on your needs and on your field.

When multiplying, you must choose a generator F ^x . When you add, you should use the fact that F is a vector space over a smaller F _{p ^m} . In practice, what you do a lot of time is a mixed approach. For instance. if you are working on F ₂₅₆ , take a generator X from F ₂₅₆ ^x and let G be the minimum polynomial over F _{16sub>. Now you have}

(amount _{i less than 16} a _i X ⁱ ) (amount _{j less than 16} b _j X ^j ) = sum_k sum _{i + j = k} a _i b _j X ^{i + J}

All you need to do for effective multiplication is to store the multiplication table F ₁₆ and (using G) the construct X ^ m in terms of lower powers of X and elements in F <sub> 16sub>

Finally, in the rare case when p ⁿ = 2 ^{2 n} you get the field “Conways nimbers (see Conways) of the path" or in the volume of Knut 4A, section 7.1.3), for which there are very efficient algorithms.

Answer 4

Galois field arithmetic library (C ++, mod 2, not like that supports other simple elements)

LinBox (C ++)

MPFQ (C ++)

I have no personal experience with them (however, I made my own primitive C ++ classes for Galois fields of degree 31 or less, nothing too exotic or not worth copying). Like one of the commentators mentioned, you can check out mathoverflow.net - just ask nicely and make sure you do your homework first. Someone should know which mathematical software is suitable for manipulating finite fields, and it is close enough to the mathoverflow area of ​​interest, so that a clearly formulated question should not be closed.