Requesting suggestion for software to solve polynomial equation with coefficients in GF(1024)

Question

For example, the equation $x^2 + x + 1 = 0$ has the solutions $\alpha^{682}$ and $\alpha^{341}$, where $\alpha$ is a primitive element of GF(1024). I am looking for any software that can solve these equations where the polynomial also has coefficients from GF(1024). I only need to get the roots of cubic or quadratic polynomials for now.

Answer 1

Open source solution: use GAP (www.gap-system.org)

gap> F:=GF(1024);
GF(2^10)
gap> x:=Indeterminate(F,"x");
x
gap> f:=x^2+x+1;
x^2+x+Z(2)^0
gap> r:=RootsOfUPol(F,f);
[ Z(2^2), Z(2^2)^2 ]
gap> alpha := PrimitiveRoot(F);
Z(2^10)
gap> List(r, q -> LogFFE(q,alpha));
[ 341, 682 ]

Answer 2

Magma can do this. There is an online calculator for it here.

Change the address to http:// instead of https:// if your browser won't display the page.

Code:

F<a>:=ext<GF(2)|10>; R<X>:=PolynomialRing(F);
L:=[0,Random(1023),Random(1023)];L:=Sort(L);"exponents",L;
C:=[Random(F): k in [1..3]]; "coefficients",C;
f:=C[1]*X^L[1]+C[2]*X^L[2]+C[3]*X^L[3];
"find roots of f(X)",f;"list roots and their multiplicities"; Roots(f,F);

Output:

exponents [ 0, 226, 692 ]
coefficients [ a^288, a^1001, a^556 ]
find roots of f(X) a^556*X^692 + a^1001*X^226 + a^288
list roots and their multiplicities
[ <a^169, 2>, <a^301, 2> ]

Answer 3

The open-source Python package galois can do this. Disclaimer: I'm the author.

In [1]: import galois

In [2]: GF = galois.GF(2**10, display="power")

In [3]: poly = galois.Poly.Str("x^2 + x + 1", field=GF); poly
Out[3]: Poly(x^2 + x + 1, GF(2^10))

In [4]: poly.roots()
Out[4]: GF([α^341, α^682], order=2^10)