Difference between revisions of "ApCoCoA-1:Representation of finite fields"

From ApCoCoAWiki
(adding a remark, pointing to HowTo:Construct_fields)
m (insert version info)
 
(6 intermediate revisions by 4 users not shown)
Line 1: Line 1:
To represent a finite field of charakteristic 2 in ApCoCoA an integer is used.
+
{{Version|1}}
 
+
<command>
For example, lef <math>K= \mathbb{{F}_2 [x]}_{\setminus(x^2+x+1)</math>.
+
<title>Representation of finite fields</title>
So we have a field with <math>2^2 = 4</math> elements, namely one representation of <math>\mathbb{F}_4</math>. The fields elements are
+
<description>
0, 1, x, and x+1 (choosing their cannonical representatives).
+
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
 
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
+
<example>
1 <-> 1
+
0 maps to 0
2 <-> x
+
1 maps to 1
3 <-> x+1.
+
2 maps to x
 +
3 maps to x+1.
 +
</example>
  
A polynomial Ring Z[y[1..3]]; can be used to represent  
+
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.
<math>\mathbb{F}_4[y_1, y_2, y_3]</math>. Therefore, we map  
+
<par/>
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 <math>(x+1)y_1 + y_2 + y_3 + (x_1)y_1 y_2</math>.
+
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/>
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 the <ref>ApCoCoA-1:Subst|Subst</ref> command of CoCoA and substitute x with 2 to compute a integer representation and send this to the server.
 
 
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:
 
The corresponding CoCoAL code could be as follows:
  
 +
<example>
 
  Use Z/(2)[x,y[1..3]];
 
  Use Z/(2)[x,y[1..3]];
 
  Modulus := x^2 + x + 1; -- the polynomial to create the field
 
  Modulus := x^2 + x + 1; -- the polynomial to create the field
Line 34: Line 39:
 
  Use Z[y[1..3]];
 
  Use Z[y[1..3]];
 
  IntegeredGens := [BringIn(G)| G In IntegeredGens]; -- the generators in the integer representation
 
  IntegeredGens := [BringIn(G)| G In IntegeredGens]; -- the generators in the integer representation
[[User:Dheldt|dheldt]] 16:52, 5 March 2008 (CET) 
+
</example>
  
 
+
If you have some polynomials in integer representation you can also compute their 'meaning', which is then the inverse of the transformation above.
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:
 
To achieve this, you could apply:
 
   
 
   
 +
<example>
 
  Use Z[y[1..3]];
 
  Use Z[y[1..3]];
 
   
 
   
Line 54: Line 59:
 
   
 
   
 
  Gens := [ Sum([ Images[Mod(LC(M),2^Deg(Modulus))+1]*LogToTerm(Concat([0],Log(M)))  | M In Monomials(G)]) |G In IntegeredGens];
 
  Gens := [ Sum([ Images[Mod(LC(M),2^Deg(Modulus))+1]*LogToTerm(Concat([0],Log(M)))  | M In Monomials(G)]) |G In IntegeredGens];
[[User:Dheldt|dheldt]] 16:52, 5 March 2008 (CET)
+
</example>
 
+
</description>
  
More details on the construction of these fields is contained in the article [[HowTo:Construct_fields]].
+
<key>finite</key>
 +
<key>field</key>
  
[[Category:HowTo]][[Category:ApCoCoA]]
+
<wiki-category>ApCoCoA-1:Package_charP</wiki-category>
 +
</command>

Latest revision as of 10:31, 7 October 2020

This article is about a function from ApCoCoA-1.

Representation of finite fields

Description

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

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).

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.

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.

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.

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 Subst 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

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