Roots of polynomials over a non-prime finite field in a given extension

edit

Notice that

sage: h.change_ring(G)
a*b^3 + b^2

i.e. the polynomial variable x is sent to the generator of G, rather than to the generator of G['x'].

Unfortunately, root finding is not implemented for G:

sage: _.<y> = F[]
sage: h1 = y^4 + y^3 + (a+1)*y^2 + a
sage: h1.roots(ring=G)
---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
...

You can work around this with the newly added coercions in lattices of Conway polynomials (this is limited to small finite fields, like the ones in your example).

sage: F.<a2> = GF(4, conway=True, prefix='a')
sage: F
Finite Field in a2 of size 2^2
sage: G = GF(4^4, conway=True, prefix='a')
sage: K.<x> = G[]
sage: f = x^4 + (a2 + 1)*x^3 + a2*x^2 + a2
sage: f.roots()
[(a8^6 + a8^5 + a8^4 + 1, 1),
 (a8^6 + a8^5 + a8^4 + a8^2 + a8, 1),
 (a8^6 + a8^5 + a8^4 + a8^3 + a8, 1),
 (a8^7 + a8^5 + a8^3 + a8, 1)]
sage: b = f.roots()[0][0]
sage: h = x^4 + x^3 + (a2+1)*x^2 + a2
sage: h.roots()
[(a8^3 + a8^2 + a8, 1),
 (a8^6 + a8^4 + a8^3, 1),
 (a8^7 + a8^4 + a8^2 + a8 + 1, 1),
 (a8^7 + a8^6, 1)]

Now you can express the roots of h in terms of powers of b by linear algebra.

sage: r = h.roots()[0][0]
sage: M = matrix([vector(b^i) for i in range(8)])
sage: v = M.solve_left(vector(r)); v
(0, 0, 0, 1, 0, 0, 1, 1)
sage: v*vector([b^i for i in range(8)]) == r
True

There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.