Re: Primitive polynomial over/of GF(p^m)

On 10 31 , 7 16 , jaco.versf...@xxxxxxxxx wrote:
Hi Jia,

I am not sure if we have the same definition for a "primitive
polynomial"?

I understand the meaning of "primitive polynomial of GF(p^m)", which
means the coefficients of the polynomial is from GF(p) where p denotes
a prime number (e.g. p=2)

In "Error Control Coding" second edition (By Lin and Costello), 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)

However, as to the meaning of "primitive polynomial over GF(p^m)", I
think, it means the coefficients is from GF(p^m), not from GF(p).

I think that when we move to extension fields, we will now use the
extension field, i.e., if P(x) is a polynomial over GF(p^y), a
primitive polynomial will be an irreducible polynomial over GF(p^y) of
degree m (thus, the coefficients will be from GF(2^y)), such that the
smallest integer n for which P(x) divides X^n + 1 is n = 2^m - 1.

There are two things to distinguish:
1.) The primitive polynomial used to create the extension field, this
will always be from the "base" field, i.e., p = 2,3, 5, etc. As an
example, 1+X + X^3 over GF(2) can be used to generate a finite field
GF(2^3).
2.) Primitive polynomials in the specific field that you are working
in. In this case all polynomials with coefficients in GF(2^3) that
meet (1) will be primitive. (I know that x^7 - 1 over GF(2^3) can be
divided by the following polynomials: (x - \alpha^i), i in {0,1,
2, ... 6}. However, I don't know if (x - \alpha^i) is primitive, but
they are irreducible for sure. (These polynomials are used to create
the generator polynomial of Reed-Solomon codes.)

Hope this helps
Jaco

Hi, Jaco.

I also have the same book "Error Control Coding".

In fact, the terminoly "primitive polynomial" used in that book means
--
"a primitive polynomial of degree m over GF(2)".

What I want to find is the primitive polynomial of degree m over
GF(2^m).

However, there is no definition about primitive polynomial over the
extension of GF(2) in that book. I saw you gave a definition "a
irreducible polynomial over GF(2^m), if the smallest integer n for
which P(x) divides X^n + 1 is n = 2^m - 1", which is similar to the
definition over GF(2).
Are you sure about the definition of the primitive polynomial over
GF(2^m)?

Thanks for your help.

.

Relevant Pages

  • Re: Primitive polynomials over GF(2^m)
    ... I am dealing with error correction codes for telecommunication. ... if we have a field extension L/K and alpha is an element of L ... definition about primitive polynomials in this book. ...
    (sci.math)
  • Re: Integer-Valued Polynomials
    ... polynomials in n indetermintes over D consists of those ... over the extension field K, ... polynomial which is not simply integer coefficients: ...
    (sci.math)
  • 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: Integer-Valued Polynomials
    ... polynomials in n indetermintes over D consists of those ... over the extension field K, ... polynomial which is not simply integer coefficients: ...
    (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)