CoCoA:HowTo:Construct fields

This article is a stub. You can make this wiki more useful by adding information.

about

To construct finite field extensions, you adjungate an indeterminate and compute modulo an irreducible polynomial, e.g. $\mathbb {R} [i]/(i^{2}+1)$. In this HowTo I will present some lines of code to find irreducible polynomials and their roots. These roots are helpful to create the field's endomorphism group or to switch between different representations of the same field.

This HowTo assumes we are working with finite field extensions of $\mathbb {F} _{2}=\mathbb {Z} /(2)$, so the code has to be adapted for other characteristics.

finding irreducible polynomials

First, we need a small function, giving us all polynomials having a degree smaller than a given bound. If Deg contains this bound the code

 Define Buildall(Deg)
   If Deg=0 Then
     Return [0,1];
   EndIf;
 
   L := Buildall(Deg - 1);
   Return Concat([x*E | E In L], [x*E + 1 | E In L])
 EndDefine;

dheldt 12:30, 22 May 2007 (CEST)

accomplishes this task. Now, we use this function to create all polynomials of a given degree and check if they are irreduceable. This can be done with

  Use Z/(2)[x];
 
  Deg := 4;  -- change for the degree you want. 
 
  L := [x^(Deg) + E | E In Buildall(Deg-1)]; -- take all polynomials of smaller degrees and add x^Deg. 
 
  Result := [];
 
  -- find all irred. polynomials.
  ForEach E In L Do
    H := Factor(E);
    If Len(H) = 1 Then
  	If H[1][2] = 1 Then
  		Append(Result, E);
  	EndIf;	
    EndIf;
  EndForEach;

dheldt 12:30, 22 May 2007 (CEST)

Now result is a list of all irreducible polynomials of degree Deg.

finding the roots

To find the roots for all polynomials in result, the following code is avaiable:

 All :=  Buildall(Deg-1);
 AllL := [];
 Foreach F In Result Do
     L := [];
     Foreach E In All Do
 		If (NF(Subst(F,[ [x,E] ]),Ideal([F])) = 0) Then
 			Append(L,E);
 		EndIf;
     EndForeach;
     Append( AllL, [F,L]);
 EndForeach;

dheldt 12:30, 22 May 2007 (CEST)

Then AllL contains pairs, each containing one of the irreducible polynomials and all of their roots in the corresponding field extension.

creating multiplication matrices

The files F_2048_multiplication.C and Building_finite_fields.coc were built to create semi-logarithmic multiplication and division matrices for ApCoCoA's finite fields with characteristic 2. There is not much documentation in the files, but they may give an idea. In case you have any questions / problems, feel free to contact me! dheldt 14:25, 3 November 2007 (CET)