# General advice on multiplying polynomials in a finite field?

Any tips on how to write the multiplication table in general for a finite field of polynomials (specific example: $F = (\mathbb{Z}/2\mathbb{Z})[x]/(x^2+x+1)$. I know that $F$ has four elements here, $\{0,1,x,x+1\}$, and I know how to make a multiplication table for this. But it gets very tricky with "bigger" fields of polynomials, as modding elements becomes difficult. Any tips?

-
Please clarify: do you actually want a multiplication table, or do you just want to be able to compute products? – Hurkyl Mar 1 '13 at 8:06

If you're in one variable modding elements is just long division. It can be a little tedious but it is a straightforward process. If things are really big and you don't want to do it by hand there are free computer programs that can handle this. You can also try to use wofphram alpha. If it gives you an answer over the rationals then you can clear fractions and reduce mod $p$ to get an answer over a prime field.

If you'd like to do it by hand having a normal form for representatives of the cosets is helpful. It's easier to tell when things are equal that way. For the example above the normal form would be a coset representative that has only a constant and degree $1$ term (because you know $x^2 = x + 1$ in the quotient). Having a normal form will also work in a lot of situations where multiple variables are involved.

If there are multiple variables and no obvious normal form then you can resort to a Grobner basis. You really don't want to do this way by hand though. Again, computer programs are helpful here. I would recommend Macaulay2.

-

A popular solution (for example in a computer implementation of a finite field) is to use discrete logarithms. As the multiplicative group of a finite field is cyclic, all the non-zero elements can be written as powers of $g^i, i=0,1,\ldots,q-2,$ of a generator $g$, aka a primitive element. The discrete log table then maps the element $g^i$ to the exponent $i$, i.e. $\log_g(x):=i$, when $g^i=x$. The values of this function are stored in a table, usually sorted lexicographically according to the coefficients of $x$ with respect to some monomial basis.

Then you can multiply two elements $a$ and $b$ easily by the process of: 1) find $i,j$ such that $a=g^i, b=g^j$ (I usee a table indexed by $a$), 2) compute $i+j\equiv k \pmod{q-1}$, 3) look up the answer $g^k$ (another table). If we know the minimal polynomial of the primitive element, then it is easy to generate the tables as part of the program initialization routine - provided that the field is not too large. Note that the values of the function $\log_g$ reside in the residue class ring $\mathbb{Z}_{q-1}$.

See this answer by Dilip Sarwate for an interesting tweak of discrete log tables, and the latter half of this answer by yours truly for an example of generating the log table for the field of 8 elements (and a link to a log table of the field of 256 elements).

Another possibility that has been used is the so called Zech logarithm. The idea is to internally represent the elements by their logarithms only, and then use a single table designede to help you with the addition of two elements (addition becomes the harder task, if you only have the logarithms). The wikipedia page on that contained a lot of horrid misconceptions, and I didn't have the time to fix it, so I will not endorse Wikipedia here. Go to a math library.

-
If your finite fields are very large, like a couple hundred bits, then normal bases are probably the way to go, and Handbook of Cryptography is your friend and contains the necessary algorithms. – Jyrki Lahtonen Mar 1 '13 at 22:03