3
$\begingroup$

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)$ ?

$\endgroup$
2
  • $\begingroup$ Is there a specific $N$, or are you looking for something that works for all $N$? $\endgroup$
    – Alfonso Fernandez
    Mar 24, 2013 at 23:06
  • $\begingroup$ N will be given as input. I need to compute for that N ! Actually I need to compute Addition and multiplication Table so I need Irreducible polynomial first. I dont know any other method to compute tables directly, if exists. $\endgroup$
    – geek_guy
    Mar 24, 2013 at 23:07

3 Answers 3

Reset to default
5
$\begingroup$

One choice would be the Conway polynomial.

See also this page by Frank Lübeck.

$\endgroup$
0
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .