Data.Number.Flint.Fmpz.Mod.Poly.Factor

Factorisation of polynomials over integers mod n

data FmpzModPolyFactor

Constructors

FmpzModPolyFactor !(ForeignPtr CFmpzModPolyFactor)

data CFmpzModPolyFactor

Constructors

CFmpzModPolyFactor (Ptr CFmpzModPoly) (Ptr CLong) CLong CLong

Instances

Storable CFmpzModPolyFactor

Defined in Data.Number.Flint.Fmpz.Mod.Poly.Factor.FFI

Methods

sizeOf :: CFmpzModPolyFactor -> Int

alignment :: CFmpzModPolyFactor -> Int

peekElemOff :: Ptr CFmpzModPolyFactor -> Int -> IO CFmpzModPolyFactor

pokeElemOff :: Ptr CFmpzModPolyFactor -> Int -> CFmpzModPolyFactor -> IO ()

peekByteOff :: Ptr b -> Int -> IO CFmpzModPolyFactor

pokeByteOff :: Ptr b -> Int -> CFmpzModPolyFactor -> IO ()

peek :: Ptr CFmpzModPolyFactor -> IO CFmpzModPolyFactor

poke :: Ptr CFmpzModPolyFactor -> CFmpzModPolyFactor -> IO ()

newFmpzModPolyFactor :: FmpzModCtx -> IO FmpzModPolyFactor

withFmpzModPolyFactor :: FmpzModPolyFactor -> (Ptr CFmpzModPolyFactor -> IO a) -> IO (FmpzModPolyFactor, a)

Factorisation

fmpz_mod_poly_factor_init :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_init fac ctx

Initialises fac for use.

fmpz_mod_poly_factor_clear :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_clear fac ctx

Frees all memory associated with fac.

fmpz_mod_poly_factor_realloc :: Ptr CFmpzModPolyFactor -> CLong -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> CLong -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPolyFactor -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_set res fac ctx

Sets res to the same factorisation as fac.

fmpz_mod_poly_factor_print :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_print fac ctx

Prints the entries of fac to standard output.

fmpz_mod_poly_factor_print_pretty :: Ptr CFmpzModPolyFactor -> CString -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_print_pretty fac var ctx

Prints the entries of fac to standard output.

fmpz_mod_poly_factor_insert :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> CLong -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPolyFactor -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> CLong -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_pow fac exp ctx

Raises fac to the power exp.

fmpz_mod_poly_is_irreducible :: Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO CInt

fmpz_mod_poly_is_irreducible f ctx

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

fmpz_mod_poly_is_irreducible_ddf :: Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO CInt

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 :: Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO CInt

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 :: Ptr CFmpz -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO CInt

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 :: Ptr CFmpz -> CLong -> Ptr CFmpzModCtx -> IO CInt

_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 :: Ptr CFmpz -> Ptr CFmpz -> CLong -> Ptr CFmpzModCtx -> IO CInt

_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 :: Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO CInt

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 :: Ptr CFmpz -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO CInt

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 :: Ptr CFmpzModPoly -> Ptr CFRandState -> Ptr CFmpzModPoly -> CLong -> Ptr CFmpzModCtx -> IO CInt

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> CLong -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> Ptr (Ptr CLong) -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> Ptr (Ptr CLong) -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_squarefree res f ctx

Sets res to a squarefree factorization of f.

fmpz_mod_poly_factor :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> Ptr CFmpzModCtx -> IO ()

fmpz_mod_poly_factor_berlekamp factors f ctx

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

Root Finding

fmpz_mod_poly_roots :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> CInt -> Ptr CFmpzModCtx -> IO ()

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 :: Ptr CFmpzModPolyFactor -> Ptr CFmpzModPoly -> CInt -> Ptr CFmpzFactor -> Ptr CFmpzModCtx -> IO CInt

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.