fmpz_mod_poly_factor.h

Initialises fac as the empty factorisation, without allocating memory.

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 as empty. 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.

Set the output to the factor of index i, 0 \le i < \mathit{num}. The exponent is exp[i]. fmpz_mod_poly_factor_get_fmpz_mod_poly is an older name, with a non-const factorisation argument.

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 fmpz_mod_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, in the formats of fmpz_mod_poly_print and of fmpz_mod_poly_print_pretty with the variable name var.

Sets res to the factorisation of f into monic irreducible polynomials, with multiplicities. The leading coefficient of f is not returned. A constant f gives the empty factorisation.

Like fmpz_mod_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). The output is overwritten.

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. This is gr_poly_factor_squarefree; see Squarefree 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. This is gr_poly_factor_equal_deg; see Equal-degree factorisation. An exception is raised if d does not divide the degree.

Returns whether f is irreducible over \mathbb{F}_p. As a special case, constant polynomials, including zero, are considered irreducible. This is gr_poly_is_irreducible, which uses the distinct-degree test for degree below 600 and a filter for small factors followed by Rabin's test for larger degrees; see Irreducibility testing over finite fields.

Return whether f is irreducible, using the distinct-degree test (gr_poly_is_irreducible_ddf) or Rabin's test with the Frobenius powers computed by modular composition (gr_poly_is_irreducible_rabin). Constants are considered irreducible.

Rabin's irreducibility test for a possibly composite modulus n: either sets fac to 1 and returns whether f is irreducible (when n is prime), or sets fac to a nontrivial factor of n, met as a non-invertible leading coefficient, and returns an unspecified value.

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 (gr_poly_is_squarefree). Nonzero constants are squarefree; as a special case, the zero polynomial is not.

Squarefreeness test for a possibly composite modulus n: either sets fac to 1 and returns whether f is squarefree, or sets fac to a nontrivial factor of n and returns 0.

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. This is gr_poly_roots_finite_field; see Roots of polynomials over finite fields.

Set the output to the linear factors x - a for the distinct roots a \in \mathbb{Z}/n\mathbb{Z} of the nonzero polynomial f, where the fmpz_factor_t holds the prime factorisation of the modulus n (not checked). If the multiplicity flag 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. Return 1 on success and 0 if the roots were not computed because there are too many of them. A zero f causes an exception.