Re: Primitive polynomials over GF(2^m)


Timothy Murphy wrote:
Derek Holt wrote:

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

Except it should be x^n - 1, I guess ...

Same thing in characteristic 2, but I agree it would be preferable to
write x^n-1.

Sorry, didn't read carefully enough.
Of course the result holds in any characteristic (with p^m - 1).

Incidentally, I never realized that primitive polynomial
had another meaning: a polynomial in Z[x] with coprime coefficients.
I hope that meaning is obsolete.

I don't think it is obsolete, but fortunately there is very little
danger of any confusion. One meaning only applies to finite fields,
and and set of elements of a field is coprime, so "coprime
coefficients" is not a sensible concept for polynomials over fields.

Incidentally, both MathWorld and Wikipedia have incorrect/inconsistent
definitions of primitive polynomials over finite fields.

MathWorld:
A primitive polynomial is a polynomial that generates all elements of
an extension field from a base field.

But then in the following discussion, they are clearly thinking of it
as meaning a polynomial whose roots generate the multiplicative group
of the field.

Wikipedia:
In field theory, a branch of mathematics, a primitive polynomial is
the minimal polynomial of a primitive element of the extension field
GF(p^m). In other words, a polynomial F(X) with coefficients in GF(p)
= Z/pZ is a primitive polynomial if it has a root in GF(p^m) such
that the linear span of \{1, \alpha, \alpha^2, \alpha^3,\dots\} over
GF(p) is the entire field GF(p^m), and moreover, F(X) is the smallest
degree polynomial having as root.

The "in other words" part of the definition is wrong, but the
following discussion is correct.

Derek Holt.

.

Relevant Pages

  • Re: JSH: Keep it simple
    ... arbitrary rule that you take roots of monic polynomials with integer coefficients. ... integral root is divisible by something that is coprime to ... Your claim regarding rational roots of this polynomial cannot do that, since the standard theory makes no claims regarding common factors among such roots. ...
    (sci.math)
  • Re: Orthogonal polynomials (was Chebyshv, etc.)
    ... Legendre, Chebyshev, Hermite, etc.) have n real roots in the ... This general property of orthogonal polynomials is proved as ... you can simply ignore any zeros ... If alpha is a real root of phi_k, ...
    (sci.math)
  • Re: New paper, algebraic integers, Galois Theory
    ... > Now consider the case that m, f, and u are algebraic integers, then I ... > something about the factors of roots of monic polynomials with integer ... Note that this claim does not require Galois Theory, ...
    (sci.math)
  • Re: Question on algebraic numbers
    ... adjoining to Q the roots of all polynomials over Q. ... extensions of Q which have a solvable Galois group. ... solutions by radicals). ...
    (sci.math)
  • Re: Some math, algebraic integers
    ... >> Like, yeah, the polynomial has rational roots, which is what I already ... are mathematicians as a group as big about their ... > be related to the coefficients of their irreducible polynomials. ... So I said, hey, it all follows in the ring of algebraic integers too! ...
    (sci.math)