Ask Your Question

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

asked 2013-11-06 18:48:49 +0200

geo909 gravatar image

updated 2023-01-10 02:12:53 +0200

tmonteil gravatar image

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()

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()

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 flag offensive close merge delete


Are you sure h has some roots in G ?

tmonteil gravatar imagetmonteil ( 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

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

2 Answers

Sort by ยป oldest newest most voted

answered 2013-11-06 20:06:21 +0200

Luca gravatar image

updated 2013-11-07 08:34:01 +0200

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

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

edit flag offensive delete link 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.

Luca gravatar imageLuca ( 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?

geo909 gravatar imagegeo909 ( 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.

geo909 gravatar imagegeo909 ( 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.

ppurka gravatar imageppurka ( 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?

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

answered 2023-01-10 02:10:50 +0200

tmonteil gravatar image

updated 2023-01-10 02:12:41 +0200

This is now fixed:

sage: h.roots(ring=G)
[(a*b^2 + (a + 1)*b + a + 1, 1),
 (b^3 + b^2 + b + a, 1),
 (a*b^3 + a*b^2 + (a + 1)*b + 1, 1),
 ((a + 1)*b^3 + b^2 + b + 1, 1)]

Setting tags from confirmed_issue to fixed_issue.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools


Asked: 2013-11-06 18:48:49 +0200

Seen: 2,044 times

Last updated: Jan 10