Irreducible Polynomial of degree N

Question

In my project I need to generate addition and multiplication table of $GF(2^N)$.

I think first of all i need irreducible Polynomial of degree $N$.

So, Is there any algorithm to find Irreducible polynomial of degree $N$ ? Or Is there any other way to find $GF(2^N)$ ?

Answer 1

One choice would be the Conway polynomial.

See also this page by Frank Lübeck.

Answer 2

For a lot on computing in finite fields see the (sadly unfinished) "Computation in Finite Fields" by John Kerl.

Answer 3

This is surprisingly tricky. I face this task quite often, but only for relatively small $N$ (up to twenty or so), so I use a look-up-table. Using primitive polynomials I can then build the entire logarithm table as described here.

If $N$ is a larger number, then you are not going to build a logarithm table, but need to simply be able to carry out multiplication of long vectors of bits. There are algorithms for finding relatively efficient normal bases that will help you there. The Handbook of Cryptography describes something. That does treat different values of $N$ somewhat unequally (cannot be helped, really). IIRC, if $N+1$ or $2N+1$ is a prime such that the residue class of two has order $N$ in $\mathbb{Z}_{N+1}^*$ (resp. $\mathbb{Z}_{2N+1}^*$), then you get something really efficient.