Re: finite field

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

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