Safe Haskell | Safe-Inferred |
---|---|
Language | Haskell2010 |
Synopsis
- data FmpzPolyFactor = FmpzPolyFactor !(ForeignPtr CFmpzPolyFactor)
- data CFmpzPolyFactor = CFmpzPolyFactor (Ptr CFmpz) (Ptr CFmpzPoly) (Ptr CLong) CLong CLong
- newFmpzPolyFactor :: IO FmpzPolyFactor
- withFmpzPolyFactor :: FmpzPolyFactor -> (Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a)
- fmpz_poly_factor_init :: Ptr CFmpzPolyFactor -> IO ()
- fmpz_poly_factor_init2 :: Ptr CFmpzPolyFactor -> CLong -> IO ()
- fmpz_poly_factor_realloc :: Ptr CFmpzPolyFactor -> CLong -> IO ()
- fmpz_poly_factor_fit_length :: Ptr CFmpzPolyFactor -> CLong -> IO ()
- fmpz_poly_factor_clear :: Ptr CFmpzPolyFactor -> IO ()
- fmpz_poly_factor_set :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> IO ()
- fmpz_poly_factor_insert :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> CLong -> IO ()
- fmpz_poly_factor_concat :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> IO ()
- fmpz_poly_factor_print :: Ptr CFmpzPolyFactor -> IO ()
- fmpz_poly_factor_squarefree :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO ()
- fmpz_poly_factor_zassenhaus_recombination :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> Ptr CFmpz -> CLong -> IO ()
- _fmpz_poly_factor_zassenhaus :: Ptr CFmpzPolyFactor -> CLong -> Ptr CFmpzPoly -> CLong -> CInt -> IO ()
- fmpz_poly_factor_zassenhaus :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO ()
- _fmpz_poly_factor_quadratic :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> CLong -> IO ()
- fmpz_poly_factor :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO ()
Factorisation of polynomials over the integers
data CFmpzPolyFactor Source #
Instances
Storable CFmpzPolyFactor Source # | |
Defined in Data.Number.Flint.Fmpz.Poly.Factor.FFI sizeOf :: CFmpzPolyFactor -> Int # alignment :: CFmpzPolyFactor -> Int # peekElemOff :: Ptr CFmpzPolyFactor -> Int -> IO CFmpzPolyFactor # pokeElemOff :: Ptr CFmpzPolyFactor -> Int -> CFmpzPolyFactor -> IO () # peekByteOff :: Ptr b -> Int -> IO CFmpzPolyFactor # pokeByteOff :: Ptr b -> Int -> CFmpzPolyFactor -> IO () # peek :: Ptr CFmpzPolyFactor -> IO CFmpzPolyFactor # poke :: Ptr CFmpzPolyFactor -> CFmpzPolyFactor -> IO () # |
withFmpzPolyFactor :: FmpzPolyFactor -> (Ptr CFmpzPolyFactor -> IO a) -> IO (FmpzPolyFactor, a) Source #
Types, macros and constants
Memory management
fmpz_poly_factor_init :: Ptr CFmpzPolyFactor -> IO () Source #
fmpz_poly_factor_init fac
Initialises a new factor structure.
fmpz_poly_factor_init2 :: Ptr CFmpzPolyFactor -> CLong -> IO () Source #
fmpz_poly_factor_init2 fac alloc
Initialises a new factor structure, providing space for at least alloc
factors.
fmpz_poly_factor_realloc :: Ptr CFmpzPolyFactor -> CLong -> IO () Source #
fmpz_poly_factor_realloc fac alloc
Reallocates the factor structure to provide space for precisely alloc
factors.
fmpz_poly_factor_fit_length :: Ptr CFmpzPolyFactor -> CLong -> IO () Source #
fmpz_poly_factor_fit_length fac len
Ensures that the factor structure has space for at least len
factors.
This functions takes care of the case of repeated calls by always at
least doubling the number of factors the structure can hold.
fmpz_poly_factor_clear :: Ptr CFmpzPolyFactor -> IO () Source #
fmpz_poly_factor_clear fac
Releases all memory occupied by the factor structure.
Manipulating factors
fmpz_poly_factor_set :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> IO () Source #
fmpz_poly_factor_set res fac
Sets res
to the same factorisation as fac
.
fmpz_poly_factor_insert :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> CLong -> IO () Source #
fmpz_poly_factor_insert fac p e
Adds the primitive polynomial \(p^e\) to the factorisation fac
.
Assumes that \(\deg(p) \geq 2\) and \(e \neq 0\).
fmpz_poly_factor_concat :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> IO () Source #
fmpz_poly_factor_concat res fac
Concatenates two factorisations.
This is equivalent to calling fmpz_poly_factor_insert
repeatedly with
the individual factors of fac
.
Does not support aliasing between res
and fac
.
Input and output
fmpz_poly_factor_print :: Ptr CFmpzPolyFactor -> IO () Source #
fmpz_poly_factor_print fac
Prints the entries of fac
to standard output.
Factoring algorithms
fmpz_poly_factor_squarefree :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO () Source #
fmpz_poly_factor_squarefree fac F
Takes as input a polynomial \(F\) and a freshly initialized factor
structure fac
. Updates fac
to contain a factorization of \(F\) into
(not necessarily irreducible) factors that themselves have no repeated
factors. None of the returned factors will have the same exponent. That
is we return \(g_i\) and unique \(e_i\) such that
\[F = c \prod_{i} g_i^{e_i}\]
where \(c\) is the signed content of \(F\) and \(\gcd(g_i, g_i') = 1\).
fmpz_poly_factor_zassenhaus_recombination :: Ptr CFmpzPolyFactor -> Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> Ptr CFmpz -> CLong -> IO () Source #
fmpz_poly_factor_zassenhaus_recombination final_fac lifted_fac F P exp
Takes as input a factor structure lifted_fac
containing a squarefree
factorization of the polynomial \(F \bmod p\). The algorithm does a
brute force search for irreducible factors of \(F\) over the integers,
and each factor is raised to the power exp
.
The impact of the algorithm is to augment a factorization of F^exp
to
the factor structure final_fac
.
_fmpz_poly_factor_zassenhaus :: Ptr CFmpzPolyFactor -> CLong -> Ptr CFmpzPoly -> CLong -> CInt -> IO () Source #
_fmpz_poly_factor_zassenhaus final_fac exp f cutoff use_van_hoeij
This is the internal wrapper of Zassenhaus.
It will attempt to find a small prime such that \(f\) modulo \(p\) has a
minimal number of factors. If it cannot find a prime giving less than
cutoff
factors it aborts. Then it decides a \(p\)-adic precision to
lift the factors to, hensel lifts, and finally calls Zassenhaus
recombination.
Assumes that \(\operatorname{len}(f) \geq 2\).
Assumes that \(f\) is primitive.
Assumes that the constant coefficient of \(f\) is non-zero. Note that this can be easily achieved by taking out factors of the form \(x^k\) before calling this routine.
If the final flag is set, the function will use the van Hoeij factorisation algorithm with gradual feeding and mod \(2^k\) data truncation to find factors when the number of local factors is large.
fmpz_poly_factor_zassenhaus :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO () Source #
fmpz_poly_factor_zassenhaus final_fac F
A wrapper of the Zassenhaus factoring algorithm, which takes as input
any polynomial \(F\), and stores a factorization in final_fac
.
The complexity will be exponential in the number of local factors we find for the components of a squarefree factorization of \(F\).
_fmpz_poly_factor_quadratic :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> CLong -> IO () Source #
_fmpz_poly_factor_quadratic fac f exp
Inserts the factorisation of the quadratic (resp. cubic) polynomial f into fac with multiplicity exp. This function requires that the content of f has been removed, and does not update the content of fac. The factorzation is calculated over \(\mathbb{R}\) or \(\mathbb{Q}_2\) and then tested over \(\mathbb{Z}\).
fmpz_poly_factor :: Ptr CFmpzPolyFactor -> Ptr CFmpzPoly -> IO () Source #
fmpz_poly_factor final_fac F
A wrapper of the Zassenhaus and van Hoeij factoring algorithms, which
takes as input any polynomial \(F\), and stores a factorization in
final_fac
.