Ask Your Question

# Finding roots of a polynomial over an extension field

Anonymous

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

## 1 Answer

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

## Comments

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

( 2016-07-07 16:06:35 +0200 )edit

## Your Answer

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

Add Answer

## Stats

Asked: 2016-07-07 07:22:22 +0200

Seen: 750 times

Last updated: Jul 07 '16