3
$\begingroup$

I need help, I'm working over the Galois Fields $\mathrm{GF}(2^m)$ and I will construct the field with a chosen irreducible polynomial of degree $m$ over $\mathrm{GF}(2)$. I can do it on GAP. Now comes my problem. I'll take $a$ to be a root of this polynomial and I need to find, for a fixed $c$ in $GF(2^m)$, an expression for $c$ in terms of the field $F[a]$ that I constructed. Is it possible to do it in GAP? And if it is, how can I do it? I know the basics of GAP.

(This is a follow-up to my question How to solve a quadratic equation over finite fields with GAP.. in which I asked for solutions to polynomial equations. I however need to say GAP what irreducible polynomial to take to construct the field.)

$\endgroup$
2
$\begingroup$

Basically you want to change coefficient between two bases. Your field has the basis $1,a,a^2,...$, GAP's field uses another basis, namely its own primitive element $b$. For example, for $p=2$ and polynomial $x^2+x-1$ and some (here randomly chosen) $c\in GF(7^2)$:

gap> p:=7;;x:=X(GF(p),"x");; pol:=x^2+x-1;;
gap> c:=Random(GF(7^2));
Z(7^2)^4

First calculate a basis for the field. We can for example calculate coefficients wrt this basis:

gap> b:=Basis(GF(p^2));
CanonicalBasis( GF(7^2) )
gap> BasisVectors(b);
[ Z(7)^0, Z(7^2) ]
gap> Coefficients(b,c);
[ Z(7)^3, Z(7)^2 ]
gap> List(last, Int);
[ 6, 2 ]

To get the base change, lets calculate $a$ and get coefficient vectors for $1,a,...$:

gap> a:=RootsOfUPol(GF(7^2),pol)[1]; # doesn't matter which root we take.
Z(7^2)^3
gap> abas:=[a^0,a];
[ Z(7)^0, Z(7^2)^3 ]
gap> mat:=List(abas,x->Coefficients(b,x));
[ [ Z(7)^0, 0*Z(7) ], [ Z(7)^4, Z(7)^5 ] ]
gap> Display(mat);
 1 .
 4 5

To express elements in terms of the $a$-basis we need the inverse matrix:

gap> inv:=mat^-1;Display(inv);
[ [ Z(7)^0, 0*Z(7) ], [ Z(7)^2, Z(7) ] ]
 1 .
 2 3

Now we use this inverse to convert the coeffiicients of $c$ wrt. GAP's basis to the $a$-basis. (Multiplication from the right, as GAP uses row vectors.)

gap> Coefficients(b,c)*inv;
[ Z(7), Z(7)^3 ]
gap> List(last,Int);
[ 3, 6 ]
gap> 3+6*a;
Z(7^2)^4

(The last 4 lines verify the calculation. Indeed $c=3+6*a$.)

If you wanted to display finite field elements prettily in your basis, the following hack function (using polynomials over the integers) would do so:

gap> avar:=X(Rationals,"a");
a

gap> abasrep:=function(x)
  return UnivariatePolynomial(Rationals,List(Coefficients(b,x)*inv,Int),avar);
end;

gap> List(Elements(GF(49)),x->abasrep(x));
[ 0, 1, 3, 2, 6, 4, 5, 3*a+2, 3*a+6, a, 6*a+3, 3*a+3, 6*a+1, 4*a+6, 2*a+6,
  2*a+4, 3*a, 4*a+2, 2*a+2, 4*a+3, 5*a+4, 6*a+4, 6*a+5, 2*a, 5*a+6, 6*a+6,
  5*a+2, a+5, 4*a+5, 4*a+1, 6*a, a+4, 4*a+4, a+6, 3*a+1, 5*a+1, 5*a+3, 4*a,
  3*a+5, 5*a+5, 3*a+4, 2*a+3, a+3, a+2, 5*a, 2*a+1, a+1, 2*a+5, 6*a+2 ]

and as the exaple shows you could even apply this function to lists of numbers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.