Loading [MathJax]/jax/output/HTML-CSS/jax.js
Ask Your Question

Revision history [back]

click to hide/show revision 1
initial version

answered 3 years ago

tungnt gravatar image

Thank you very much for your detailed answer.

Let me provide a more precise description of the problem that I am working on. I have a polynomial f over Z and I want to see whether it is irreducible. My original method is to study the factorization of f modulo a prime q and then use this factorization to see whether f is irreducible or not. As I mentioned earlier, this method is quite slow. For example, it took hours to return the result for f of degree around 500.

Note that I need to verify other properties of f so taking modulo various primes q is a must. However, for irreducibility, I realized that I can just use the built-in function is_irreducible(). And since I already used mod q, I continued to change the ring to GF(q) and use this function is_irreducible over Fq[x]. It is faster than the method that I used before. Following the suggestion from rburing, I checked that the function the reduction mod q has the type ='sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>. So, using rburing's answer, we can trace back and learn that this method uses the FLINT library. Specifically, it uses

Uses fast distinct-degree factorisation.

I realize that I can even test for irreducibility over Z directly. This method is much faster than the previous two methods. For example, it only took 4 minutes (wall time) to return the result for polynomials of degree around 1500. I copied the method of rburing and learned that the type in this case is

<class 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>

The documentation about the irreducibility test says the following

  • If the base ring implements _is_irreducible_univariate_polynomial, then this method gets used instead of the generic algorithm which just factors the input.

Unfortunately, reading through the codes, I cannot decide which method it uses in my case (generic algorithm or is_irreducible_univariate_polynomial). I would appreciate your expertise on this matter.

Thank you again for your wonderful help!

click to hide/show revision 2
No.2 Revision

Thank you very much for your detailed answer.

Let me provide a more precise description of the problem that I am working on. I have a polynomial f over Z and I want to see whether it is irreducible. My original method is to study the factorization of f modulo a prime q and then use this factorization to see whether f is irreducible or not. As I mentioned earlier, this method is quite slow. For example, it took hours to return the result for f of degree around 500.

Note that I need to verify other properties of f so taking modulo various primes q is a must. However, for irreducibility, I realized that I can just use the built-in function is_irreducible(). And since I already used mod q, I continued to change the ring to GF(q) and use this function is_irreducible over Fq[x]. It is faster than the method that I used before. Following the suggestion from rburing, I checked that the function the reduction mod q has the type ='sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>. So, using rburing's answer, we can trace back and learn that this method uses the FLINT library. Specifically, it uses

Uses fast distinct-degree factorisation.

I realize that I can even test for irreducibility over Z directly. This method is much faster than the previous two methods. For example, it only took 4 minutes (wall time) to return the result for polynomials of degree around 1500. I copied the method of rburing and learned that the type in this case is

<class 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'>

The documentation about the irreducibility test says the following

  • If the base ring implements _is_irreducible_univariate_polynomial, then this method gets used instead of the generic algorithm which just factors the input.

Unfortunately, reading through the codes, I cannot decide which method it uses in my case (generic algorithm or is_irreducible_univariate_polynomial). I would appreciate your expertise on this matter.

Thank you again for your wonderful help!

help!