FPGA Central

Hi, here

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)

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

Here is a website for calculating 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?

Thanks.

--
Jia

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

"jia" <[email protected]> wrote in message
news:[email protected] ups.com...
> Hi, here
>
> 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)
>
> 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).

There are two different things:

1. The primitive polynomials which are any polynomials that can't be
factored.
2. The particular generator polynomial to extend the GF(p) into GF(p^m).

What are you looking for?

> Here is a website for calculating 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).

Write your own. What is the problem?

> Now, I'm interested in finding the "primitive polynomials over
> GF(2^16)".

There are 2048 of those. Why do you need them?

> While, I don't understand the methods of the above website
> used to caculate the primitive polynomial "over" GF(2^m).

Factoring, by definition.

Vladimir Vassilevsky
DSP and Mixed Signal Consultant
www.abvolt.com

On 10 31 , 7 16 , jaco.versf...@gmail.com 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.

jia <[email protected]> writes:

> On 10 31 , 7 16 , jaco.versf...@gmail.com 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.

I believe the set of mth-order polynomials with coefficients from GF(p)
IS the extension field GF(p^m) since GF(p) is a subset of GF(p^m) - it
is simply the set of all constants in GF(p^m).
--
% Randy Yates % "So now it's getting late,
%% Fuquay-Varina, NC % and those who hesitate
%%% 919-577-9882 % got no one..."
%%%% <[email protected]> % 'Waterfall', *Face The Music*, ELO
http://www.digitalsignallabs.com

Hi Jia,

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


Unfortunately, I am not sure about this definition. I double checked
with another text (Fundamentals of Error-Correcting Codes, Huffman and
Pless), which gave the same definition as Lin and Costello, again only
for GF(2). I think that when we move to extension fields (GF(2^m)),
we define and work with minimal polynomials.

Sorry, I got a bit rusty on the coding.

The guys at sci.math might be able to help as well.

Hope this helps a bit
Jaco

Hi,

Here is a definition from Wolfram: http://mathworld.wolfram.com/PrimitivePolynomial.html.
A primitive polynomial is only defined over the base field GF(p).

On Nov 1, 9:04 am, jaco.versf...@gmail.com wrote:
> Hi Jia,
>
> > 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)?
>
> Unfortunately, I am not sure about this definition. I double checked
> with another text (Fundamentals of Error-Correcting Codes, Huffman and
> Pless), which gave the same definition as Lin and Costello, again only
> for GF(2). I think that when we move to extension fields (GF(2^m)),
> we define and work with minimal polynomials.
>
> Sorry, I got a bit rusty on the coding.
>
> The guys at sci.math might be able to help as well.
>
> Hope this helps a bit
> Jaco

On 10 31 , 11 10 , "Vladimir Vassilevsky"
<antispam_bo...@hotmail.com> wrote:
> "jia" <jia.qing...@gmail.com> wrote in message
>
> news:[email protected] ups.com...
>
> > Hi, here
>
> > 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)
>
> > 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).
>
> There are two different things:
>
> 1. The primitive polynomials which are any polynomials that can't be
> factored.
> 2. The particular generator polynomial to extend the GF(p) into GF(p^m).
>
> What are you looking for?
>
> > Here is a website for calculating 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).
>
> Write your own. What is the problem?
>
> > Now, I'm interested in finding the "primitive polynomials over
> > GF(2^16)".
>
> There are 2048 of those. Why do you need them?
>
> > While, I don't understand the methods of the above website
> > used to caculate the primitive polynomial "over" GF(2^m).
>
> Factoring, by definition.
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Consultantwww.abvolt.com

Hi Vladimir Vassilevsky ,

Thanks for your reply.

But, it seems that you didn't distinguish the concept of "irreducible
polynomial" and "primitive polynomial".

Although "irreducible" and "prime" have the same meaning for natural
numbers, hmmm... for polynomials, I think, they are different.

--
Jia

On Nov 1, 9:59 am, jia <jia.qing...@gmail.com> wrote:
> On 10 31 , 11 10 , "Vladimir Vassilevsky"
>
>
>
> <antispam_bo...@hotmail.com> wrote:
> > "jia" <jia.qing...@gmail.com> wrote in message
>
> >news:[email protected] oups.com...
>
> > > Hi, here
>
> > > I understand the meaning of "primitivepolynomialof GF(p^m)", which
> > > means the coefficients of thepolynomialis from GF(p) where p denotes
> > > a prime number (e.g. p=2)
>
> > > However, as to the meaning of "primitivepolynomialover GF(p^m)", I
> > > think, it means the coefficients is from GF(p^m), not from GF(p).
>
> > There are two different things:
>
> > 1. Theprimitivepolynomials which are any polynomials that can't be
> > factored.
> > 2. The particular generatorpolynomialto extend the GF(p) into GF(p^m).
>
> > What are you looking for?
>
> > > Here is a website for calculating the "primitivepolynomials 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).
>
> > Write your own. What is the problem?
>
> > > Now, I'm interested in finding the "primitivepolynomials over
> > > GF(2^16)".
>
> > There are 2048 of those. Why do you need them?
>
> > > While, I don't understand the methods of the above website
> > > used to caculate theprimitivepolynomial"over" GF(2^m).
>
> > Factoring, by definition.
>
> > Vladimir Vassilevsky
> > DSP and Mixed Signal Consultantwww.abvolt.com
>
> Hi Vladimir Vassilevsky ,
>
> Thanks for your reply.
>
> But, it seems that you didn't distinguish the concept of "irreduciblepolynomial" and "primitivepolynomial".
>
> Although "irreducible" and "prime" have the same meaning for natural
> numbers, hmmm... for polynomials, I think, they are different.
>
> --
> Jia

Hi Jia,

There is a C program for finding all primitive polynomials up to
GF( 2^60 ) along with a theoretical explanation in

http://www.seanerikoconnor.freeserve.../overview.html

Regards,

Sean