ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 17 Mar 2022 15:10:04 +0100How is "is_irreducible" function implemented in SAGEhttps://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/Dear community,
Suppose I have a polynomial $g$ over a finite field $\mathbb{F}_q[x]$. Then we can check whether $g$ is irreducible by using the following command
> g.is_irreducible()
I did not know about this method until recently. Previously, I just factorized g and counted the number of factors. If this number is 1, then g is irreducible. I compared the running time of my method and the above built-in method. I learned that the latter method is much faster (which makes sense). That leads me to wonder whether which method is used to implement is_irreducible. For example, some search on the internet suggests that Rabin's algorithm is a popular one. Is it true that Rabin's algorithm is implemented on Sage? For the record, I am using the paid version of Cocalc.
Thank you for your consideration!
Best wishes, TungWed, 16 Mar 2022 06:16:03 +0100https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/Comment by FrédéricC for <p>Dear community, </p>
<p>Suppose I have a polynomial $g$ over a finite field $\mathbb{F}_q[x]$. Then we can check whether $g$ is irreducible by using the following command </p>
<blockquote>
<p>g.is_irreducible()</p>
</blockquote>
<p>I did not know about this method until recently. Previously, I just factorized g and counted the number of factors. If this number is 1, then g is irreducible. I compared the running time of my method and the above built-in method. I learned that the latter method is much faster (which makes sense). That leads me to wonder whether which method is used to implement is_irreducible. For example, some search on the internet suggests that Rabin's algorithm is a popular one. Is it true that Rabin's algorithm is implemented on Sage? For the record, I am using the paid version of Cocalc. </p>
<p>Thank you for your consideration!</p>
<p>Best wishes, Tung</p>
https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?comment=61524#post-id-61524To see the code:
g.is_irreducible??Wed, 16 Mar 2022 08:19:04 +0100https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?comment=61524#post-id-61524Answer by tungnt for <p>Dear community, </p>
<p>Suppose I have a polynomial $g$ over a finite field $\mathbb{F}_q[x]$. Then we can check whether $g$ is irreducible by using the following command </p>
<blockquote>
<p>g.is_irreducible()</p>
</blockquote>
<p>I did not know about this method until recently. Previously, I just factorized g and counted the number of factors. If this number is 1, then g is irreducible. I compared the running time of my method and the above built-in method. I learned that the latter method is much faster (which makes sense). That leads me to wonder whether which method is used to implement is_irreducible. For example, some search on the internet suggests that Rabin's algorithm is a popular one. Is it true that Rabin's algorithm is implemented on Sage? For the record, I am using the paid version of Cocalc. </p>
<p>Thank you for your consideration!</p>
<p>Best wishes, Tung</p>
https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?answer=61529#post-id-61529Thank 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!Wed, 16 Mar 2022 15:40:04 +0100https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?answer=61529#post-id-61529Comment by rburing for <p>Thank you very much for your detailed answer. </p>
<p>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$. </p>
<p>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 =<code>'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'></code>. So, using rburing's answer, we can trace back and learn that this method uses the FLINT library. Specifically, it uses </p>
<pre><code>Uses fast distinct-degree factorisation.
</code></pre>
<p>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 </p>
<p><code><class 'sage.rings.polynomial.polynomial_integer_dense_flint.Polynomial_integer_dense_flint'></code></p>
<p>The documentation about the irreducibility test says the following </p>
<ul>
<li>If the base ring implements
<code>_is_irreducible_univariate_polynomial</code>,
then this method gets used instead of
the generic algorithm which just
factors the input.</li>
</ul>
<p>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. </p>
<p>Thank you again for your wonderful help!</p>
https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?comment=61541#post-id-61541You're welcome! Generally I would advise to post a follow-up question as a separate question (linking to the previous question). For factorization over $\mathbb{Z}$ the generic algorithm is used (because `ZZ` does not have a method `_is_irreducible_univariate_polynomial`), so the input is just factored. From `g.factor??` you can see that factorization uses NTL or PARI, depending on the degree. For more details, please post a separate question.Thu, 17 Mar 2022 15:10:04 +0100https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?comment=61541#post-id-61541Answer by rburing for <p>Dear community, </p>
<p>Suppose I have a polynomial $g$ over a finite field $\mathbb{F}_q[x]$. Then we can check whether $g$ is irreducible by using the following command </p>
<blockquote>
<p>g.is_irreducible()</p>
</blockquote>
<p>I did not know about this method until recently. Previously, I just factorized g and counted the number of factors. If this number is 1, then g is irreducible. I compared the running time of my method and the above built-in method. I learned that the latter method is much faster (which makes sense). That leads me to wonder whether which method is used to implement is_irreducible. For example, some search on the internet suggests that Rabin's algorithm is a popular one. Is it true that Rabin's algorithm is implemented on Sage? For the record, I am using the paid version of Cocalc. </p>
<p>Thank you for your consideration!</p>
<p>Best wishes, Tung</p>
https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?answer=61525#post-id-61525SageMath contains multiple implementations of finite fields and polynomial rings over them, even if this is not always clear from the interface. So the answer to the question depends on which implementation is used.
For finite fields there are the specialized classes `PolynomialRing_dense_mod_p` (with implementations `'FLINT'`, `'NTL'`, and `'GF2X'`) and `PolynomialRing_dense_finite_field` (with implementations `'NTL'` and `'generic'`), and there is the generic class `PolynomialRing_field` (with a sparse and dense implementation).
You can find out which one you are dealing with (if you didn't specify one explicitly) by checking the `type`s:
sage: R.<x> = PolynomialRing(GF(2))
sage: g = R.random_element()
sage: type(R)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_p_with_category'>
sage: type(g)
<class 'sage.rings.polynomial.polynomial_gf2x.Polynomial_GF2X'>
So here we have a `PolynomialRing_dense_mod_p` with the `'GF2X'` implementation. We can check how `is_irreducible` is implemented by looking at its source code as follows:
sage: g.is_irreducible??
We see that the function is defined in `sage/rings/polynomial/polynomial_gf2x.pyx`, and that it calls `GF2X_IterIrredTest`. To find out where `GF2X_IterIrredTest` comes from we have to look at the file. We can find [the file](https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/polynomial_gf2x.pyx) e.g. [on GitHub, starting from the `src/sage` folder](https://github.com/sagemath/sage/tree/develop/src/sage). We see `GF2X_IterIrredTest` is only mentioned once, so the name must be imported somehow. Looking at the top of the file, we see `include "sage/libs/ntl/decl.pxi"`. Chasing down [this file](https://github.com/sagemath/sage/blob/develop/src/sage/libs/ntl/decl.pxi) we see that it imports more stuff, in particular [GF2X.pxd](https://github.com/sagemath/sage/blob/develop/src/sage/libs/ntl/GF2X.pxd). In here we find the line
long GF2X_IterIrredTest "IterIrredTest" (GF2X_c f)
which means that `GF2X_IterIrredTest` refers to the C function `IterIrredTest` defined somewhere in the NTL library. After [finding the NTL source code](https://github.com/libntl/ntl) and [searching for the function](https://github.com/libntl/ntl/search?q=IterIrredTest) we finally find its definition in [GF2XFactoring.cpp](https://github.com/libntl/ntl/blob/main/src/GF2XFactoring.cpp). Indeed it looks like an algorithm, not sure which one (there are 0 comments). Fortunately the same repository contains documentation; we want [doc/GF2XFactoring.txt](https://github.com/libntl/ntl/blob/main/doc/GF2XFactoring.txt). It reads:
long IterIrredTest(const GF2X& f);
// performs an iterative deterministic irreducibility test, based on
// DDF. Fast on average (when f has a small factor).
By doing a web search we find that DDF stands for [distinct-degree factorization](https://en.wikipedia.org/wiki/Factorization_of_polynomials_over_finite_fields#Distinct-degree_factorization). With this information and some more effort, one could decipher the C code of `IterIrredTest`.
---
Another example:
sage: R.<x> = PolynomialRing(GF(3))
sage: g = R.random_element()
sage: type(R)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_mod_p_with_category'>
sage: type(g)
<class 'sage.rings.polynomial.polynomial_zmod_flint.Polynomial_zmod_flint'>
So we have a `PolynomialRing_dense_mod_p` with the `'FLINT'` implementation. Checking `g.is_irreducible??` we find that it is defined in the file [sage/rings/polynomial/polynomial_zmod_flint.pyx](https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/polynomial_zmod_flint.pyx) and that it calls `nmod_poly_is_irreducible`. Checking the file we find the import statement `from sage.libs.flint.nmod_poly cimport *` which looks promising. Checking [sage/libs/flint/nmod_poly.pxd](https://github.com/sagemath/sage/blob/develop/src/sage/libs/flint/nmod_poly.pxd) we find the line
cdef int nmod_poly_is_irreducible(nmod_poly_t f)
which means that it refers to a C function defined in the FLINT library. Looking up the [FLINT source code](https://github.com/wbhart/flint2/) and [searching for the function](https://github.com/wbhart/flint2/search?q=nmod_poly_is_irreducible) we find its definition in [nmod_poly_factor/is_irreducible.c](https://github.com/wbhart/flint2/blob/trunk/nmod_poly_factor/is_irreducible.c), where it calls `nmod_poly_is_irreducible_ddf`. Searching for that one, we find its definition in [nmod_poly_factor/is_irreducible_ddf.c](https://github.com/wbhart/flint2/blob/trunk/nmod_poly_factor/is_irreducible_ddf.c). Indeed, it looks like an algorithm, even with some comments. The respective [documentation](https://github.com/wbhart/flint2/blob/trunk/doc/source/nmod_poly_factor.rst) states:
Uses fast distinct-degree factorisation.
So again one can try to understand the C code with this hint.
---
Another example:
sage: R.<x> = PolynomialRing(GF(3^2))
sage: g = R.random_element()
sage: type(R)
<class 'sage.rings.polynomial.polynomial_ring.PolynomialRing_dense_finite_field_with_category'>
sage: type(g)
<class 'sage.rings.polynomial.polynomial_zz_pex.Polynomial_ZZ_pEX'>
This is a `PolynomialRing_dense_finite_field` with the `'NTL'` implementation. Checking `g.is_irreducible??` we find that it is defined in the file [sage/rings/polynomial/polynomial_zz_pex.pyx](https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/polynomial_zz_pex.pyx) and that it calls `ZZ_pEX_IterIrredTest` by default (though it offers other options). We see the import statement `include "sage/libs/ntl/ntl_ZZ_pEX_linkage.pxi"` and in [the respective file](https://github.com/sagemath/sage/blob/develop/src/sage/libs/ntl/ntl_ZZ_pEX_linkage.pxi) we find `from sage.libs.ntl.ZZ_pEX cimport *`; [in there](https://github.com/sagemath/sage/blob/develop/src/sage/libs/ntl/ZZ_pEX.pxd) we find
long ZZ_pEX_IterIrredTest "IterIrredTest"(ZZ_pEX_c x)
so it refers to the C function `IterIrredTest` (note: now with a differently typed argument!) in the NTL library. After a search we find its definition in [src/ZZ_pEXFactoring.cpp](https://github.com/libntl/ntl/blob/fa1a36168a4d054b823b33b869863133b0ca54e6/src/ZZ_pEXFactoring.cpp#L832). In the [documentation](https://github.com/libntl/ntl/blob/main/doc/ZZ_pEXFactoring.txt) we find:
// performs an iterative deterministic irreducibility test, based on
// DDF. Fast on average (when f has a small factor).
So it is similar to the first example.
---
I encourage others to post answers about the other implementations.Wed, 16 Mar 2022 11:28:12 +0100https://ask.sagemath.org/question/61523/how-is-is_irreducible-function-implemented-in-sage/?answer=61525#post-id-61525