![]() | 1 | initial version |
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
_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!
![]() | 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
_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!