Re: question about finite fields,please help me!!!

[Paul van Wamelen <wamelen@math.lsu.edu>]

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