ApCoCoA:Representation of finite fields

From CoCoAWiki
Jump to: navigation, search

<command> <title>Representation of finite fields</title> <description> To represent a finite field of characteristic 2 in ApCoCoA an integer is used. <par/> For example, let K = F_2[x]/(x^2+x+1). So we have a field with 2^2 = 4 elements, namely one representation of F_4. The elements of the field are 0, 1, x, and x+1 (choosing their canonical representatives). <par/> 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

<example> 0 maps to 0 1 maps to 1 2 maps to x 3 maps to x+1. </example>

A polynomial Ring Z[y[1..3]] can be used to represent F_4[y_1, y_2, y_3]. Therefore, we map Z[y[1..3]] to Z/(4)[y[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 (x+1)y_1 + y_2 + y_3 + (x_1)y_1 y_2. <par/> 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 Groebner basis is computed and the results were sent back, again as polynomials with integer coefficients. <par/> In case you have represented your polynomials in the graphical user interface, using an additional indeterminate (e.g. x like above), you can use the <ref>Subst</ref> command of CoCoA and substitute x with 2 to compute a integer representation and send this to the server. The corresponding CoCoAL code could be as follows:

<example>

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

</example>

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

<example>

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

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

</example> </description>

<key>finite</key> <key>field</key>

<wiki-category>Package_charP</wiki-category> </command>