Ask Your Question
1

How sage checks the irreducibility of a polynomial?

asked 2019-09-17 18:19:57 -0600

captain gravatar image

Hi, given a polynomial we can check whether its irreducibility via .is_irreducible() command. I wonder how sage checks it so fast even though the polynomial has large degree with large coefficients?

edit retag flag offensive close merge delete

Comments

Polynomial in one variable? Over which ring?

rburing gravatar imagerburing ( 2019-09-18 04:02:51 -0600 )edit

A univariate polynomial over the integers

captain gravatar imagecaptain ( 2019-09-18 06:59:54 -0600 )edit

In this case, a mixture between ntl and pari is used as i explained.

tmonteil gravatar imagetmonteil ( 2019-09-18 15:36:05 -0600 )edit

1 answer

Sort by ยป oldest newest most voted
1

answered 2019-09-18 04:02:57 -0600

tmonteil gravatar image

updated 2019-09-18 04:22:08 -0600

When such computation is fast, it depends on some optimized library (note that Sage can be seen as a bundle of optimized libraries behind a uniform Python interface), and that one depends on the type of polynomials. If you do:

sage: R.<x> = QQ[]
sage: P = R.random_element()
sage: P.is_irreducible??

You will see that flint is used.

If you do the same by replacing QQ with GF(2), you will see that the gf2x library is used but for GF(p) with p>2, the nmod_poly_is_irreducible function is used and that one relies on flint as well. If you have polynomials over ZZ, then you will see that the factor method is used, and there you will see that pari is used when the degree of the polyomial is between 30 and 300, and ntl is used otherwise, and so on.

So, you have to see the source of the corresponding upstream program to see which algorithm and optimizations they are using.

edit flag offensive delete link more

Comments

When I replace QQ with GF(p) I am getting "Object P.is_irreducible not found." error. What is the problem?

captain gravatar imagecaptain ( 2019-09-18 14:41:20 -0600 )edit

Could you please provide your exact code, it works for me:

sage: R.<x> = GF(5)[]
sage: P = R.random_element()
sage: P.is_irreducible()
False
tmonteil gravatar imagetmonteil ( 2019-09-18 15:35:24 -0600 )edit

I think I forgot to add " [] " because it works now, my bad.

captain gravatar imagecaptain ( 2019-09-19 02:20:36 -0600 )edit

ok, no pb.

tmonteil gravatar imagetmonteil ( 2019-09-25 17:29:01 -0600 )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: 2019-09-17 18:19:57 -0600

Seen: 51 times

Last updated: Sep 18