Re: Primitive polynomials over GF(2^m)

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.
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.



==========
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?


.

Relevant Pages

  • Re: Primitive polynomials over GF(2^m)
    ... extension field, and the definition given above is equivalent to that. ... coefficients" is not a sensible concept for polynomials over fields. ... definitions of primitive polynomials over finite fields. ... as meaning a polynomial whose roots generate the multiplicative group ...
    (sci.math)
  • Re: Shamir sharing and GF(2^n)
    ... the field element except 0 as a power of x. ... building log tables to do the arithmetic because it means there's an ... grim) little utility program which finds primitive polynomials. ...
    (sci.crypt)
  • Re: Primitive polynomial over/of GF(p^m)
    ... means the coefficients of the polynomial is from GFwhere p denotes ... The primitive polynomial used to create the extension field, ... Primitive polynomials in the specific field that you are working ...
    (comp.dsp)
  • Primitive polynomials over GF(2^m)
    ... I am dealing with error correction codes for telecommunication. ... definition about primitive polynomials in this book. ... the programs listed on that website is only from GF--GF. ...
    (sci.math)
  • Re: Primitive polynomial over/of GF(p^m)
    ... means the coefficients of the polynomial is from GFwhere p denotes ... The primitive polynomial used to create the extension field, ... Primitive polynomials in the specific field that you are working ...
    (comp.dsp)