Paul van Wamelen on Sat, 18 May 2002 10:46:37 -0500 (CDT)

```On Fri, 17 May 2002, UMBERTO COVA wrote:

> First of all,thanks for your help!
> I need to know how I can determine a generator of a finite field using Pari;is there a specific function that builds a primitive polynomial of degree n over a field Fp(something similar to ffinit)?

I don't believe anything is built-in but the following code will do what
you want:

\\ This finds a random primitive element in the finite field with p^n
\\ elements
ranffinitprim(p,n) =
{
local(ffp,dum,dn,dum2);
ffp = ffinit(p,n,x);
dum = factor(p^n-1)[,1];
while(1,
dn = 1;
dum2 = Mod(sum(i=1,n,Mod(random(),p)*x^(i-1)),ffp);
for(i=1,length(dum),
if(lift(lift(dum2^((p^n-1)/dum[i])))==1,dn=0));
if(dum2 == Mod(0,ffp),,
if(dn == 1,return(dum2))))
}

> Futhermore,how can I realize a modular exponentiation of a polynomial (f(x))^a (mod g(x)) without problems of overflow and in a reasonable time?
>
If you do Mod(f(x),g(x))^a instead of Mod(f(x)^a,g(x)) the *right thing*
happens automatically.

Enjoy!
Paul van Wamelen
```