Re: Nomenclature question

From: Kristian Gjøsteen (kristiag+news_at_math.ntnu.no)
Date: 10/01/04 

Date: Fri, 1 Oct 2004 12:45:09 +0000 (UTC)

BRG <brg@nowhere.org> wrote:
>Kristian Gjøsteen wrote:
>
>> To me, the words "p(x) is primitive in GF(N)" do not make sense, although
>> the meaning is clear from context.
>
>I agree that the wording here was possibly misleading since it might or
>might not make sense depending on what the original poster really meant.
>However I am not sure that the context really resolves this.

Your statement seems clear from context. What the original poster
meant is anybody's guess.

>The problem is that the words "P(x) is primitive in GF(N)" do make sense
>since the concept of being 'primitive' applies in any finite field even
>though we tend to associate the concept only with the base field.
>
>Hence, for example, there are six second order polynomials that do not
>factor in GF(4) and a number of these generate GF(16) over GF(4). It is
>hence possible to claim that these polynomials are "primitive in GF(4)".

Yes, this is possible. I still do not like the wording. A polynomial
is irreducible _over_ a field, so it should also be primitive _over_
a field, not _in_. (An _element_ could be primitive _in_ a field _over_
a ground field, though.)

If the original poster meant to ask if his polynomial was primitive
over the finite fields, the answer is clearly no in both cases. Note
that the OP's polynomial x^3+x+1 is defined over GF(2).

Suppose we have a finite field F, a finite extension field E of F,
and a polynomial p(x) in F[x]. If p(x) is reducible over E, then p(x)
is not primitive. If p(x) is irreducible over E, we get an extension
field K=E[x]/(p(x)) of E.

Since p(x) must then also be irreducible over F, we get an extension
field L=F[x]/(p(x)). Since F is a subfield of E, L is a subfield of K,
and they are not equal.

But the image of the polynomial x in K=E[x]/(p(x)) is in the subfield
L=F[x]/(p(x)), so x cannot generate the multiplicative group of K.
Therefore p(x) is not primitive over E. 

-- 
Kristian Gjøsteen

Relevant Pages

  • Re: Nomenclature question
    ... >>might not make sense depending on what the original poster really meant. ... >>However I am not sure that the context really resolves this. ... >>Hence, for example, there are six second order polynomials that do not ... I still do not like the wording. ...
    (sci.crypt)
  • Re: Looking for algorithm
    ... > sequence of C's as your checksum.) ... My pitiful finite field knowledge is being sorely tested, ... I've used PARI/GP to test a few polynomials, to see how well I understood ... For example for ring operations I use "modulo the polynomial ...
    (sci.crypt)
  • Re: Properties of polynomials over finite fields
    ... > multivariate polynomials over a finite field F in their proofs. ... > from the affine space F^k to the field F and make various claims about ...
    (sci.math.research)
  • Re: Public Key, Symbolic Calculation
    ... that polynomials with coefficients in Q are really the same as ... But the algebraics over Z are not a finite field, ... explained by someone who isn't a professional mathematician. ... would "get" this Berlekemp method, if it were written more clearly. ...
    (sci.crypt)
  • Re: JSH: Understanding polynomials
    ... In the context it is *not* irrelevant. ... normally in the context of polynomials.) ... there was no clear visible connection between the constant term of P ... *would* have been a clear visible connection. ...
    (sci.math)