FLINT3.7.0-dev
/

gr_poly_factor_finite_field, _gr_poly_factor_finite_field, gr_poly_factor_cantor_zassenhaus, gr_poly_factor_berlekamp, gr_poly_factor_kaltofen_shoup

Synopsis#include <flint/gr_poly.h>
int gr_poly_factor_finite_field(gr_ptr c, gr_poly_vec_t fac, fmpz_vec_t exp, const gr_poly_t F, gr_ctx_t ctx)source
int _gr_poly_factor_finite_field(gr_ptr c, gr_poly_vec_t fac, fmpz_vec_t exp, const gr_poly_t F, int algorithm, gr_ctx_t ctx)source
int gr_poly_factor_cantor_zassenhaus(gr_ptr c, gr_poly_vec_t fac, fmpz_vec_t exp, const gr_poly_t F, gr_ctx_t ctx)source
int gr_poly_factor_berlekamp(gr_ptr c, gr_poly_vec_t fac, fmpz_vec_t exp, const gr_poly_t F, gr_ctx_t ctx)source
int gr_poly_factor_kaltofen_shoup(gr_ptr c, gr_poly_vec_t fac, fmpz_vec_t exp, const gr_poly_t F, gr_ctx_t ctx)source

Factor F over \mathbb{F}_q as F = c \prod_i g_i^{e_i}, where c is the leading coefficient, the g_i are distinct monic irreducible polynomials (written to fac, a vector of polynomials over ctx) and the e_i \ge 1 are written to exp, in no particular order. For F = 0, c is set to zero and the factorisation is empty.

All versions start with a squarefree factorisation and then factor each squarefree part: with the Cantor-Zassenhaus algorithm (distinct-degree factorisation by \gcd(f, x^{q^i} - x) for i = 1, 2, \ldots, then equal-degree factorisation), Berlekamp's algorithm [Ber1967; Ber1970] (a basis of the kernel of the Frobenius map minus the identity by linear algebra, then random splitting), or the Kaltofen-Shoup algorithm (baby-step giant-step distinct-degree factorisation, then equal-degree factorisation). The main function first deflates inputs of the form G(x^m), m > 1, and chooses between Cantor-Zassenhaus and Kaltofen-Shoup from the degree and the size of the field. The underscore version takes algorithm, one of GR_POLY_FACTOR_ALGORITHM_DEFAULT, GR_POLY_FACTOR_ALGORITHM_CANTOR_ZASSENHAUS, GR_POLY_FACTOR_ALGORITHM_BERLEKAMP and GR_POLY_FACTOR_ALGORITHM_KALTOFEN_SHOUP.

References#

  • [Ber1967] E. R. Berlekamp. Factoring polynomials over finite fields. Bell System Technical Journal 46 (1967), 1853–1859.
  • [Ber1970] E. R. Berlekamp. Factoring polynomials over large finite fields. Mathematics of Computation 24 (1970), 713–735.
Cite this page

The FLINT team, “gr_poly_factor_finite_field, _gr_poly_factor_finite_field, gr_poly_factor_cantor_zassenhaus, gr_poly_factor_berlekamp, gr_poly_factor_kaltofen_shoup (gr_poly.h),” FLINT: Fast Library for Number Theory, documentation, version 3.7.0-dev, 2026. https://flintlib.org/doc/gr_poly/gr_poly_factor_finite_field.html (generated 2026-10-20).