Dear gap-forum readers,

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 ?

Michel Lavrauw.

Miles-Receive-Header: reply