> < ^ Date: Tue, 13 Jul 1999 14:16:03 +0200 (CEST)
> < ^ From: Frank Luebeck <frank.luebeck@math.rwth-aachen.de >
< ^ Subject: Re: polynomials over finite fields

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