ApCoCoA-1:Representation of finite fields

From ApCoCoAWiki
Revision as of 20:07, 30 March 2008 by Dheldt (talk | contribs) (fixing formula)

To represent a finite field of charakteristic 2 in ApCoCoA an integer is used.

For example, lef . So we have a field with elements, namely one representation of . The fields elements are 0, 1, x, and x+1 (choosing their cannonical representatives). In the ring of integers, the elements 0,1,2 and 3 are chosen to represent the field. To map between both sets the substitution map, substituting x with 2 is chosen, so we have

0 <-> 0
1 <-> 1
2 <-> x
3 <-> x+1.

A polynomial Ring Z[y[1..3]]; can be used to represent . Therefore, we map Z[y[1..3]]; to Z/(4)[1..3]]; and interpret each integer via the above described map. So the polynomial 3y[1] + 1y[2] + 5y[3] - 1 y[1]y[2]; is first mapped to 3y[1] + 1y[2] + 1y[3] +3 y[1]y[2]; which means the polynomial .

To compute a Groebner basis in one of the implemented finite fields, polynomials with integer coefficients are used and sent to the ApCoCoAServer. These polynomials are then interpreted as described above. Then a Gr\"obner basis is computed and the results were sent back, again as polynomials with integer coefficients.

In case you have represented your polynomials in the graphical user interface, using an additional indeterminate (e.g. x like above), you can use CoCoA's subst() command and substitute x with 2 to compute a integer representation and send this to the server. The corresponding CoCoAL code could be as follows:

Use Z/(2)[x,y[1..3]];
Modulus := x^2 + x + 1; -- the polynomial to create the field

Gens := [...]; -- your generators in CurrentRing()/(Modulus);
Gens := [NR(G,[Modulus])| G In Gens]; -- first, reduce the generators, just to be sure.

Use Z[x,y[1..3]];
IntegeredGens := [Sum([Subst(BringIn(M),[ [x,2 ] ]) |M In Monomials(G)]) |G In Gens];

Use Z[y[1..3]];
IntegeredGens := [BringIn(G)| G In IntegeredGens]; -- the generators in the integer representation

dheldt 16:52, 5 March 2008 (CET)

If you have some polynomials in integer representation you can also compute their 'meaning', which is then the inverse of above's transformation. To achieve this, you could apply:

Use Z[y[1..3]];

IntegeredGens := [3y[1]];
--IntegeredGens := [...]; -- your generators in integer representation.

Use Z/(2)[x,y[1..3]];
Modulus := x^2 + x + 1;
 Images := [0];
 For I:=0 To Deg(Modulus)-1 Do
	Images :=Concat(Images, [x^I +Im | Im In Images]);

Gens := [ Sum([ Images[Mod(LC(M),2^Deg(Modulus))+1]*LogToTerm(Concat([0],Log(M)))  | M In Monomials(G)]) |G In IntegeredGens];

dheldt 16:52, 5 March 2008 (CET)

More details on the construction of these fields is contained in the article HowTo:Construct_fields.