How is "is_irreducible" function implemented in SAGE

edit

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.