Re: Primitive polynomials over GF(2^m)


hagman wrote:
On 1 Nov., 09:37, jia <jia.qing...@xxxxxxxxx> wrote:
Hi, here,

I am dealing with error correction codes for telecommunication.

In the book "Error Control Coding" second edition (By Lin and
Costello), the "irreducible polynomials" and "primitive polynomials"
are defined as below:

An irreducible polynomial over GF(2) is defined as a polynomial P(x)
which is not divisible by any polynomial over GF(2) of degree less
than m but greater than zero.

A primitive polynomial is an irreducible polynomial of degree m with
the added constraint that the smallest integer n for which P(x)
divides X^n + 1 is n = 2^m - 1. ..(1)


That's not the usual definition of primitive.

I don't agree! The usual definition is that a primitive polynomial is
one whose roots are generators of the multiplicative group of the
extension field, and the definition given above is equivalent to that.

Rather, if we have a field extension L/K and alpha is an element of L
such that L = K[alpha], then alpha is called a primitive element
and its irreducible polynomial P -- which has the property that
L = K[X]/(P) -- is called a primitive polynomial.
The constraint you give is equivalent to the above if K=GF(p) for
some prime p:
If P is the irreducible polynomial of alpha and has degree d,
then 1, alpha, alpha^2, ..., alpha^{d-1} are K-linearly independant
and all higher powers alpha^k are in the span of these.
Thus for alpha to be primitive, it is necessary (and sufficient)
to have dim_K L = d.
If L=GF(p^n) and K=GF(p^m) then this dimension is simply n/m.
Note that for finite fields L=GF(p^n) the multiplicative group L^* is
cyclic
of order p^n-1, hence all elements of L^* are roots of X^(p^n)-1,
especially alpha must be a root, i.e. P must divide X^(p^n)-1.
OTOH, P must not divide X^k-1 for any smaller k for then the powers
of alpha would all be in (the multiplicative group of) a smaller
field than L.

I don't think that's right. An element of multiplicative order 5 in
the field of order 16 is primitive over the field of order 2 according
to your definition but not according to (what I claim is) the usual
definition.

Note that its minimal polynomial divides X^5 - 1, whereas a primitive
element would have order 15, and the smallest k for which its minimla
polynomial divides X^k-1 is 15.

Derek Holt.


==========
However, when we move to the extension field GF(2^m), there is no
definition about primitive polynomials in this book. I also checked
with other books, the same thing happened.


The extension field GF(2^m) is extended by GF(2) with "a primitive
polynomial of degree m over GF(2)". But I really don't know how to
find such primitive polynomials over GF(2^m).
As far as I know that the coeffients of the primitive polynomials over
GF(2^m) is from the field GF(2^m).

One way to find primitve polynomials of degree d over K=GF(p^m) would
be
to look for primitive polynomials of degree m*d over GF(p) and
factor thes over K.


Here is a reference website for finding the primitive polynomials over
GF(2^m)http://www.theory.cs.uvic.ca/~cos/gen/poly.html

But, the programs listed on that website is only from GF(2)--GF(8).
Now, I'm interested in finding the "primitive polynomials over
GF(2^16)". While, I don't understand the methods of the above website
used to caculate the primitive polynomial over GF(2^m).

Could anybody give me some light on that?

.

Loading