Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

This is a bug in my opinion. 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, as in your example).

sage: F = 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 + a
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.

This is a bug in my opinion. 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, as like the ones in your example).

sage: F F.<a2> = GF(4, conway=True, prefix='a')
sage: F
Finite Field in a2 of size 2^2
sage: G G.<a8> = GF(4^4, conway=True, prefix='a')
sage: K.<x> = G[]
sage: f = x^4 + (a2 + 1)*x^3 + a2*x^2 + a
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.

click to hide/show revision 3
made code mor thought provoking

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