Factorisation

These functions factor a polynomial A \in \mathbb{F}_p[x_1, \ldots, x_m], p prime, as

where c \in \mathbb{F}_p is the leading coefficient of A and the bases f_i are monic. nmod_mpoly_factor_content only separates the monomial content and the contents with respect to each variable; nmod_mpoly_factor_squarefree returns squarefree, pairwise coprime bases; nmod_mpoly_factor returns the irreducible factorisation, in which the bases are irreducible and pairwise distinct. The order of the factors is not specified; nmod_mpoly_factor_sort sorts them by exponent and then by nmod_mpoly_cmp, which makes the output canonical. The zero polynomial gives c = 0 and no factors, a nonzero constant gives c = A and no factors.

All functions return 1 for success. They return 0 only in extreme cases (exponents of more than one word after removing the content, or no usable evaluation points or extension fields), and f is then undefined.

Characteristic p#

Two features of characteristic p appear in the output. First, a polynomial with zero derivative in every variable is a p-th power: over \mathbb{F}_p, \sum_e c_e x^{pe} = (\sum_e c_e x^e)^p. The squarefree decomposition therefore extracts p-th roots by dividing exponents, and multiplicities divisible by p come out naturally; in the example below, (x^3 + yz + 1)^3 = x^9 + y^3z^3 + 1 over \mathbb{F}_3. Second, factoring needs evaluation points at which the polynomial keeps its degree and stays squarefree. When \mathbb{F}_p does not have enough of them, the polynomial is factored over an extension \mathbb{F}_{p^k} and the conjugate factors under the Frobenius automorphism are multiplied back together. Both are invisible to the caller.

nmod_mpoly_factor_separable with sep = 1 refines the squarefree decomposition so that each base g satisfies, for each variable, \partial g/\partial x_i = 0 or \gcd(g, \partial g/\partial x_i) = 1. This is the input format of the irreducible factorisation.

The variants nmod_mpoly_factor_zassenhaus, nmod_mpoly_factor_wang and nmod_mpoly_factor_zippel restrict the method used to lift factorisations of bivariate images to all variables (recombination of lifted factors, Wang's leading coefficient method with dense Hensel lifting, or sparse Hensel lifting); nmod_mpoly_factor_algo takes a bit mask of these methods. nmod_mpoly_factor uses all of them, choosing the order from the density of the polynomial; see Choosing among the methods.

Example#

Over \mathbb{F}_3, the squarefree decomposition of a polynomial with a cube factor, and its irreducible factorisation; then a factorisation over \mathbb{F}_2, where x^4 + y^4 = (x + y)^4:

#include <flint/flint.h>
#include <flint/nmod_mpoly.h>
#include <flint/nmod_mpoly_factor.h>

static void print_factor(const char * name, nmod_mpoly_factor_t f,
                         const char ** vars, const nmod_mpoly_ctx_t ctx)
{
    slong i;
    flint_printf("%s: %wu", name, nmod_mpoly_factor_get_constant_ui(f, ctx));
    for (i = 0; i < nmod_mpoly_factor_length(f, ctx); i++)
    {
        flint_printf(" * (");
        nmod_mpoly_print_pretty(f->poly + i, vars, ctx);
        flint_printf(")^%wd", nmod_mpoly_factor_get_exp_si(f, i, ctx));
    }
    flint_printf("\n");
}

int main(void)
{
    nmod_mpoly_ctx_t ctx;
    nmod_mpoly_t a;
    nmod_mpoly_factor_t f;
    const char * vars[] = {"x", "y", "z"};

    nmod_mpoly_ctx_init(ctx, 3, ORD_LEX, 3);
    nmod_mpoly_init(a, ctx);
    nmod_mpoly_factor_init(f, ctx);

    nmod_mpoly_set_str_pretty(a, "2*y^2*(x^3 + y*z + 1)^3*(x^2 + y^2 + z^2)*(x^2 - y^2 + z)", vars, ctx);
    flint_printf("a has %wd terms\n", nmod_mpoly_length(a, ctx));

    nmod_mpoly_factor_squarefree(f, a, ctx);
    nmod_mpoly_factor_sort(f, ctx);
    print_factor("squarefree", f, vars, ctx);

    nmod_mpoly_factor(f, a, ctx);
    nmod_mpoly_factor_sort(f, ctx);
    print_factor("irreducible", f, vars, ctx);

    /* over F_2: x^4 + y^4 = (x + y)^4, and a factorisation needing extensions */
    nmod_mpoly_ctx_set_modulus(ctx, 2);
    nmod_mpoly_set_str_pretty(a, "(x^2*y + x*z^2 + y*z + 1)*(x^3 + y^2*z + x*z + z + 1)*(x^4 + y^4)", vars, ctx);
    nmod_mpoly_factor(f, a, ctx);
    nmod_mpoly_factor_sort(f, ctx);
    print_factor("over F_2", f, vars, ctx);

    nmod_mpoly_factor_clear(f, ctx);
    nmod_mpoly_clear(a, ctx);
    nmod_mpoly_ctx_clear(ctx);
    return 0;
}

a has 21 terms
squarefree: 2 * (x^4+x^2*z^2+x^2*z+2*y^4+2*y^2*z^2+y^2*z+z^3)^1 * (y)^2 * (x^3+y*z+1)^3
irreducible: 2 * (x^2+2*y^2+z)^1 * (x^2+y^2+z^2)^1 * (y)^2 * (x^3+y*z+1)^3
over F_2: 1 * (x^2*y+x*z^2+y*z+1)^1 * (x^3+x*z+y^2*z+z+1)^1 * (x+y)^4

The squarefree decomposition keeps the two factors of multiplicity 1 together as one base; the irreducible factorisation separates them. The program switches to \mathbb{F}_2 with nmod_mpoly_ctx_set_modulus, which is allowed because both a and f are completely overwritten before they are used again. nmod_mpoly_factor_get_exp_si takes a non-const factorisation.