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 = [20a^29, 51a^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.

edit retag close merge delete

Sort by ยป oldest newest most voted

The 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)!

more

Oh my goodness...thanks so much Bruno!! I racked my brain so much over this.

( 2016-07-07 09:06:35 -0600 )edit