Revision history [back]

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 $\mathbb{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 $\mathbb{F}_q[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 $\mathbb{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!

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 $\mathbb{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 $\mathbb{F}_q[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 $\mathbb{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!