Gerhard Niklasch on Wed, 20 Dec 2000 23:52:04 +0100 (MET) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: finite field |
In response to: > Message-ID: <005901c06a0d$b15487c0$87faf9c1@default> > From: "Elie Cali" <Elie.Cali@wanadoo.fr> > To: <pari-users@list.cr.yp.to> > Subject: finite field > Date: Tue, 19 Dec 2000 01:55:22 +0100 > > I am new on Pari. I would like to consider the 2^n elements fiite field, for > a given n, with the 2^n-1 roots of unity as representatives, and I would > like to make some computing on these elements (for instance, compute xi + > xi' + 1 for given xi and xi') or solve an equation (for instance xi + xi' + > 1 = 0 for a given xi). Can I do this with Pari? Sure. There are, as usually, several ways to go about it, and it depends on the size of n which of them are more or less attractive. A simple one is as follows (taking n=3): gp > f=polcyclo(7,x); // in fact, the cyclotomic poly will use x by default gp > factormod(f,2) // get irred factors. Either of them will work %2 = [Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2) 1] [Mod(1, 2)*x^3 + Mod(1, 2)*x^2 + Mod(1, 2) 1] gp > g=%[1,1]; // first component of first factor/exponent pair gp > z0=Mod(x,g); // primitive (2^n-1)th root of unity gp > xi0=z0*Mod(1,2) // this is really a tensor product, %5 = Mod(Mod(1, 2)*x, Mod(1, 2)*x^3 + Mod(1, 2)*x + Mod(1, 2)) gp > /* and does behave like a primitive element of the desired field. comment> At this point, depending on your needs, you may wish to create comment> a table of powers -- if n is small enough to keep such a table comment> in memory all the time: */ gp > xi_pwr=vector(7,j,xi0^j); // xi_pwr[1]=xi0, xi_pwr[7] represents 1 gp > /* and we might as well construct the table of discrete logs to comment> go with it, for the inverse mapping. I'm inventing a trick comment> to map a nonzero field element to an integer in the range comment> 1...2^n-1 for use as an array lookup index, and code this comment> as a gp function: */ gp > xi_idx(y)=subst(lift(lift(y)),x,2); gp > xi_idx(xi0) %7 = 2 gp > xi_idx(xi0^4) %8 = 6 gp > /* (the idea being to map the sequence of coefficients of the comment> representing polynomial into the bits of an integer. Again, comment> there are many ways to do this.) */ gp > xi_dlg=vector(7,j,0); gp > for(j=1,7,xi_dlg[xi_idx(xi_pwr[j])]=j); gp > /* And behold, now you can figure out the solution to xi0 + xi' + 1 = 0 comment> in the form xi' = some precise power of xi0 : */ gp > xi_dlg[xi_idx(1-xi0)] %11 = 3 gp > /* and, sure enough, this is the solution: */ gp > xi0 + xi0^% + 1 %12 = 0