How to solve a quadratic equation over finite fields with GAP..

Question

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

Answer 1

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 ], ...