Ask Your Question
3

How is "is_irreducible" function implemented in SAGE

asked 2022-03-16 06:16:03 +0200

tungnt gravatar image

updated 2022-03-16 06:16:40 +0200

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, Tung

edit retag flag offensive close merge delete

Comments

3

To see the code:

g.is_irreducible??
FrédéricC gravatar imageFrédéricC ( 2022-03-16 08:19:04 +0200 )edit

2 Answers

Sort by » oldest newest most voted
4

answered 2022-03-16 11:28:12 +0200

rburing gravatar image

updated 2022-03-16 12:00:35 +0200

SageMath 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 types:

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 e.g. on GitHub, starting from the src/sage folder. 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 we see that it imports more stuff, in particular 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 and searching for the function we finally find its definition in 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. 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. 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 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 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 and searching for the function we find its definition in 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. Indeed, it looks like an algorithm, even with some comments. The respective documentation 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 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 we find from sage.libs.ntl.ZZ_pEX cimport *; in there 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. In the documentation 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.

edit flag offensive delete link more
0

answered 2022-03-16 15:40:04 +0200

tungnt gravatar image

updated 2022-03-16 15:40:32 +0200

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!

edit flag offensive delete link more

Comments

1

You'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.

rburing gravatar imagerburing ( 2022-03-17 15:10:04 +0200 )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: 2022-03-16 06:16:03 +0200

Seen: 79 times

Last updated: Mar 16