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

I am trying to find the roots of a primitive polynomial over a non-prime finite field, in a desired extension. Here is an example of what I'm trying to do:

First, I define my non-prime finite field (GF(4)), and a primitive polynomial f.

sage: F.<a>=GF(4)
sage: K.<x>=F[]
sage: F
Finite Field in a of size 2^2
sage: K
Univariate Polynomial Ring in x over Finite Field in a of size 2^2
sage: f=x^4 + (a + 1)*x^3 + a*x^2 + a
sage: f.is_primitive()
True


Now, I define an extension field G where f has its roots

 sage: G=f.root_field('b')
sage: G
Univariate Quotient Polynomial Ring in b over Finite Field in a of size 2^2 with modulus x^4 + (a + 1)*x^3 + a*x^2 + a


I assume that b is a root of f, by definition (correct me if I'm wrong). Now, I take a new primitive polynomial h.

 sage: h=x^4 + x^3 + (a + 1)*x^2 + a
sage: h.is_primitive()
True


But when I try to find the roots of h in G, I get nothing.

 sage: h.roots(ring=G)
[]


Could somebody tell me how I could get the roots of h in G with respect to b?

edit retag close merge delete

Are you sure h has some roots in G ?

( 2013-11-06 19:51:06 +0200 )edit

@tmonteil Yes, it's of degree 4 over F4, so it has a root in F_{4^4} from finite field theory

( 2013-11-06 20:40:36 +0200 )edit

Sort by » oldest newest most voted

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.

more

Had to spend some time scratching my head, but, on second thought, I don't think it is a bug. Obviously, the splitting field should be a finite field rather than a quotient polynomial ring, and it would be nice to fix this (it's not so easy, though). But, given the current implementation and Sage's conventions about polynomial quotient rings, it makes sense that any polynomial over F coerces to an element of G, rather than an element of its polynomial ring.

( 2013-11-06 20:20:43 +0200 )edit

@Luca Thank you very much for the quick reply. Though there are a couple of things that I do not get. For one, you use prefix='a' for both F and G? And what is the a8 that appears in the roots of f and h?

( 2013-11-06 20:53:57 +0200 )edit

@Luca Actually.. It doesn't work for me (Sage version 5.5): F = GF(4, conway=True, prefix='a') Traceback (click to the left of this block for traceback) ... TypeError: you must specify the generator name.

( 2013-11-06 20:54:37 +0200 )edit

@geo909 Like Luca mentioned, this is a very new addition. It will appear in sage-5.13. The relevant tickets are ticket 8335 and ticket 13214.

( 2013-11-07 06:04:17 +0200 )edit

Oops! I thought it had entered 5.12 already. prefix is a replacement for name, specific to Conway lattices. By the way, my code was buggy, I have fixed it. Is it clearer now?

( 2013-11-07 08:31:52 +0200 )edit