nmod_mpoly_factor.h

Initialise f as the empty product with constant 1; nmod_mpoly_factor_init2 also allocates space for alloc factors.

Frees the memory used by f.

Change the allocation of f to alloc factors (truncating the product if it is longer), or ensure space for at least len factors.

Swap f and g efficiently, and set f to a copy of g.

Sets f to the empty product with constant 1.

Return the number k of factors and the constant c of f.

Set p to the base f_i of index i, or swap p with it, where 0 \le i < k.

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

Append the factor A^e to f, copying A.

nmod_mpoly_factor_expand sets A to the product c \prod_i f_i^{e_i} and returns 1, or returns 0 if an exponent is negative or a power is too large to compute. nmod_mpoly_factor_matches returns whether f expands to a.

Sorts the factors of f by increasing exponent, and factors with equal exponents by nmod_mpoly_cmp.

Compares two factorisations, first by constant, then by number of factors, then factor by factor (exponent, then base by nmod_mpoly_cmp). Returns -1, 0 or 1. Factorisations of the same polynomial compare equal after nmod_mpoly_factor_sort.

Prints f as the constant followed by one line *(base)^exp per factor, with the variable names vars.

Sets f to a factorisation of A whose bases are variables and polynomials that are primitive with respect to every variable, that is, have no factor independent of some variable that they involve. This is the first step of the other functions.

Sets f to a factorisation of A whose bases are squarefree and pairwise coprime. Bases with equal exponents are not multiplied together; to get the product of all irreducible factors of a given multiplicity, sort with nmod_mpoly_factor_sort and multiply the bases with that exponent.

With sep = 0 this is nmod_mpoly_factor_squarefree. With sep = 1, each base g in addition satisfies, for every variable x_i, either \partial g/\partial x_i = 0 or \gcd(g, \partial g/\partial x_i) = 1, with \partial g/\partial x_i \ne 0 for at least one i; this is the form required by the irreducible factorisation.

Sets f to the factorisation of A into irreducible factors over \mathbb{F}_p: the bases are monic, irreducible and pairwise distinct.

As nmod_mpoly_factor, but lifting the bivariate factorisation with only one method: Zassenhaus-style recombination after lifting a univariate factorisation, Wang's leading coefficient method with dense Hensel lifting, or sparse Hensel lifting. nmod_mpoly_factor_algo takes a bit mask algo of MPOLY_FACTOR_USE_ZAS, MPOLY_FACTOR_USE_WANG, MPOLY_FACTOR_USE_ZIP (or MPOLY_FACTOR_USE_ALL). Polynomials in one or two variables are always factored by the univariate and bivariate algorithms.

Convert between B, a polynomial in the variables of indices var0 and var1 only, and the dense bivariate n_bpoly_t A in which var0 is the main (outer) variable; nmod_mpoly_set_bpoly produces exponents of Abits bits.

Convert between a polynomial in the variables varx and vary and an n_polyun_t with exponents in varx and n_poly_t coefficients in vary.

_nmod_mpoly_get_lead0 sets c to the leading coefficient of A viewed as a polynomial in variable 0 (a polynomial in the other variables). _nmod_mpoly_set_lead0 sets A to B with that leading coefficient replaced by c.

Memory management of vectors; nmod_mpolyv_set_coeff swaps c into position i, extending the vector with zeros.

Convert between B and the vector of its coefficients in the expansion B = \sum_i A_i\, \mathit{xalpha}^i in powers of xalpha, which is of the form x_j - \alpha; the coefficients do not involve x_j. nmod_mpoly_from_mpolyv produces exponents of Abits bits.

The GCD of the Alen polynomials A (returning 1 for success), and exact division or multiplication of all of them by c.

Operations on vectors of univariate polynomials: maximum degree, multiplication by an invertible scalar or by g, exact division by g, the monic GCD g of the entries, and division by it.

Apply the compression M (computed by mpoly_compression_set, see mpoly.h) to the terms Acoeffs of length Alen, giving L in the context Lctx with fewer variables, and undo it, giving A with Abits exponent bits. A compression is an invertible monomial change of variables that removes unused variables and redundancy in the exponents.

Check an nmod_mpolyu_t, and print one whose exponents pack three main variables with the names var0, var1, var2.

Factors the bivariate polynomial B in x (main variable) and y, which must be separable in x: sets c to its content with respect to x and F to its irreducible factors. Evaluates y = \alpha for \alpha \in \mathbb{F}_p (only \alpha = 0 if allow_shift is zero), factors the univariate image, lifts the factors y-adically by Hensel lifting and recombines them with the linear algebra on logarithmic derivatives of Lecerf [Lec2006] (Bivariate factorisation). Returns 0 if no suitable \alpha exists in \mathbb{F}_p. B is destroyed.

As n_bpoly_mod_factor_smprime, but reduces y modulo irreducible polynomials m(y) of increasing degree, factors the image over \mathbb{F}_p[y]/(m) \cong \mathbb{F}_{p^d}, lifts m-adically and recombines. Always succeeds.

Helpers of the recombination: nmod_mat_is_reduced returns whether every column of N contains exactly one nonzero entry, equal to 1, so that the rows describe a partition of the local factors. nmod_mat_init_nullspace_tr initialises X to a matrix whose rows are a basis of the right nullspace of tmp (which is destroyed).

Hensel lifting of a factorisation of a bivariate (or, for n_polyu3_mod_hlift, trivariate) polynomial A modulo y - \alpha to a factorisation modulo (y - \alpha)^{d} with d = degree_inner + 1, for two factors B0, B1 or r factors B; the cubic versions evaluate and interpolate in the other variable. n_bpoly_mod_pfrac solves the corresponding partial fraction equation. They return 1 for success and 0 if the lifted factors do not multiply to A.

nmod_mpoly_pfrac_init prepares Iv for the r factors betas in l + 1 variables with the evaluation points alpha, and returns 0 if the factors are not pairwise coprime at the evaluation points. nmod_mpoly_pfrac solves the equation for the right-hand side t in the first r + 1 variables with degree bounds deg, returning 1 for success.

Given factors f[0], ..., f[r-1] with A = \prod_i f_i modulo x_m - \alpha_{m-1} and degree bounds degs, lift them to a factorisation of A in the variables x_0, \ldots, x_m: by dense Hensel lifting, or by sparse interpolation of the lifted coefficients. Return 1 for success.

Wang's leading coefficient distribution [Wan1978] along a curve: given the factorisation lcAfac of the leading coefficient of A, and the content Auc \in \mathbb{F}_p[Y] and the r factors Auf of the bivariate image of A under the substitution of the polynomials alpha[i] \in \mathbb{F}_p[Y] for the variables other than the main one, sets lc_divs to the true leading coefficients of the factors (up to constants) (Leading coefficients over a finite field). Returns 1 for success and 0 if the curve is unlucky.

Set fac (or Af) to the irreducible factors of the monic squarefree A in lexicographic order with at least three variables, given for the Wang and Zippel methods the factorisation lcAfac of the leading coefficient lcA in variable 0. The smprime versions use evaluation points in \mathbb{F}_p; the medprime versions map A to \mathbb{F}_{p^k} represented by fq_zech (with p^k \le 10^6), factor there and combine Frobenius-conjugate factors; the lgprime versions do the same with fq_nmod and no bound on k. Return 1 for success, 0 if they ran out of evaluation points or extension degrees, and -1 for a failure that other evaluation points would not fix (for example exponents that do not fit one word).

As nmod_mpoly_factor_separable for a monic A whose content has been removed.

Evaluate all variables after the first one or two at given points (or at given univariate polynomials), giving univariate or bivariate images; and set A from a bivariate polynomial in variable 0 and var.

Zippel's GCD algorithm in a lexicographic context, as used by the factoring code: gcdp interpolates the variables up to var with points in \mathbb{F}_p, gcds solves for the coefficients of the assumed monomial structure G (marked by Gmarks).

Evaluate the monomials of a polynomial at powers of the evaluation points cached in alpha_caches, keeping zero, one or two main variables symbolic; used to set up the Vandermonde systems of sparse interpolation.

Sparse interpolation of the coefficients of a polynomial with known monomial structure H: start collecting req_images images in Z, add the image A (returning 0 if its support does not match), and solve the transposed Vandermonde systems, returning 1 for success and 0 or -1 if the images are inconsistent with the assumed structure.