Ask Your Question
1

Finding roots of a polynomial over an extension field

asked 2016-07-07 00:22:22 -0500

anonymous user

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

1 answer

Sort by ยป oldest newest most voted
1

answered 2016-07-07 08:58:16 -0500

B r u n o gravatar image

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

edit flag offensive delete link more

Comments

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

jimbo gravatar imagejimbo ( 2016-07-07 09:06:35 -0500 )edit

Your Answer

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

Add Answer

Question Tools

1 follower

Stats

Asked: 2016-07-07 00:22:22 -0500

Seen: 79 times

Last updated: Jul 07 '16