1 | initial version |

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 `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 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`

.

I encourage others to post answers about the other implementations.

2 | No.2 Revision |

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 `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 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.

I encourage others to post answers about the other implementations.

3 | No.3 Revision |

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 `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 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.

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.