fmpz_mod_poly_factor_init fac ctx

Initialises fac for use.

fmpz_mod_poly_factor_clear fac ctx

Frees all memory associated with fac.

fmpz_mod_poly_factor_realloc fac alloc ctx

Reallocates the factor structure to provide space for precisely alloc factors.

fmpz_mod_poly_factor_fit_length fac len ctx

Ensures that the factor structure has space for at least len factors. This function takes care of the case of repeated calls by always at least doubling the number of factors the structure can hold.

fmpz_mod_poly_factor_set res fac ctx

Sets res to the same factorisation as fac.

fmpz_mod_poly_factor_print fac ctx

Prints the entries of fac to standard output.

fmpz_mod_poly_factor_print_pretty fac var ctx

Prints the entries of fac to standard output.

fmpz_mod_poly_factor_insert fac poly exp ctx

Inserts the factor poly with multiplicity exp into the factorisation fac.

If fac already contains poly, then exp simply gets added to the exponent of the existing entry.

fmpz_mod_poly_factor_concat res fac ctx

Concatenates two factorisations.

This is equivalent to calling fmpz_mod_poly_factor_insert repeatedly with the individual factors of fac.

Does not support aliasing between res and fac.

fmpz_mod_poly_factor_pow fac exp ctx

Raises fac to the power exp.

fmpz_mod_poly_is_irreducible f ctx

Returns 1 if the polynomial f is irreducible, otherwise returns 0.

fmpz_mod_poly_is_irreducible_ddf f ctx

Returns 1 if the polynomial f is irreducible, otherwise returns 0. Uses fast distinct-degree factorisation.

fmpz_mod_poly_is_irreducible_rabin f ctx

Returns 1 if the polynomial f is irreducible, otherwise returns 0. Uses Rabin irreducibility test.

fmpz_mod_poly_is_irreducible_rabin_f r f ctx

Either sets \(r\) to \(1\) and returns 1 if the polynomial f is irreducible or \(0\) otherwise, or sets \(r\) to a nontrivial factor of \(p\).

This algorithm correctly determines whether \(f\) is irreducible over \(\mathbb{Z}/p\mathbb{Z}\), even for composite \(f\), or it finds a factor of \(p\).

_fmpz_mod_poly_is_squarefree f len ctx

Returns 1 if (f, len) is squarefree, and 0 otherwise. As a special case, the zero polynomial is not considered squarefree. There are no restrictions on the length.

_fmpz_mod_poly_is_squarefree_f fac f len ctx

If \(fac\) returns with the value \(1\) then the function operates as per _fmpz_mod_poly_is_squarefree, otherwise \(f\) is set to a nontrivial factor of \(p\).

fmpz_mod_poly_is_squarefree f ctx

Returns 1 if f is squarefree, and 0 otherwise. As a special case, the zero polynomial is not considered squarefree.

fmpz_mod_poly_is_squarefree_f fac f ctx

If \(fac\) returns with the value \(1\) then the function operates as per fmpz_mod_poly_is_squarefree, otherwise \(f\) is set to a nontrivial factor of \(p\).

fmpz_mod_poly_factor_equal_deg_prob factor state pol d ctx

Probabilistic equal degree factorisation of pol into irreducible factors of degree d. If it passes, a factor is placed in factor and 1 is returned, otherwise 0 is returned and the value of factor is undetermined.

Requires that pol be monic, non-constant and squarefree.

fmpz_mod_poly_factor_equal_deg factors pol d ctx

Assuming pol is a product of irreducible factors all of degree d, finds all those factors and places them in factors. Requires that pol be monic, non-constant and squarefree.

fmpz_mod_poly_factor_distinct_deg res poly degs ctx

Factorises a monic non-constant squarefree polynomial poly of degree \(n\) into factors \(f[d]\) such that for \(1 \leq d \leq n\) \(f[d]\) is the product of the monic irreducible factors of poly of degree \(d\). Factors \(f[d]\) are stored in res, and the degree \(d\) of the irreducible factors is stored in degs in the same order as the factors.

Requires that degs has enough space for \((n/2)+1 * sizeof(slong)\).

fmpz_mod_poly_factor_distinct_deg_threaded res poly degs ctx

Multithreaded version of fmpz_mod_poly_factor_distinct_deg.

fmpz_mod_poly_factor_squarefree res f ctx

Sets res to a squarefree factorization of f.

fmpz_mod_poly_factor res f ctx

Factorises a non-constant polynomial f into monic irreducible factors choosing the best algorithm for given modulo and degree. Choice is based on heuristic measurements.

fmpz_mod_poly_factor_cantor_zassenhaus res f ctx

Factorises a non-constant polynomial f into monic irreducible factors using the Cantor-Zassenhaus algorithm.

fmpz_mod_poly_factor_kaltofen_shoup res poly ctx

Factorises a non-constant polynomial poly into monic irreducible factors using the fast version of Cantor-Zassenhaus algorithm proposed by Kaltofen and Shoup (1998). More precisely this algorithm uses a baby step/giant step strategy for the distinct-degree factorization step. If flint_get_num_threads is greater than one fmpz_mod_poly_factor_distinct_deg_threaded is used.

fmpz_mod_poly_factor_berlekamp factors f ctx

Factorises a non-constant polynomial f into monic irreducible factors using the Berlekamp algorithm.

fmpz_mod_poly_roots r f with_multiplicity ctx

Fill \(r\) with factors of the form \(x - r_i\) where the \(r_i\) are the distinct roots of a nonzero \(f\) in \(Z/pZ\). It is expected and not checked that the modulus of \(ctx\) is prime. If \(with\_multiplicity\) is zero, the exponent \(e_i\) of the factor \(x - r_i\) is \(1\). Otherwise, it is the largest \(e_i\) such that \((x-r_i)^e_i\) divides \(f\). This function throws if \(f\) is zero, but is otherwise always successful.

fmpz_mod_poly_roots_factored r f with_multiplicity n ctx

Fill \(r\) with factors of the form \(x - r_i\) where the \(r_i\) are the distinct roots of a nonzero \(f\) in \(Z/nZ\). It is expected and not checked that \(n\) is a prime factorization of the modulus of \(ctx\). If \(with\_multiplicity\) is zero, the exponent \(e_i\) of the factor \(x - r_i\) is \(1\). Otherwise, it is the largest \(e_i\) such that \((x-r_i)^e_i\) divides \(f\). The roots are first found modulo the primes in \(n\), then lifted to the corresponding prime powers, then combined into roots of the original polynomial \(f\). A return of \(1\) indicates the function was successful. A return of \(0\) indicates the function was not able to find the roots, possibly because there are too many of them. This function throws if \(f\) is zero.