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

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

On Sat, 18 May 2002, Paul van Wamelen wrote:

> 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);

Since random() is a congruential generator, you may get an infinite loop
if p = 2. I'd use Mod(random(p), p). And in fact

  dum2 = Mod( Pol( vector(n,i, Mod(random(p), p)) ), 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))))
> }

There is something built-in, very carefully hidden [ used by idealstar() ].
Provided you have an up-to-date development version from the CVS server, and
provided install() works on your system, you can use the following:

  install(FpXQ_gener,GG)

  ffinitprim(p,n) =
  { local(ffp);

    ffp = ffinit(p,n,x);
    Mod(FpXQ_gener(lift(ffp), p) * Mod(1,p), ffp)
  }

(14:07) gp > ranffinitprim(101, 40);
time = 1mn, 40,980 ms.
(14:08) gp > ranffinitprim(2, 100)
 ***   user interrupt after 13mn, 57,260 ms.


(14:28) gp > ffinitprim(101, 40);
time = 940 ms.
(14:28) gp > ffinitprim(2, 100)
time = 330 ms.

Obviously, this is quite a useful routine, so I'll have to make it directly
available to gp someday (with a decent name).

Cheers,

    Karim.

P.S: Sorry about discussing the development version on the pari-users list.
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas
--
PARI/GP Home Page: http://www.parigp-home.de/