Factoring polynomials over a prime field

nmod_poly_factor computes the complete factorisation

of a polynomial $f \in \mathbb{F}_p[x]$ into distinct monic irreducible polynomials $f_i$ with multiplicities $e_i \ge 1$: the factors and exponents are stored in an nmod_poly_factor_t, and the leading coefficient $c$ is the return value. The modulus $p$ must be prime. The _with_ variants force one algorithm and are otherwise identical; the three void functions append to an existing factorisation instead of overwriting it and discard $c$, which is convenient when factoring the parts of a product one by one.

Algorithms#

All functions are wrappers of the generic implementation in gr_poly over the nmod context, which proceeds in four steps:

1. Deflation. If $f(x) = g(x^m)$ with $m \ge 2$, $g$ is factored first, and then each $g_j(x^m)$ separately.
2. Squarefree factorisation, by Yun-type gcd iterations and $p$-th roots (Squarefree factorisation), which costs a few gcds.
3. Distinct-degree factorisation of each squarefree part, which separates the irreducible factors by degree.
4. Equal-degree factorisation, a randomised splitting of each product of irreducible factors of the same degree.

The algorithms differ in steps 3 and 4. The Cantor–Zassenhaus algorithm finds the factors of degree $d$ as $\gcd(g, x^{p^d} - x)$ for $d = 1, 2, \ldots$, computing each $x^{p^d} \bmod g$ by an exponentiation by $p$; its cost is about $\tfrac{n}{2} \cdot \tfrac{3}{2} \log_2 p$ multiplications modulo $g$ for an irreducible $g$ of degree $n$, so it suits small $p$ and small degrees. The Kaltofen–Shoup algorithm replaces the exponentiations by modular compositions in a baby-step giant-step scheme, about $\sqrt{2n}$ compositions and $n/2$ multiplications modulo $g$, independent of $p$. Berlekamp's algorithm computes the kernel of an $n \times n$ matrix over $\mathbb{F}_p$ instead; at $O(n^3)$ (or $O(n^\omega)$) it is slower for large $n$, and is mainly useful for checking the others.

nmod_poly_factor chooses Cantor–Zassenhaus when the degree $n$ of the (deflated) input satisfies $n < 125 / (\log_2 p)^{1.3}$ and Kaltofen–Shoup otherwise:

For large inputs the work is dominated by the distinct-degree factorisation, which uses several threads when they are available (flint_set_num_threads); see The complete algorithms and FLINT's choice.

The factors are returned in no particular order: grouped by squarefree part, and within a part in the order in which the distinct-degree and equal-degree steps find them. The random choices use a random state with a fixed seed, so repeated calls give the same output.

Examples#

A product of known factors modulo 7, one of them with multiplicity $7 = p$, is recovered together with its leading coefficient. The squarefree factorisation alone separates the multiplicities:

#include <flint/flint.h>
#include <flint/nmod_poly.h>
#include <flint/nmod_poly_factor.h>

int main(void)
{
    nmod_poly_t f, g;
    nmod_poly_factor_t fac;
    ulong c;

    nmod_poly_init(f, 7);
    nmod_poly_init(g, 7);
    nmod_poly_factor_init(fac);

    /* f = 3 x (x^2 + 1)^2 (x + 1)^7 (x^3 + x + 1) */
    nmod_poly_set_str(f, "3 7  1 0 1");
    nmod_poly_pow(f, f, 2);
    nmod_poly_set_str(g, "2 7  1 1");
    nmod_poly_pow(g, g, 7);
    nmod_poly_mul(f, f, g);
    nmod_poly_set_str(g, "4 7  1 1 0 1");
    nmod_poly_mul(f, f, g);
    nmod_poly_shift_left(f, f, 1);
    nmod_poly_scalar_mul_nmod(f, f, 3);

    c = nmod_poly_factor(fac, f);
    flint_printf("leading coefficient %wu\n", c);
    nmod_poly_factor_print_pretty(fac, "x");

    nmod_poly_factor_squarefree(fac, f);
    flint_printf("squarefree:\n");
    nmod_poly_factor_print_pretty(fac, "x");

    nmod_poly_clear(f);
    nmod_poly_clear(g);
    nmod_poly_factor_clear(fac);
    return 0;
}

leading coefficient 3
x ^ 1
x^3+x+1 ^ 1
x^2+1 ^ 2
x+1 ^ 7
squarefree:
x^4+x^2+x ^ 1
x^2+1 ^ 2
x+1 ^ 7

The factor $(x + 1)^7$ has a multiplicity divisible by $p = 7$; the squarefree factorisation finds it by taking a $p$-th root.

By Theorem 1 of Factoring polynomials over finite fields, $x^{3^6} - x$ is the product of all monic irreducible polynomials over $\mathbb{F}_3$ whose degree divides 6. Factoring it and counting the factors by degree gives the numbers $I_d = \frac1d \sum_{e \mid d} \mu(d/e)\, 3^e$ of monic irreducible polynomials of degree $d$; all three algorithms agree:

#include <flint/flint.h>
#include <flint/nmod_poly.h>
#include <flint/nmod_poly_factor.h>

static void count(const nmod_poly_factor_t fac)
{
    slong i, num[7] = {0};
    for (i = 0; i < fac->num; i++)
        num[nmod_poly_degree(fac->p + i)]++;
    flint_printf("%wd %wd %wd %wd %wd %wd\n",
        num[1], num[2], num[3], num[4], num[5], num[6]);
}

int main(void)
{
    nmod_poly_t f;
    nmod_poly_factor_t fac;

    nmod_poly_init(f, 3);
    nmod_poly_factor_init(fac);

    nmod_poly_set_coeff_ui(f, 729, 1);
    nmod_poly_set_coeff_ui(f, 1, 2);       /* x^729 - x */

    nmod_poly_factor(fac, f);
    count(fac);
    nmod_poly_factor_with_cantor_zassenhaus(fac, f);
    count(fac);
    nmod_poly_factor_with_berlekamp(fac, f);
    count(fac);

    nmod_poly_clear(f);
    nmod_poly_factor_clear(fac);
    return 0;
}

3 3 8 0 0 116
3 3 8 0 0 116
3 3 8 0 0 116