fmpz_poly_factor_init fac

Initialises a new factor structure.

fmpz_poly_factor_init2 fac alloc

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

fmpz_poly_factor_realloc fac alloc

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

fmpz_poly_factor_fit_length fac 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.

fmpz_poly_factor_clear fac

Releases all memory occupied by the factor structure.

fmpz_poly_factor_set res fac

Sets res to the same factorisation as fac.

fmpz_poly_factor_insert fac p e

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

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

fmpz_poly_factor_concat res 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.

fmpz_poly_factor_print fac

Prints the entries of fac to standard output.

fmpz_poly_factor_squarefree fac 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\).

fmpz_poly_factor_zassenhaus_recombination final_fac lifted_fac F P 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.

_fmpz_poly_factor_zassenhaus final_fac exp f cutoff 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.

fmpz_poly_factor_zassenhaus final_fac 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\).

_fmpz_poly_factor_quadratic fac f 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 factorzation is calculated over \(\mathbb{R}\) or \(\mathbb{Q}_2\) and then tested over \(\mathbb{Z}\).

fmpz_poly_factor final_fac 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.