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

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

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; # 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,y->[x,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 ], ...

• 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 ... – Maycon Carneiro Dec 13 '17 at 11:56
• @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. – ahulpke Dec 13 '17 at 15:20
• 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 – Maycon Carneiro Dec 13 '17 at 20:22
• @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. – ahulpke Dec 13 '17 at 21:07