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.