fmpz_poly_factor.h

Initialise fac as the empty factorisation with $c = 1$, allocating nothing, respectively room for alloc factors.

Changes the allocated space to exactly alloc factors; for alloc = 0 the structure is cleared and reinitialised. The number of factors is not adjusted, so alloc should be at least fac->num.

Ensures that fac has room for at least len factors, growing the allocation to at least twice its old size if it has to grow.

Frees the memory used by fac.

Sets res to a copy of fac.

Multiplies the factorisation by $p^e$: if $p$ is equal to one of the stored factors, its multiplicity is increased by $e$, otherwise $p$ is appended with multiplicity $e$. The content is not changed. Meant for primitive $p$ of positive degree and $e \ne 0$, which is not checked.

Multiplies res by the factorisation fac: the contents are multiplied and the factors of fac are inserted with fmpz_poly_factor_insert. res and fac must be distinct.

Set $z$ to the constant factor $c$ of F, respectively to the factor with index $i$, which must satisfy $0 \le i <$ F->num.

Prints the content on one line, then each factor in the plain format of fmpz_poly_print followed by ^ and its multiplicity, one per line.

Sets fac to the factorisation of $G$ into its signed content and irreducible primitive factors with positive leading coefficient and their multiplicities. The zero polynomial gives content 0 and no factors, a constant $c$ gives content $c$ and no factors. fac must be initialised; its previous factors are discarded. The factors are not sorted.

Factors $G$ like fmpz_poly_factor, but without deflation and using only the Zassenhaus recombination. Its running time is exponential in the number of modular factors, so it is meant for comparison and testing. fac should be freshly initialised, since the factors are appended to those already present.

Sets the content of fac to the signed content $c$ of $F$ (with the sign of the leading coefficient) and appends squarefree, pairwise coprime, primitive factors $g_i$ of positive degree with distinct multiplicities $e_i$, so that $F = c \prod_i g_i^{e_i}$ with $\gcd(g_i, g_i') = 1$. Each $g_i$ is the product of all irreducible factors of $F$ of multiplicity $e_i$. Uses Yun's algorithm [Yun1976] (Squarefree factorisation). fac should be freshly initialised.

Appends the irreducible factors of the squarefree, primitive polynomial $f$ of length at least 2 with nonzero constant coefficient and positive leading coefficient, each with multiplicity exp, to final_fac; none of the conditions is checked.

Appends the irreducible factors of the squarefree primitive $f$, each with multiplicity exp, to final_fac, given its factorisation fac into $r \ge 2$ monic irreducible factors modulo the prime $p$, by van Hoeij's knapsack algorithm with gradual feeding of CLD data [vHo2002], [HvHN2011]. The modular factors are lifted to an initial precision, a lattice is reduced with LLL after each new column of CLD data, and the precision is doubled until a 0-1 basis of the recombination lattice is found and verified.

Insert the factorisation of the primitive quadratic (respectively cubic) polynomial $f$ into fac, with multiplicity exp, without changing the content of fac. A quadratic splits if and only if its discriminant is a square; a cubic is reducible if and only if it has a rational root, which is located from real and 2-adic approximations of the roots and tested over $\mathbb{Z}$ (Cubics). The content of $f$ must be 1, which is not checked.

Sets $B$ to a bound for the absolute values of the coefficients of all factors in $\mathbb{Z}[x]$ of $f$ of degree $m \ge 2$: the maximum of $|f(0)|$, $|\operatorname{lc}(f)|$ and of $\binom{m-1}{j} N + \binom{m-1}{j-1} |\operatorname{lc}(f)|$ for $1 \le j < m$, where $N \ge \|f\|_2$ is an integer [Coh1996, Theorem 3.5.1]. The Zassenhaus algorithm lifts to $p^a > 2 |\operatorname{lc}(f)| B$.

Given $T$ irreducible over $\mathbb{Q}$ of degree at least 1 and a prime $p$, attempts to prove that $T(x^p)$ is irreducible over $\mathbb{Q}$. Returns 1 if a proof was found and 0 if the search was inconclusive, in which case $T(x^p)$ may still be irreducible. The behaviour is undefined if $T$ is reducible. $T$ need not be primitive and may have negative leading coefficient.

Given $T$ irreducible over $\mathbb{Q}$ of degree at least 1 and $d \ge 1$, returns 1 if $T(x^d)$ is proved irreducible over $\mathbb{Q}$ and 0 if the attempt was inconclusive. The prime-step certificate is chained over the prime factorisation of $d$, using $T(x^d) = U(x^{d/p})$ with $U = T(x^p)$. The behaviour is undefined if $T$ is reducible. fmpz_poly_factor uses this to avoid refactoring inflations of irreducible factors of deflated polynomials.

Find the irreducible factors of the squarefree primitive $F$ from its monic factors lifted_fac modulo $P = p^a$, where $P > 2 |\operatorname{lc}(F)| B$ for the Mignotte bound $B$, by trying subsets of the modular factors in order of increasing size: for each subset $S$, the product $\operatorname{lc}(F) \prod_{i \in S} g_i$ is reduced into the symmetric range modulo $P$, its primitive part is tested as a divisor of $F$, and true factors are removed together with their modular factors. Each factor is appended to final_fac with multiplicity exp. The with_prune version skips subsets whose total degree is impossible according to Z.

Fills the $(r + 1) \times 2k$ matrix res with the CLD data of van Hoeij's algorithm for the $r$ lifted factors $g_i$ of $f$ modulo $P$: row $i$ holds low and high coefficients of $f g_i' / g_i$ modulo $P$ in the symmetric range, and row $r$ the corresponding bounds from fmpz_poly_CLD_bound. Of the low $k$ and high $k$ coefficients, only those whose bound times $\sqrt{\deg f}$ is small enough compared to $P$ are used; the function returns the number of columns filled, low ones first.

Checks whether the reduced lattice basis $M$ of van Hoeij's algorithm determines the factorisation: if the first $r$ columns of $M$ define a partition of the $r$ lifted factors (a 0-1 basis), the products of the factors in each part (times lc, reduced modulo $P$, made primitive) are tested as divisors of $f$, first modulo 2 and then over $\mathbb{Z}$. If all of them divide, the factors are appended to final_fac with multiplicity exp and 1 is returned; otherwise 0 is returned and final_fac is unchanged.

Sets s to the first subset of size $m$ of its $r$ entries, the first $m$ entries.

Advances s to the next subset of the same size in a fixed order and returns 1, or returns 0 if it was the last.

Removes the entries of the current subset from s, moving the remaining entries to the front, and sets it to the next subset of the same size $m$ of the remaining entries, returning 1, or returns 0 if there is none.

Initialise and free Z.

Sets the degree of the polynomial to be factored to $d \ge 1$ and marks all degrees $0, \ldots, d$ as possible.

Add the degrees of the modular factors for one prime: after zassenhaus_prune_start_add_factors, each call to zassenhaus_prune_add_factor records exp factors of degree deg, and zassenhaus_prune_end_add_factors intersects the set of possible degrees with the set of subset sums of the recorded degrees. The degrees must add up to the degree given to zassenhaus_prune_set_degree; otherwise an exception is raised.

Returns whether a factor of degree $d$ is still possible.

Returns whether no degree strictly between 0 and the degree of the polynomial is possible, which proves the polynomial irreducible.