Karim BELABAS on Mon, 20 May 2002 14:47:32 +0200 (MEST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: question about finite fields,please help me!!! |
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/