nmod_poly_factor.h

Initialises fac as the empty factorisation ($\mathit{num} = 0$), with space for 5 factors.

Frees the memory used by fac, including all allocated polynomials.

Changes the space of fac to exactly alloc factors. For alloc = 0 the factorisation is cleared and reinitialised (with space for 5 factors and $\mathit{num} = 0$). If alloc is smaller than the number of factors, the factors beyond the first alloc are discarded.

Ensures that fac has space for at least len factors. If it has to grow, it grows to at least twice its previous allocation.

Swaps a and b efficiently.

Sets res to a copy of fac, including the moduli of the factors.

Sets a to the factor b->p[i], for $0 \le i < \mathit{num}$. The exponent is b->exp[i].

Multiplies the factorisation by $\mathit{poly}^{\mathit{exp}}$: if poly is equal to one of the factors, exp is added to its exponent, otherwise a copy of poly is appended with exponent exp. Constant polynomials are ignored. The search is linear in the number of factors.

Multiplies res by the factorisation fac, by inserting each factor of fac with nmod_poly_factor_insert. res and fac must be distinct objects.

Multiplies every exponent of fac by exp, which raises the factored polynomial to the power exp.

Print the factors to standard output, one per line, as the polynomial followed by ^ and the exponent. nmod_poly_factor_print writes the polynomials in the format of nmod_poly_print, and nmod_poly_factor_print_pretty in the format of nmod_poly_print_pretty with the variable name var.

Sets result to the factorisation of input into monic irreducible polynomials over $\mathbb{F}_p$ and returns the leading coefficient of input, so that input equals the leading coefficient times the product of the factors raised to their exponents. A constant input gives the empty factorisation and returns the constant (0 for the zero polynomial).

Like nmod_poly_factor, but split the squarefree factors with the Cantor–Zassenhaus algorithm, Berlekamp's algorithm or the Kaltofen–Shoup algorithm respectively. Deflation is still applied.

Append the factorisation of f into monic irreducible polynomials, with exponents, to res, using the Cantor–Zassenhaus algorithm, Berlekamp's algorithm or the Kaltofen–Shoup algorithm (with deflation, as in nmod_poly_factor). The leading coefficient of f is discarded; nothing is appended for a constant f.

Sets res to the squarefree factorisation of f: monic squarefree polynomials $g_i$, pairwise coprime and with distinct exponents $e_i$, such that $f = c \prod_i g_i^{e_i}$ with $c$ the leading coefficient of $f$. A constant f gives the empty factorisation.

Distinct-degree factorisation of a squarefree polynomial poly of degree at least 1, which need not be monic. Appends to res monic polynomials $f_1, \ldots, f_k$, each with exponent 1, such that $f_j$ is the product of all monic irreducible factors of poly of one degree $d_j$, and writes $d_j$ to (*degs)[j - 1]. The array *degs must have room for $\deg(\mathit{poly})$ entries; the $d_j$ are distinct but not sorted. If poly is not squarefree the output is meaningless.

Equal-degree factorisation: pol must be squarefree and a product of irreducible polynomials of degree $d$, and $d$ must divide $\deg(\mathit{pol})$. Appends the monic irreducible factors of pol, each with exponent 1, to factors.

Returns whether f is irreducible over $\mathbb{F}_p$. As a special case, constant polynomials, including zero, are considered irreducible (unlike gr_poly_is_irreducible, which returns false for them).

Returns whether f is irreducible, by the coarse phase of the baby-step giant-step distinct-degree factorisation: after a squarefreeness test, $f$ is irreducible if and only if it has no factor of degree at most $\deg(f)/2$. Constants are considered irreducible. This is gr_poly_is_irreducible_ddf; it stops at the first interval of degrees that contains a factor.

Returns whether f is irreducible, by Rabin's test [Rab1980b]: $f$ of degree $n$ is irreducible if and only if $x^{p^n} \equiv x \pmod f$ and $\gcd(x^{p^{n/r}} - x, f) = 1$ for every prime $r \mid n$. Constants are considered irreducible.

Return whether f (given as (f, len) in the underscore version, with any $\mathit{len} \ge 0$) is squarefree, by testing whether $\gcd(f, f') = 1$; if $f' = 0$ and $\deg f \ge 2$, then $f$ is a $p$-th power and not squarefree. Nonzero constants are squarefree; as a special case, the zero polynomial is not.

Sets r to the linear factors $x - a$ for the distinct roots $a \in \mathbb{F}_p$ of the nonzero polynomial f. If with_multiplicity is nonzero, the exponent of $x - a$ is the multiplicity of $a$ as a root of f, otherwise it is 1. The modulus must be prime. A zero f causes an exception.

Sets r to the linear factors $x - a$ for the distinct roots $a \in \mathbb{Z}/n\mathbb{Z}$ of the nonzero polynomial f, where n holds the prime factorisation of the modulus $n$ of f (not checked). If with_multiplicity is nonzero, the exponent of $x - a$ is the largest $e$ such that $(x - a)^e$ divides $f$ in $(\mathbb{Z}/n\mathbb{Z})[x]$, otherwise it is

1. Returns 1 on success and 0 if the roots were not computed because there are too many of them (more than about $2^{32}$, or $2^{25}$ on 32-bit systems). A zero f causes an exception.