> < ^ From:

> < ^ Subject:

Dear GAP - Forum,

M. 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).

May it be that you calculate X^d before reducing it modulo f ?

This would certainly take a very long time (and also much memory) if

q is 'large'.

Calculating X^d mod f could be done much faster by a simple method

analogous to that used for modular exponentiation for integers, which

reduces the result after each multiplication modulo the respective

modulus.

Best regards,

Stefan Kohl

> < [top]