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.Thu, 07 Jul 2016 09:06:35 -0500Finding roots of a polynomial over an extension fieldhttp://ask.sagemath.org/question/34042/finding-roots-of-a-polynomial-over-an-extension-field/ Apologies if I am not articulating this very well. I am still in an early learning phase.
I am trying to find the roots of a polynomial s^37 + 7 over a finite field of size 241 and modulus x^32 + 44.
My code is as follows:
`K.<x> = GF(241)[]`
`T.<a> = K.quotient(x^32 + 44)`
`J.<s> = T[]`
`G = s^32 + 7`
`G.roots()`
and here I get : 'root finding with multiplicities for this polynomial not implemented (try the multiplicities=False option)'
I think I expressed this correctly as some sanity-checking with known roots is correctly evaluated as follows:
rootList = [20*a^29, 51*a^13, 221*a^13]
for r in rootList:
assert(G(r) == 0)
It does not appear root finding is implemented for G.
Is there some alternative way to find the roots of G?
Thank you.
Thu, 07 Jul 2016 00:22:22 -0500http://ask.sagemath.org/question/34042/finding-roots-of-a-polynomial-over-an-extension-field/Answer by B r u n o for <p>Apologies if I am not articulating this very well. I am still in an early learning phase.</p>
<p>I am trying to find the roots of a polynomial s^37 + 7 over a finite field of size 241 and modulus x^32 + 44.</p>
<p>My code is as follows:</p>
<p><code>K.<x> = GF(241)[]</code></p>
<p><code>T.<a> = K.quotient(x^32 + 44)</code></p>
<p><code>J.<s> = T[]</code></p>
<p><code>G = s^32 + 7</code></p>
<p><code>G.roots()</code></p>
<p>and here I get : 'root finding with multiplicities for this polynomial not implemented (try the multiplicities=False option)'</p>
<p>I think I expressed this correctly as some sanity-checking with known roots is correctly evaluated as follows:</p>
<p>rootList = [20<em>a^29, 51</em>a^13, 221*a^13]</p>
<p>for r in rootList:
assert(G(r) == 0)</p>
<p>It does not appear root finding is implemented for G.</p>
<p>Is there some alternative way to find the roots of G?</p>
<p>Thank you.</p>
http://ask.sagemath.org/question/34042/finding-roots-of-a-polynomial-over-an-extension-field/?answer=34044#post-id-34044The solution is to explicitly declare `T` as a finite field with `241^32` elements:
sage: K.<x> = GF(241)[]
sage: T.<a> = GF(241^32, modulus=x^32+44)
sage: J.<s> = T[]
sage: G = s^32 + 7
sage: G.roots()
[(221*a^13, 1),
(190*a^13, 1),
...
(51*a^29, 1),
(20*a^29, 1)]
I would be great if Sage were able to detect that your construction is equivalent to mine, but it is unfortunately not the case (yet)!
Thu, 07 Jul 2016 08:58:16 -0500http://ask.sagemath.org/question/34042/finding-roots-of-a-polynomial-over-an-extension-field/?answer=34044#post-id-34044Comment by jimbo for <p>The solution is to explicitly declare <code>T</code> as a finite field with <code>241^32</code> elements:</p>
<pre><code>sage: K.<x> = GF(241)[]
sage: T.<a> = GF(241^32, modulus=x^32+44)
sage: J.<s> = T[]
sage: G = s^32 + 7
sage: G.roots()
[(221*a^13, 1),
(190*a^13, 1),
...
(51*a^29, 1),
(20*a^29, 1)]
</code></pre>
<p>I would be great if Sage were able to detect that your construction is equivalent to mine, but it is unfortunately not the case (yet)!</p>
http://ask.sagemath.org/question/34042/finding-roots-of-a-polynomial-over-an-extension-field/?comment=34045#post-id-34045Oh my goodness...thanks so much Bruno!! I racked my brain so much over this.Thu, 07 Jul 2016 09:06:35 -0500http://ask.sagemath.org/question/34042/finding-roots-of-a-polynomial-over-an-extension-field/?comment=34045#post-id-34045