Hi,

There is a theorem that states that any integer greater than one is
either prime or a product of primes.

I think there is a similar theorem for polynomials, but I can't find
it in my maths handbook.  I have two questions:

A) When working with a polynomial ring F(x), where the coefficients of
the polynomials are from GF(2^m), should the prime polynomials be:
1) monic
2) irreducible in GF(2^m), and
3) degree less than or equal to n,

to give an expression of g(x) = p1(x)p2(x)..pn(x)?


B) How can I find these "prime" polynomials?  

Your time, effort and suggestions will be greatly appreciated
Jaco

Matt Timmermans wrote:
> "Jyrki Lahtonen" <lahtonen@utu.fi> wrote in message
> news:3F571183.2ABA9A9F@utu.fi...
> 
>>Jaco Versfeld wrote:
>>
>>
>>>B) How can I find these "prime" polynomials?
>>>
>>That is not easy. Many textbooks (like the "Bible of finite fields" by
>>Lidl & Niederreiter) have some algorithms for factoring polynomials.
>>They also have the theorem that in the ring GF(q)[x] the product
>>of all prime polynomials of degree dividing a given natural number n
>>is equal to x^(q^n)-x. Thus in theory you will find all the prime
>>polynomials of a given degree by factoring x^(q^n)-x, but I wouldn't
>>recommend this approach except possible for the smallest values of q and
>>  n.

What is not easy is proving a prime is primitive (has maximum cycle of
q-1).  But it's not that hard with a computer.


> 
> Dr. Mike answered this one for me long ago.
> 
> Given a test polynomial P of degree d over GF(q)[x], just calculate
> x^(q^n)-x MOD P for all n <= d/2, and see if the result is zero or divides
> P.
> 
> The big exponentiation can be calculated using the iteratrive square &
> multiply technique commonly used to implement encryption algorithms:
> 
> (x^a)^2 = a^(2a)
> (x^a)^2 * x = a^(2a+1)
> 
> Starting with x^a=1 (a=0), make x^N by choosing the first or second of the
> above equations according to the bits of N, written in binary, in descending
> order.
> 
> Perform all operations mod P to limit the size of the intermediate results.

Thanks Matt!  I'm sure it wouldn't have come out so nicely this time.

Patience, persistence, truth,
Dr. mike

-- 
Mike Rosing
www.beastrider.com                   BeastRider, LLC
SHARC debug tools

Jaco Versfeld wrote:
> 
> Hi,
> 
> There is a theorem that states that any integer greater than one is
> either prime or a product of primes.
> 
> I think there is a similar theorem for polynomials, but I can't find
> it in my maths handbook.  I have two questions:
> 
> A) When working with a polynomial ring F(x), where the coefficients of
> the polynomials are from GF(2^m), should the prime polynomials be:
> 1) monic
> 2) irreducible in GF(2^m), and
> 3) degree less than or equal to n,
> 
> to give an expression of g(x) = p1(x)p2(x)..pn(x)?

A few remarks: The standard notation for the ring of polynomials with
coefficients in a field F is F[x], not F(x). In F(x) you include things
like 1/x, (2x^3-x+1)/(x^2+1), i.e. all the fractions with polynomial numerator
and denominator. About your list:
1) This is often required, for one can alway divide the polynomial with
its leading coefficient. The reason is the same as in the case of the
usual primes, where we prefer to call 3 a prime, but have some doubts
about -3. This is more or less just a choice function selecting from
the collection of irreducibles only one "up to a unit factor". In the case 
of the ring F[x] the units are the non-zero constant (in the ring of integers
the units are +1 and -1).
2) This statement is misleading. GF(2^m) is a field, and hence has
no primes (all the non zero elements are units, hence not primes).
The prime polynomials are irreducible elements in the ring GF(2^m)[x].
3) This requirement is false.
You cannot bound the degree of irreducibles. I would think that
all the books on the subjest should have included a proof of the fact
that in GF(2^m)[x] there are irreducible polynomials of an arbitrarily
high degree. (knowing your interest in coding theory: How else could 
you construct BCH-codes of arbitrarily high length 2^m-1 for any m).

> 
> B) How can I find these "prime" polynomials?

That is not easy. Many textbooks (like the "Bible of finite fields" by
Lidl & Niederreiter) have some algorithms for factoring polynomials.
They also have the theorem that in the ring GF(q)[x] the product
of all prime polynomials of degree dividing a given natural number n
is equal to x^(q^n)-x. Thus in theory you will find all the prime
polynomials of a given degree by factoring x^(q^n)-x, but I wouldn't
recommend this approach except possible for the smallest values of q and n.
For more information about this problem consult books dedicated to the
subject (e.g. Lidl&Niederreiter)

Cheers,

Jyrki

"Jyrki Lahtonen" <lahtonen@utu.fi> wrote in message
news:3F571183.2ABA9A9F@utu.fi...
>
> Jaco Versfeld wrote:
>
> > B) How can I find these "prime" polynomials?
>
> That is not easy. Many textbooks (like the "Bible of finite fields" by
> Lidl & Niederreiter) have some algorithms for factoring polynomials.
> They also have the theorem that in the ring GF(q)[x] the product
> of all prime polynomials of degree dividing a given natural number n
> is equal to x^(q^n)-x. Thus in theory you will find all the prime
> polynomials of a given degree by factoring x^(q^n)-x, but I wouldn't
> recommend this approach except possible for the smallest values of q and
n.
> For more information about this problem consult books dedicated to the
> subject (e.g. Lidl&Niederreiter)

Dr. Mike answered this one for me long ago.

Given a test polynomial P of degree d over GF(q)[x], just calculate
x^(q^n)-x MOD P for all n <= d/2, and see if the result is zero or divides
P.

The big exponentiation can be calculated using the iteratrive square &
multiply technique commonly used to implement encryption algorithms:

(x^a)^2 = a^(2a)
(x^a)^2 * x = a^(2a+1)

Starting with x^a=1 (a=0), make x^N by choosing the first or second of the
above equations according to the bits of N, written in binary, in descending
order.

Perform all operations mod P to limit the size of the intermediate results.

Hi,

Sorry for the late response, but I had to attend a conference.  Thanks
a lot for all the replies

Regards,
Jaco