# fmpz_poly_factor.h – factorisation of polynomials over the integers

## Types, macros and constants

type fmpz_poly_factor_struct

type fmpz_poly_factor_t

## Memory management

void fmpz_poly_factor_init(fmpz_poly_factor_t fac)

  Initialises a new factor structure.

void fmpz_poly_factor_init2(fmpz_poly_factor_t fac, slong alloc)

  Initialises a new factor structure, providing space for at least `alloc` factors.

void fmpz_poly_factor_realloc(fmpz_poly_factor_t fac, slong alloc)

  Reallocates the factor structure to provide space for precisely `alloc` factors.

void fmpz_poly_factor_fit_length(fmpz_poly_factor_t fac, slong len)

  Ensures that the factor structure has space for at least `len` factors. This functions takes care of the case of repeated calls by always at least doubling the number of factors the structure can hold.

void fmpz_poly_factor_clear(fmpz_poly_factor_t fac)

  Releases all memory occupied by the factor structure.

## Manipulating factors

void fmpz_poly_factor_set(fmpz_poly_factor_t res, const fmpz_poly_factor_t fac)

  Sets `res` to the same factorisation as `fac`.

void fmpz_poly_factor_insert(fmpz_poly_factor_t fac, const fmpz_poly_t p, slong e)

  Adds the primitive polynomial \(p^e\) to the factorisation `fac`.

  Assumes that \(\deg(p) \geq 2\) and \(e \neq 0\).

void fmpz_poly_factor_concat(fmpz_poly_factor_t res, const fmpz_poly_factor_t fac)

  Concatenates two factorisations.

  This is equivalent to calling `fmpz_poly_factor_insert()` repeatedly with the individual factors of `fac`.

  Does not support aliasing between `res` and `fac`.

## Input and output

void fmpz_poly_factor_print(const fmpz_poly_factor_t fac)

  Prints the entries of `fac` to standard output.

## Factoring algorithms

void fmpz_poly_factor_squarefree(fmpz_poly_factor_t fac, const fmpz_poly_t F)

  Takes as input a polynomial \(F\) and a freshly initialized factor structure `fac`. Updates `fac` to contain a factorization of \(F\) into (not necessarily irreducible) factors that themselves have no repeated factors. None of the returned factors will have the same exponent. That is we return \(g_i\) and unique \(e_i\) such that

  \[F = c \prod_{i} g_i^{e_i}\]

  where \(c\) is the signed content of \(F\) and \(\gcd(g_i, g_i') = 1\).

void fmpz_poly_factor_zassenhaus_recombination(fmpz_poly_factor_t final_fac, const fmpz_poly_factor_t lifted_fac, const fmpz_poly_t F, const fmpz_t P, slong exp)

  Takes as input a factor structure `lifted_fac` containing a squarefree factorization of the polynomial \(F \bmod p\). The algorithm does a brute force search for irreducible factors of \(F\) over the integers, and each factor is raised to the power `exp`.

  The impact of the algorithm is to augment a factorization of `F^exp` to the factor structure `final_fac`.

void _fmpz_poly_factor_zassenhaus(fmpz_poly_factor_t final_fac, slong exp, const fmpz_poly_t f, slong cutoff, int use_van_hoeij)

  This is the internal wrapper of Zassenhaus.

  It will attempt to find a small prime such that \(f\) modulo \(p\) has a minimal number of factors. If it cannot find a prime giving less than `cutoff` factors it aborts. Then it decides a \(p\)-adic precision to lift the factors to, Hensel lifts, and finally calls Zassenhaus recombination.

  Assumes that \(\operatorname{len}(f) \geq 2\).

  Assumes that \(f\) is primitive.

  Assumes that the constant coefficient of \(f\) is non-zero. Note that this can be easily achieved by taking out factors of the form \(x^k\) before calling this routine.

  If the final flag is set, the function will use the van Hoeij factorisation algorithm with gradual feeding and mod \(2^k\) data truncation to find factors when the number of local factors is large.

void fmpz_poly_factor_zassenhaus(fmpz_poly_factor_t final_fac, const fmpz_poly_t F)

  A wrapper of the Zassenhaus factoring algorithm, which takes as input any polynomial \(F\), and stores a factorization in `final_fac`.

  The complexity will be exponential in the number of local factors we find for the components of a squarefree factorization of \(F\).

void _fmpz_poly_factor_quadratic(fmpz_poly_factor_t fac, const fmpz_poly_t f, slong exp)
void _fmpz_poly_factor_cubic(fmpz_poly_factor_t fac, const fmpz_poly_t f, slong exp)

  Inserts the factorisation of the quadratic (resp. cubic) polynomial f into fac with multiplicity exp. This function requires that the content of f has been removed, and does not update the content of fac. The factorization is calculated over \(\mathbb{R}\) or \(\mathbb{Q}_2\) and then tested over \(\mathbb{Z}\).

void fmpz_poly_factor(fmpz_poly_factor_t final_fac, const fmpz_poly_t F)

  A wrapper of the Zassenhaus and van Hoeij factoring algorithms, which takes as input any polynomial \(F\), and stores a factorization in `final_fac`.