> < ^ From:

< ^ Subject:

Dear Michel, dear Forum,

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.

I think it is almost ok, what you are doing. You only should learn about

the `PowerMod' command, which is certainly also used in the Maple code you

mentioned. Maybe the following (GAP4) function does what you want:

IsPrimitivePol := function(f, q) local x, one, r, ps, p; x := Indeterminate(GF(q), IndeterminateNumberOfUnivariateRationalFunction(f)); one := x^0; r := q^Degree(f)-1; ps := Set(FactorsInt(q^Degree(f)-1)); for p in ps do if PowerMod(x, r/p, f) = one then return false; fi; od; return true; end;

Also there is a command

AllIrreducibleMonicPolynomialCoeffsOfDegree(n,q);

in GAP4 which gives back what it says.

Best regards, Frank

Miles-Receive-Header: reply

> < [top]