fmpz_mpoly_factor.h

Initialise f as the empty product with constant 1, with room for alloc factors in the second version.

Change the allocation to exactly alloc factors (freeing the factors beyond it, and everything if $\mathit{alloc} \le 0$), respectively ensure room for at least len factors.

Frees the memory used by f.

Swaps f and g in constant time.

Sets f to a copy of g (the field constant_den is not copied).

Returns the number of bases of f.

Set $c$ to the constant of f. The fmpq version uses constant_den as the denominator.

Set $p$ to, respectively swap $p$ with, the base of index $i$.

Returns the exponent of the base of index $i$, which must fit an slong.

Set f to the constant $a$, 0 or 1, with no bases.

Append the factor $A^e$ to f, copying $A$, respectively swapping it in (so that $A$ is left with an unspecified value). No normalisation is done.

Sorts the factors by increasing exponent, and factors with equal exponents by fmpz_mpoly_cmp. Since the irreducible factorisation returned by fmpz_mpoly_factor has distinct bases with positive leading coefficients, two such factorisations of the same polynomial are identical after sorting.

Compares f and g by their constants, then their numbers of factors, then factor by factor (exponent, then base by fmpz_mpoly_cmp). Returns a negative, zero or positive value. This is a total order on the stored data, not a comparison of the products.

Sets $A$ to the product represented by f (ignoring constant_den). Returns 0 if an exponent is negative or a power cannot be computed, and 1 otherwise.

Returns whether f expands to $A$.

Prints f in the form c*(p1)^e1*(p2)^e2*..., using the variable names vars (or x1, x2, ... if vars is NULL).

Sets f to a factorisation of $A$ into an integer constant (the content of $A$ with the sign of its leading coefficient), powers of the variables, and polynomials with exponent 1 that are primitive with respect to each variable they involve. The latter are found by repeatedly splitting off the content with respect to one variable; they are neither squarefree nor irreducible in general. For constant $A$, f is that constant with no bases.

Sets f to a factorisation of $A$ whose bases are primitive, squarefree and pairwise coprime. A base with exponent $k$ is a product of irreducible factors of $A$ of multiplicity exactly $k$, but the factors of a given multiplicity may be spread over several bases (one for each piece found by fmpz_mpoly_factor_content). To get a single base for each multiplicity, sort with fmpz_mpoly_factor_sort and multiply the bases with equal exponents.

Sets f to the factorisation of $A$ into an integer constant and distinct irreducible polynomials with positive leading coefficients. The constant is the signed content of $A$ and is not factored into primes. See Factoring multivariate polynomials over the integers.

Versions of fmpz_mpoly_factor restricted to one method for the hard case (a squarefree primitive polynomial that is not handled by the special cases for few variables or low degree): Wang's algorithm with dense Hensel lifting, sparse Hensel lifting in Zippel's style, or lifting without leading coefficient information followed by recombination. The result is the same; these functions exist for testing and benchmarking.

Replaces each base of f by its irreducible factors, with the exponent of the base, using the methods in the bit set algo of MPOLY_FACTOR_USE_ZAS, MPOLY_FACTOR_USE_WANG and MPOLY_FACTOR_USE_ZIP (or MPOLY_FACTOR_USE_ALL). Each base must be squarefree, have positive leading coefficient and be primitive with respect to each variable it involves.

Sets $B$ to a bound on the coefficients of the divisors of a polynomial $f$ whose coefficients are bounded by $A$ in absolute value and whose degrees in its $n$ = nvars variables are $d_0, \ldots, d_{n-1}$ (degs): $B = |A| \cdot (\lfloor \sqrt{\lceil \prod_i (d_i + 1) / 2^{n} \rceil} \rfloor + 1) \cdot 2^{\sum_i d_i}$, and $B = 0$ if some $d_i < 0$. Returns 0 if the degree sum overflows and 1 otherwise. fmpz_mpolyl_gcd_zippel uses this bound to decide when to give up on a modular reconstruction and start over.

The GCD driver behind fmpz_mpoly_gcd and its variants, for nonzero $A$ and $B$: handles the easy cases, estimates degrees and term counts of the GCD, and dispatches to the algorithms allowed by the bit set algo of MPOLY_GCD_USE_* flags. Abar and Bbar may be NULL if the cofactors are not wanted. Returns 1 for success.

Convert from ctx to the context lctx, whose variable $k$ is variable perm[k] of ctx with exponents mapped by $e \mapsto (e - s)/t$ for the shift $s$ and stride $t$ of that variable, and back, packing the result into Abits bits. The results are sorted. See mpoly_to_mpolyl_perm_deflate.

Brown's dense multimodular algorithm [Bro1971] for the GCD and cofactors of nonzero $A$ and $B$. The integer contents are removed from $A$ and $B$, which are modified. Images are computed with nmod_mpolyn_gcd_brown_smprime modulo primes $p > 2^{\mathrm{FLINT\_BITS}-1}$ not dividing the GCD $\gamma$ of the leading coefficients, scaled to have leading coefficient $\gamma \bmod p$ and combined by Chinese remaindering, discarding images of too large degree. The loop stops when the product $m$ of the primes exceeds twice $\gamma$ times the larger height of $A$ and $B$ and the reconstructed $H$, $\bar A_H$, $\bar B_H$ satisfy $2 \min(\|H\|_\infty \|\bar A_H\|_1, \|H\|_1 \|\bar A_H\|_\infty) < m$ and likewise for $B$; this proves $H \bar A_H = \gamma A$ and $H \bar B_H = \gamma B$ without a division. Iv (possibly NULL) supplies degree bounds for the images. The threaded version computes images for different primes in parallel using the given thread pool handles; it is not used by fmpz_mpoly_gcd. Return 0 if the primes run out.

Zippel's sparse modular GCD [Zip1979] for $A$ and $B$ in at least two variables that are primitive as polynomials in $x_0$ over $\mathbb{Z}[x_1, \ldots, x_{n-1}]$: the GCD modulo one prime fixes the monomials (the shape), and the images modulo further primes are computed by solving for the coefficients of that shape. The coefficients are reconstructed by Chinese remaindering, and the result is verified by division. The bound of fmpz_mpoly_factor_bound_si on the inputs decides when a reconstruction is abandoned.

The sparse GCD of Hu and Monagan [HuMon2016] for $A$ and $B$ in at least three variables that are primitive as polynomials in $x_0, x_1$ over $\mathbb{Z}[x_2, \ldots, x_{n-1}]$: bivariate GCDs in $x_0, x_1$ modulo primes, with the remaining variables evaluated at powers of random points, are interpolated with the Berlekamp–Massey algorithm, and the result is verified by division. Gamma, a polynomial in $x_2, \ldots$ that is a multiple of the leading coefficient of the GCD in $x_0, x_1$ (in practice the GCD of the leading coefficients of $A$ and $B$), is imposed on the images.

The EEZ-GCD algorithm [Wan1980] for $A$ and $B$ in at least two variables that are primitive as polynomials in $x_0$, given an upper bound Gdeg on the degree in $x_0$ of the GCD: the variables $x_1, \ldots$ are evaluated at small integers, the univariate GCD is computed, and the factorisation $G \cdot \bar A$ of $A$, of $B$, or of a combination $\mu_1 A + \mu_2 B$ in which the two factors are coprime, is lifted with fmpz_mpoly_hlift.

Set $A_p = A \bmod p$, and $A$ to the lift of $A_p$ with coefficients in the symmetric range $(-p/2, p/2]$. Both contexts have the same variables and the polynomials are packed with the same number of bits.

Replaces $H$, known modulo $m$, by the polynomial with coefficients in the symmetric range modulo $mp$ that is congruent to $H$ modulo $m$ and to $A$ modulo $p$. $H$ and $A$ must have the same monomials. Returns whether $H$ changed, and sets *coeffbits to the largest bit length of its new coefficients.

The same operations with the image in recursive form $\mathbb{F}_p[x_0, \ldots, x_{n-2}][x_{n-1}]$ (an nmod_mpolyn_t, whose coefficients are univariate in the last variable), as used by Brown's algorithm. The CRT version updates $F$ so that it is unchanged modulo modulus and congruent to $A$ modulo $p$, without assuming that the monomials match; it uses $T$ as scratch space, returns whether $F$ changed, and does not update modulus.

Initialise an empty vector, free it, swap two vectors in constant time, and ensure room for length entries.

Prints the entries, one per line, as coeff[i]: ....

Sets entry $i$ to the nonzero polynomial $c$ by swapping (so $c$ is left with an unspecified value), extending the vector with zero entries if needed.

The first writes $B = \sum_i A_i \cdot \mathit{xalpha}^i$ by repeated division with remainder by xalpha; for $\mathit{xalpha} = x_j - \alpha$ the $A_i$ are the Taylor coefficients of $B$ at $x_j = \alpha$. The second evaluates such an expansion by Horner's rule and packs the result into Abits bits.

Sets $g$ to the GCD of the Alen polynomials in $A$, with positive leading coefficient, starting with the two shortest ones. Returns 0 if a GCD computation failed.

Divide each polynomial of $A$ exactly by $c$, respectively multiply each by $c$.

Negates the nonzero polynomial $A$ if its leading coefficient is negative.

Initialise and free.

Prepares Iv for the $r \ge 2$ nonconstant denominators $b_i \in \mathbb{Z}[x]$: computes the products $b_{i+1} \cdots b_{r-1}$, the resultants that bound the size of solutions, a prime $p$ for which the $b_i$ stay coprime modulo $p$, and the corresponding inverses. Returns 0 if $r < 2$, some $b_i$ is constant, or two of them are not coprime.

Solves $A / \prod_i b_i = \sum_i c_i / b_i$ for $c_i \in \mathbb{Z}[x]$ with $\deg c_i < \deg b_i$ for $i < r - 1$. The solution is computed modulo a power $p^k$ of the prime and checked by exact division; on failure the precision is raised until a Cramer–Hadamard bound on the solution shows that no integer solution exists. Returns 1 if a solution exists and 0 otherwise, so a return value of 0 is a proof.

Prepare for the $r$ denominators betas in the variables $x_0, \ldots, x_w$ and the evaluation point $(\alpha_0, \ldots, \alpha_{w-1})$ for $x_1, \ldots, x_w$, in a lex context with bits bits. The univariate images in $x_0$ must keep their degrees and be pairwise coprime; if not, the initialisation throws an error. Free the data.

Solves $t = \sum_i \delta_i \prod_{j \ne i} \beta_j^{(l)}$ in the variables $x_0, \ldots, x_l$ with $\deg_{x_0} \delta_i < \deg_{x_0} \beta_i$ and $\deg_{x_k} \delta_i$ at most what the bound degs[k] allows, storing the solution in Iv->deltas + l*r. For $l = 0$ this is a univariate problem; for $l > 0$ the Taylor coefficients of $t$ in $x_l - \alpha_{l-1}$ are processed in turn, each by a call at level $l - 1$. $t$ is destroyed. Returns 1 if a solution exists, 0 if no solution satisfies the degree bounds, and $-1$ if $t$ cannot be repacked to the working bits.

Lifts the $r \ge 2$ factors $f_i$ of $A \equiv \prod_i f_i \bmod (x_m - \alpha_{m-1})$, in a lex context with single-word exponents, to factors in the variables $x_0, \ldots, x_m$. The leading coefficients of the $f_i$ in $x_0$ must already be the correct ones (polynomials in all of $x_1, \ldots, x_m$), and degs are the degrees of $A$. The lifting runs up to degree degs[m] in $x_m - \alpha_{m-1}$; it uses the error update of the quartic method, specialised for $r = 2$, when $r < 20$, and recomputes the product of the factors (quintic method) otherwise. Returns 0 if a partial fraction problem has no solution or the degrees exceed degs[m], in which case there is no factorisation of $A$ with these images and leading coefficients. Only the quintic version checks at the end that $A = \prod_i f_i$; the callers verify the factors by division in any case. See The lifting step.

In a lex context, set $c$ to the leading coefficient of $A$ as a polynomial in $x_0$ (a polynomial in the other variables), and set $A$ to $B$ with that leading coefficient replaced by $c$.

Memory management: initialise as zero, free, swap in constant time, ensure room for at least len coefficients in $x$ (realloc never shrinks), and set to zero.

Return a pointer to the leading coefficient in $x$, the degree in $x$, and the degree in $y$ (both $-1$ for zero).

Sets the coefficient of $x^{\mathit{exp0}} y^{\mathit{exp1}}$ to the nonzero integer $c$.

Prints $A$ as a sum of terms (c(y))*x^i, with the given names for $x$ and $y$.

Convert between a multivariate polynomial in the variables of index var0 (for $x$) and var1 (for $y$) and a dense bivariate polynomial. The first requires single-word exponents and ignores the exponents of the other variables; the second packs the result into Abits bits.

Set res to the resultant of $A$ and $B$ with respect to $x$, a polynomial in $y$, by reduction modulo word-size primes, resultants of the images and Chinese remaindering. If proved is nonzero, enough primes are used for their product to exceed twice a Hadamard-type bound on the coefficients of the resultant, which makes the result exact; otherwise the reconstruction stops once it has been left unchanged by primes whose product exceeds $2^{100}$, which is a heuristic. Return 0 if no image could be computed. The underscore version works in place on the coefficient arrays, whose contents it removes, and requires $\mathit{lenA} \ge \mathit{lenB} \ge 2$. This is the dense case of fmpz_mpoly_resultant and the modular resultant of the generic polynomial module; see Bivariate resultants by evaluation and interpolation.

Initialise an empty vector, free it, swap in constant time, and ensure room for len entries.

Factors the squarefree bivariate polynomial $B$ of positive degree in $x$: sets $c$ to its content as a polynomial in $x$ over $\mathbb{Z}[y]$ and $F$ to the irreducible factors of the primitive part. The point $\alpha$ is the first of $0, 1, -1, 2, -2, \ldots$ for which $B(x, \alpha)$ keeps its degree and is squarefree; $B(x, \alpha)$ is factored with fmpz_poly_factor, the factors are lifted in $(\mathbb{Z}/p^k\mathbb{Z})[[y - \alpha]][x]$ to a precision given by a bound on the factors, and recombined by trying subsets. $B$ is destroyed. If $B$ is not squarefree, the search for $\alpha$ does not terminate.

As fmpz_bpoly_factor, with the point $\alpha$ and the squarefree factorisation Bevalf of $B(x, \alpha)$ given (with at least two factors). On success there is one factor in $F$ for each factor of Bevalf, in the same order. Returns 1 on success, 0 if the lifted factors do not correspond one to one with the factors of Bevalf, and $-1$ if $B$ is not primitive (with its content in $c$). Used by Kaltofen's leading coefficient method.

Appends a squarefree factorisation of $A^e$ to f, where $A$ is primitive with respect to each variable. Constant and monomial $A$ are handled directly; otherwise Yun's algorithm [Yun1976] is run with respect to the first variable in which $A$ has a nonzero derivative. $A$ is destroyed. Returns 0 if a GCD failed for every variable.

Set fac to the irreducible factors of $A$, which must be squarefree, primitive with respect to each variable and have positive leading coefficient, in a lex context with at least two variables. lcA is the leading coefficient of $A$ in $x_0$ and lcAfac a squarefree factorisation of it, irreducible if lcAfac_irred is nonzero. Z collects the degrees of the factors of univariate images and can prove irreducibility early.

The Wang version evaluates $x_1, \ldots$ at $0$ and, if allow_shift is nonzero, then at random points of growing size, distributes the leading coefficient with fmpz_mpoly_factor_lcc_wang or fmpz_mpoly_factor_lcc_kaltofen, and lifts the factors one variable at a time with fmpz_mpoly_hlift. The Zippel version lifts modulo a prime with sparse Hensel lifting and then $p$-adically. The Zassenhaus version lifts without leading coefficient information and recombines subsets of the lifted factors. Return 1 on success, 0 if the method failed (another method or point may succeed), and $-1$ on an exceptional failure such as exponents that no longer fit one word.

Wang's leading coefficient determination [Wan1978]. Given the irreducible factorisation lcAfac of the leading coefficient of $A$ in $x_0$ and the factorisation $\mathit{Auc} \prod_{i < r} \mathit{Auf}_i$ of $A(x_0, \alpha)$, sets lc_divs[i] to the predicted leading coefficient of the $i$-th factor of $A$: the product of the powers of the factors of the leading coefficient whose values at $\alpha$ divide the leading coefficient of $\mathit{Auf}_i$, times an integer. Returns 0 if the evaluation point fails Wang's condition, that each factor of the leading coefficient evaluates to an integer with a prime divisor not dividing $\mathit{Auc}$ times the constant and the values of the other factors.

Kaltofen's leading coefficient determination [Kal1985]. For each variable $x_v$, $v \ge 1$, the bivariate image of $A$ in $x_0, x_v$ (all other variables evaluated at $\alpha$) is factored with fmpz_bpoly_factor_ordered in the order of the univariate factors uf, and the leading coefficients of its factors show how the squarefree factors lcAf_ of the leading coefficient of $A$ involving $x_v$ are distributed; these are multiplied into divs. Returns 1 if the whole leading coefficient has been distributed, 0 if only part of it was, and $-1$ if the evaluation point is unusable.

One step of fmpz_mpoly_factor_lcc_kaltofen for the variable $x_v$: given the squarefree factorisation Af of the remaining part of the leading coefficient and the univariate leading coefficients Au[i] in $x_v$ of the bivariate factors, lifts the matching factors of the image of Af to all variables, multiplies them into divs[i] and removes them from Af. Returns 1 on success and 0 if the images do not match.

Sets $e$ to $A$ with $x_i = \alpha_{i-1}$ for every $i \ge 1$ other than $v$, as a polynomial in $x_v$. Returns 0 if an evaluation failed or the result involves $x_0$.

The first sets $E = A(x_0, \alpha_0, \ldots, \alpha_{n-2})$ for $A$ in a lex context with single-word exponents. The second is its kernel: for a block of Alen terms of a lex polynomial whose exponents agree in the variables before var, it evaluates the variables from var on at alphas (indexed from var) by a recursive Horner scheme and puts the value in E[0]; starts, ends, stops, es and the further entries of $E$ are work arrays of length nvars, and offsets and shifts locate the exponent fields.

Apply the change of variables found by mpoly_compression_set. The first builds $L$ in the compressed lex context Lctx from the coefficients Acoeffs, which are swapped in, and the compressed exponents stored in M, then sorts it and makes its leading coefficient positive. The second maps $L$ (typically a factor of the compressed polynomial, whose coefficients are swapped out) back to Actx with Abits bits, divides by the largest monomial dividing it, sorts, and makes the leading coefficient positive.

Helpers for enumerating evaluation points in $\mathbb{N}^n$: print a tuple, step to the next tuple (all tuples with a given sum are visited before the sum increases), and move the entries after index $m$ into entry $m$ (making it 1 if the first $m + 1$ entries would all be zero) so that one of the first $m + 1$ entries changes at the next step.