2
$\begingroup$

i need help, i'm working over the Galois Fields GF(2^m) and i will construct the field with a choosed irreducible polynomial of degree m over 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), all the solutions of the equation x^2+xy+ay^2=c over this field.. is it possible to do in GAP? and if it is, how can i do it? i know the basics of GAP..

if it is not, i'd like to solve at least the equation in one variable, i'd set y=b in GF(2^m) and solve for x the same equation..

thanks for your help..

$\endgroup$
1
$\begingroup$

There is a function, RootsOfUPol that finds the roots of a univariate polynomial. So for $y=b$ fixed you can use this to find all roots. For example ($p=7$ and the quadratic extension defined by $x^2+x-1$:

gap> x:=X(GF(7),"x");
gap> defin:=x^2+x-1;;Factors(defin);
[ x^2+x-Z(7)^0 ]
gap> RootsOfUPol(GF(49),defin);
[ Z(7^2)^3, Z(7^2)^21 ]
gap> a:=last[1]; # your generating element
Z(7^2)^3

Now pick at random $b$ and $c$ and solve:

gap> RootsOfUPol(x^2+x*b+a*b^2-c);
[ Z(7^2)^6, Z(7^2)^20 ]

There is no nice multivariate solver available (you might be able to build one yourself from Groebner basis or Resultant functionality), however for $p^m$ not too large you could solve in brute force:

gap> res:=List(Elements(GF(49)),x->[x,Filtered(Elements(GF(49)),y->x^2+x*y+a*y^2=c)]);
[ [ 0*Z(7), [  ] ], [ Z(7)^0, [  ] ], [ Z(7), [ Z(7^2)^4, Z(7^2)^33 ] ],
  [ Z(7)^2, [ 0*Z(7), Z(7^2)^37 ] ], [ Z(7)^3, [  ] ], ...

Respectively, nicer formatted

gap> Concatenation(List(res,x->List(x[2],y->[x[1],y])));
[ [ Z(7), Z(7^2)^4 ], [ Z(7), Z(7^2)^33 ], [ Z(7)^2, 0*Z(7) ],
  [ Z(7)^2, Z(7^2)^37 ], [ Z(7)^4, Z(7^2)^9 ], [ Z(7)^4, Z(7^2)^28 ],
  [ Z(7)^5, 0*Z(7) ], [ Z(7)^5, Z(7^2)^13 ], [ Z(7^2), Z(7^2)^10 ], ...
$\endgroup$
  • $\begingroup$ thanks for the help.. it works but i still have a problem.. when i take GF(8), for exemple.. it already has a definging polynomial that is x^3+x+1..but i need to construct the field F8=GF(8) having the polinomial x^3+x^2+1, i need this because i need that the generating element have trace = 1.. i tried to do this: gap> x:=X(GF(2),"x"); x gap> pol:=x^3+x^2+1; x^3+x^2+Z(2)^0 gap> F8:=AlgebraicExtension(GF(2),pol); <algebra-with-one of dimension 3 over GF(2)> then gap> Factors(pol); [ x^3+x^2+Z(2)^0 ] gap> RootsOfUPol(F8,pol); Error, no method found! For debugging hints type ... $\endgroup$ – Maycon Carneiro Dec 13 '17 at 11:56
  • $\begingroup$ @MayconCarneiro That is really a separate question and will get awkward to push into commentary discussion. If you want put it as a new question and I'll reply there. $\endgroup$ – ahulpke Dec 13 '17 at 15:20
  • $\begingroup$ hi, thanks again, so what i need is exactly what u did, but instead of taking the field GF(2^m) that GAP already has, i need to construct the field saying what irreducible polynomial GAP shoud take to construct the field.. new question has the title: how to solve a multivariete equation over a created finite field in GAP $\endgroup$ – Maycon Carneiro Dec 13 '17 at 20:22
  • $\begingroup$ @MayconCarneiro Yes. Your question is how to translate elements of $GF(p^n)$ as given by GAP to elements of this field if constructed by a different polynomial. That was the "seperate question" I referred to. $\endgroup$ – ahulpke Dec 13 '17 at 21:07

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.