> < ^ From:

> < ^ Subject:

Dear GAP Forum,

Michel Lavrauw wrote

To find a primitive polynomial over a finite field,

I did the following:pring:=UnivariatePolynomialRing(<finite field>);

X:=IndeterminatesOfPolynomialRing(pring)[1];

SetName(X,"X");Suppose the field is GF(q) and I want a primitive polynomial of degree 3.

Then I generate a random polynomial by generating random coefficients

in the field. Let f be such a random polynomial. To check if it is primitive

I make a list of all divisors d of q^3-1 such that (q^3-1)/x is prime.

Then f is primitive if X^d mod f is different from One(GF(q)) for all

d in list with d < q^3-1.Calculating X^d mod f takes a long time in Gap ( even if we work over a

prime field).

In Maple however, (over a prime field) it takes no time at all to check

if a polynomial is primitive.Is there a better way in Gap4 to find a primitive polynomial ?

One reason why checking primitivity (for example in Maple) is faster

than the GAP code sketched above is that writing down `X^d mod f' in GAP

means first to compute the power `X^d' and then to reduce

this polynomial modulo `f'.

Here one can do better by reducing modulo `f' during the powering.

A (documented) GAP function for this purpose is `PowerModCoeffs'.

For small prime values of q and small degrees,

GAP stores a list of Conway polynomials.

These are special primitive polynomials

that are used to implement GAP's finite field arithmetic.

For example, GAP stores the degree 3 Conway polynomials for

all primes q up to 100;

for larger primes q, the Conway polynomial of degree 3 can

be computed in acceptable time using `ConwayPolynomial'.

(The computation of Conway polynomials becomes more time

consuming for larger degree, in particular if the degree is

not a prime.)

One possibility to write GAP code for finding an arbitrary primitive

polynomial would be to modify the code for `ConwayPolynomial' accordingly,

which mainly means to remove the compatibility checks from this code.

Kind regards,

Thomas

Miles-Receive-Header: reply

> < [top]