1
$\begingroup$

Why generator polynomial of the cyclic group $GF(2^m)$ are irreducible?

$\endgroup$
1
  • 2
    $\begingroup$ Galois fields are not just groups; they are finite fields (en.wikipedia.org/wiki/Finite_field). The generator polynomial needs to be irreducible to ensure that you actually get a field. $\endgroup$ May 13 '15 at 17:27
1
$\begingroup$

It looks like you're confusing two different meanings of "generator polynomial".

First, $GF(2^m)$ is the field $\mathbb F_2[X]/ \langle p\rangle$ for some irreducible polynomial $p$ of degree $m$ over $\mathbb F_2$. This $p$ is sometimes know as the generator polynomial for the field (representation) in question. It needs to be irreducible, because otherwise we're not getting a field, just a ring with zero divisors.

(It turns out that all irreducible polynomials of the same degree give the same field up to isomorphism, so for high-level purposes we don't need to specify which).

Second, however, the multiplicative group of any finite field such as $GF(2^m)$ is always cyclic and so has a generator. Concretely, this generator can be written down as a polynomial of degree $<m$, and that polynomial does not have to be irreducible.

For example, $GF(32)$ can be represented as $\mathbb F_2/\langle X^5+X^2+1\rangle$, because $X^5+X^2+1$ is irreducible.

The multiplicative group of $GF(32)$ is a cyclic group with 31 elements, each of which is a generator (because 31 is prime). So, for example $X^2$ is a generator of the multiplicative group as a cyclic group, but it is plainly not irreducible as a polynomial.

(On the other hand, $X^5+X^2+1$ is not a member of the multiplicative group at all, and so in particular not a generator).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.