Finding the roots of a polynomial mod a composite number in Python

I am looking for a way to solve 3rd and 4th degree polynomials from Python (actually Python 3) using Sage. The polynomials are not square-free and the modulo can be a composite number. How do I do that? Help would be appreciated.

answered 0 years ago

Max Alekseyev

6902 ●9 ●52 ●161

Like this:

mymod = 21
x = polygen(Zmod(mymod))
f = x^4 + x^2 + 1
print( f.roots(multiplicities=False) )

link

Comments

Hey, awesome. I can't believe you answered so quickly. Thanks. One more question. What if I know the factorization, e.g. 7*3, can I pass it in to speed up the calculation? I guess it can be just precomputed once.

The Big Lebowski ( 0 years ago )

I believe it will be factored once if you create a single Zmod (and x) object and reuse it in all polynomials.

Max Alekseyev ( 0 years ago )

add a comment

Your Answer

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

Finding the roots of a polynomial mod a composite number in Python

1 Answer

Comments

Your Answer

Question Tools

Stats

Finding the roots of a polynomial mod a composite number in Python savecancel

1 Answer

Comments

Your Answer

Question Tools

Stats

Finding the roots of a polynomial mod a composite number in Python