fq_zech_poly_factor.h

Initialises fac as an empty factorisation, with room for 5 factors.

Frees the memory used by fac.

fq_zech_poly_factor_realloc changes the allocation to alloc factors (clearing factors beyond it; alloc = 0 reinitialises fac). fq_zech_poly_factor_fit_length ensures room for len factors, at least doubling the allocation when it grows.

Sets res to a copy of fac.

Multiplies the factorisation by poly^exp: if poly is already one of the factors, exp is added to its exponent, otherwise poly is appended with exponent exp. Constant polynomials are ignored.

Inserts all factors of fac into res with fq_zech_poly_factor_insert.

Multiplies all exponents by exp, raising the factored polynomial to the power exp.

Sets z to the factor of index $i$, $0 \le i < \mathit{num}$.

Print the factors to stdout, one per line, each followed by ^ and its exponent, in the format of fq_zech_poly_print, respectively of fq_zech_poly_print_pretty with the variable name var.

Return whether $f$ is squarefree, that is, not divisible by the square of a polynomial of positive degree. Polynomials of length at most 2 other than 0 are squarefree, and 0 is not. This is a wrapper of gr_poly_is_squarefree, which computes $\gcd(f, f')$ and handles $p$-th powers.

Sets res to a squarefree factorisation of $f$: pairwise coprime monic squarefree polynomials $g_i$ with distinct exponents $e_i$ such that $f = c \prod g_i^{e_i}$, where $c$ is the leading coefficient of $f$. Previous contents of res are discarded; for $f$ of length at most 1 the factorisation is empty.

Return whether $f$ is irreducible. Unlike gr_poly_is_irreducible, these functions return 1 for all polynomials of length at most 2, including constants and zero.

Factors input as $c \prod g_i^{e_i}$ with distinct monic irreducible $g_i$: sets result to the factors and exponents (discarding previous contents) and leading_coeff to $c$. For the zero polynomial $c = 0$ and the factorisation is empty; for a constant, $c$ is the constant.

As fq_zech_poly_factor, but factoring the squarefree parts with the Cantor–Zassenhaus algorithm (distinct-degree factorisation followed by equal-degree splitting), Berlekamp's algorithm (a basis of the kernel of the Frobenius map minus the identity, followed by random splitting), or the Kaltofen–Shoup algorithm (distinct-degree factorisation with baby-step giant-step Frobenius computations by modular composition).

As the _with_ functions, without returning the leading coefficient: the output is the factorisation of the monic polynomial $f / c$. Previous contents of the output are discarded.

Distinct-degree factorisation of the squarefree polynomial poly: appends to res, with exponent 1, polynomials $g_1, g_2, \ldots$ such that $\operatorname{monic}(\mathit{poly}) = \prod g_i$ and each $g_i$ is the product of all irreducible factors of degree $d_i$, and writes the degrees $d_i$ to (*degs)[0], (*degs)[1], .... The caller must provide room for $\deg(\mathit{poly})$ entries in *degs. The result is undefined if poly is not squarefree. This is a wrapper of gr_poly_factor_distinct_deg.

Equal-degree factorisation: appends to factors, with exponent 1, the irreducible factors of pol, which must be a monic squarefree product of irreducible polynomials of degree $d$. The factors are found by random splitting (Cantor–Zassenhaus), using an internal random state.

Sets linfactor to one monic linear factor $x - a$ of input, which must split into linear factors (not necessarily distinct). If input has degree 1 it is copied. Throws FLINT_ERROR if no root is found. This is the step used by fq_zech_embed_gens to find a root of a defining polynomial in an extension field.

Sets rop[i] to $x^{q^i} \bmod v$ for $0 \le i < n$, where vinv is the inverse of the reversal of $v$ (see fq_zech_poly_reverse and fq_zech_poly_inv_series). The array rop must contain $n$ initialised polynomials. If FQ_ZECH_POLY_ITERATED_FROBENIUS_CUTOFF returns 1, the powers after the first are computed by modular composition with a precomputed Brent–Kung matrix ($x^{q^{i}} = x^{q^{i-1}}(x^q)$), otherwise by exponentiation.

Returns 1 if fq_zech_poly_iterated_frobenius_preinv should use modular composition for a modulus of length length, which is the case if $2 \log_2 q < 3(\lfloor \sqrt{\mathit{length}} \rfloor + 1)$.

Sets r to the roots of the nonzero polynomial $f$ in $\mathbb{F}_q$, stored as the monic linear factors $x - a$. If with_multiplicity is nonzero, the exponents are the multiplicities of the roots; otherwise they are 1. Previous contents of r are discarded. This is a wrapper of gr_poly_roots_finite_field, which splits $\gcd(f, x^q - x)$ by equal-degree factorisation; see Roots of polynomials over finite fields.