ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Fri, 08 Nov 2013 05:34:36 -0600Roots of polynomials over a non-prime finite field in a given extensionhttp://ask.sagemath.org/question/10711/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?Wed, 06 Nov 2013 11:48:49 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/Comment by tmonteil for <p>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:</p>
<p>First, I define my non-prime finite field (GF(4)), and
a primitive polynomial f.</p>
<pre><code>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
</code></pre>
<p>Now, I define an extension field G where f has its roots</p>
<pre><code> 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
</code></pre>
<p>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.</p>
<pre><code> sage: h=x^4 + x^3 + (a + 1)*x^2 + a
sage: h.is_primitive()
True
</code></pre>
<p>But when I try to find the roots of h in G, I get nothing.</p>
<pre><code> sage: h.roots(ring=G)
[]
</code></pre>
<p>Could somebody tell me how I could get the roots of h in G
with respect to b?</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16772#post-id-16772Are you sure h has some roots in G ?Wed, 06 Nov 2013 12:51:06 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16772#post-id-16772Comment by geo909 for <p>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:</p>
<p>First, I define my non-prime finite field (GF(4)), and
a primitive polynomial f.</p>
<pre><code>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
</code></pre>
<p>Now, I define an extension field G where f has its roots</p>
<pre><code> 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
</code></pre>
<p>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.</p>
<pre><code> sage: h=x^4 + x^3 + (a + 1)*x^2 + a
sage: h.is_primitive()
True
</code></pre>
<p>But when I try to find the roots of h in G, I get nothing.</p>
<pre><code> sage: h.roots(ring=G)
[]
</code></pre>
<p>Could somebody tell me how I could get the roots of h in G
with respect to b?</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16770#post-id-16770@tmonteil Yes, it's of degree 4 over F4, so it has a root in F_{4^4} from finite field theoryWed, 06 Nov 2013 13:40:36 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16770#post-id-16770Answer by Luca for <p>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:</p>
<p>First, I define my non-prime finite field (GF(4)), and
a primitive polynomial f.</p>
<pre><code>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
</code></pre>
<p>Now, I define an extension field G where f has its roots</p>
<pre><code> 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
</code></pre>
<p>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.</p>
<pre><code> sage: h=x^4 + x^3 + (a + 1)*x^2 + a
sage: h.is_primitive()
True
</code></pre>
<p>But when I try to find the roots of h in G, I get nothing.</p>
<pre><code> sage: h.roots(ring=G)
[]
</code></pre>
<p>Could somebody tell me how I could get the roots of h in G
with respect to b?</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?answer=15671#post-id-15671Notice 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.Wed, 06 Nov 2013 13:06:21 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?answer=15671#post-id-15671Comment by Luca for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16755#post-id-16755`a8` is the way the generator of `GF(2^8)` is printed out: a because of `prefix='a'`, and 8 because it's the extention of degree 8 (the splitting field of your polynomial).Fri, 08 Nov 2013 05:34:36 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16755#post-id-16755Comment by Luca for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16763#post-id-16763Oops! 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?Thu, 07 Nov 2013 01:31:52 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16763#post-id-16763Comment by geo909 for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16760#post-id-16760@Luca I see where the a2 came from, but I still don't understand where the a8 comes from.. Also, I still get an error message:
F. \< a2 \> = GF(4, conway=True, prefix='a')
Traceback (click to the left of this block for traceback)
...
TypeError: __init__() got an unexpected keyword argument 'prefix'
Is that what @ppruka's tickets refer to? I'm a bit of a new user and I can't understand 100% what the tickets imply for my case..
EDIT: have no idea how to make the first line appear correct.. It's F.<a2>
Thu, 07 Nov 2013 08:40:22 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16760#post-id-16760Comment by Luca for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16771#post-id-16771Had 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.Wed, 06 Nov 2013 13:20:43 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16771#post-id-16771Comment by ppurka for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16765#post-id-16765@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.Wed, 06 Nov 2013 23:04:17 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16765#post-id-16765Comment by geo909 for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16768#post-id-16768@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.Wed, 06 Nov 2013 13:54:37 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16768#post-id-16768Comment by Luca for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16756#post-id-16756Yes, you get an error because, as @ppurka said, your version of sage is too old. This functionality will appear in Sage 5.13, which is not out yet (it will before the end of 2013, I guess). If you are a daredevil, and use Linux on a 64 bit machine, you can try the development version here http://boxen.math.washington.edu/home/release/sage-5.13.beta3/sage-5.13.beta3-boxen-x86_64-Linux.tar.gzFri, 08 Nov 2013 05:28:22 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16756#post-id-16756Comment by geo909 for <p>Notice that</p>
<pre><code>sage: h.change_ring(G)
a*b^3 + b^2
</code></pre>
<p>i.e. the polynomial variable <code>x</code> is sent to the generator of <code>G</code>, rather than to the generator of <code>G['x']</code>.</p>
<p>Unfortunately, root finding is not implemented for G:</p>
<pre><code>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)
...
</code></pre>
<p>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).</p>
<pre><code>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)]
</code></pre>
<p>Now you can express the roots of <code>h</code> in terms of powers of <code>b</code> by linear algebra.</p>
<pre><code>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
</code></pre>
<p>There is some development happening on finite field extensions, so hopefully this will be easier in a couple of releases from now.</p>
http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16769#post-id-16769@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?
Wed, 06 Nov 2013 13:53:57 -0600http://ask.sagemath.org/question/10711/roots-of-polynomials-over-a-non-prime-finite-field-in-a-given-extension/?comment=16769#post-id-16769