Data.Number.Flint.Fq.NMod.Poly.Factor

Factorisation of univariate polynomials over finite fields

data FqNModPolyFactor

Constructors

FqNModPolyFactor !(ForeignPtr CFqNModPolyFactor)

data CFqNModPolyFactor

Constructors

CFqNModPolyFactor (Ptr CFqNModPoly) (Ptr CLong) CLong CLong

Instances

Storable CFqNModPolyFactor

Defined in Data.Number.Flint.Fq.NMod.Poly.Factor.FFI

Methods

sizeOf :: CFqNModPolyFactor -> Int

alignment :: CFqNModPolyFactor -> Int

peekElemOff :: Ptr CFqNModPolyFactor -> Int -> IO CFqNModPolyFactor

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

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

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

peek :: Ptr CFqNModPolyFactor -> IO CFqNModPolyFactor

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

newFqNModPolyFactor :: FqNModCtx -> IO FqNModPolyFactor

withFqNModPolyFactor :: FqNModPolyFactor -> (Ptr CFqNModPolyFactor -> IO a) -> IO (FqNModPolyFactor, a)

Memory Management

fq_nmod_poly_factor_init :: Ptr CFqNModPolyFactor -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_init fac ctx

Initialises fac for use. An fq_nmod_poly_factor_t represents a polynomial in factorised form as a product of polynomials with associated exponents.

fq_nmod_poly_factor_clear :: Ptr CFqNModPolyFactor -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_clear fac ctx

Frees all memory associated with fac.

fq_nmod_poly_factor_realloc :: Ptr CFqNModPolyFactor -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_realloc fac alloc ctx

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

fq_nmod_poly_factor_fit_length :: Ptr CFqNModPolyFactor -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_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.

Basic Operations

fq_nmod_poly_factor_set :: Ptr CFqNModPolyFactor -> Ptr CFqNModPolyFactor -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_set res fac ctx

Sets res to the same factorisation as fac.

fq_nmod_poly_factor_print_pretty :: Ptr CFqNModPolyFactor -> CString -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_print_pretty fac ctx

Pretty-prints the entries of fac to standard output.

fq_nmod_poly_factor_print :: Ptr CFqNModPolyFactor -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_print fac ctx

Prints the entries of fac to standard output.

fq_nmod_poly_factor_insert :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_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.

fq_nmod_poly_factor_concat :: Ptr CFqNModPolyFactor -> Ptr CFqNModPolyFactor -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_concat res fac ctx

Concatenates two factorisations.

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

Does not support aliasing between res and fac.

fq_nmod_poly_factor_pow :: Ptr CFqNModPolyFactor -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_pow fac exp ctx

Raises fac to the power exp.

fq_nmod_poly_remove :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CULong

fq_nmod_poly_remove f p ctx

Removes the highest possible power of p from f and returns the exponent.

Irreducibility Testing

fq_nmod_poly_is_irreducible :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_is_irreducible f ctx

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

fq_nmod_poly_is_irreducible_ddf :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_is_irreducible_ddf f ctx

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

fq_nmod_poly_is_irreducible_ben_or :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_poly_is_irreducible_ben_or f ctx

Returns 1 if the polynomial f is irreducible, otherwise returns 0. Uses Ben-Or's irreducibility test.

_fq_nmod_poly_is_squarefree :: Ptr (Ptr CFqNMod) -> CLong -> Ptr CFqNModCtx -> IO CInt

_fq_nmod_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.

fq_nmod_poly_is_squarefree :: Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO CInt

fq_nmod_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.

Factorisation

fq_nmod_poly_factor_equal_deg_prob :: Ptr CFqNModPoly -> Ptr CFRandState -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO CInt

fq_nmod_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.

fq_nmod_poly_factor_equal_deg :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> CLong -> Ptr CFqNModCtx -> IO ()

fq_nmod_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.

fq_nmod_poly_factor_split_single :: Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_split_single linfactor input ctx

Assuming input is a product of factors all of degree 1, finds a single linear factor of input and places it in linfactor. Requires that input be monic and non-constant.

fq_nmod_poly_factor_distinct_deg :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> Ptr (Ptr CLong) -> Ptr CFqNModCtx -> IO ()

fq_nmod_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 are stored in res, associated powers of irreducible polynomials are stored in degs in the same order as factors.

Requires that degs have enough space for irreducible polynomials' powers (maximum space required is \(n * sizeof(slong)\)).

fq_nmod_poly_factor_squarefree :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_squarefree res f ctx

Sets res to a squarefree factorization of f.

fq_nmod_poly_factor :: Ptr CFqNModPolyFactor -> Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor res lead f ctx

Factorises a non-constant polynomial f into monic irreducible factors choosing the best algorithm for given modulo and degree. The output lead is set to the leading coefficient of \(f\) upon return. Choice of algorithm is based on heuristic measurements.

fq_nmod_poly_factor_cantor_zassenhaus :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_cantor_zassenhaus res f ctx

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

fq_nmod_poly_factor_kaltofen_shoup :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_kaltofen_shoup res poly ctx

Factorises a non-constant polynomial f 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.

fq_nmod_poly_factor_berlekamp :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_berlekamp factors f ctx

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

fq_nmod_poly_factor_with_berlekamp :: Ptr CFqNModPolyFactor -> Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_with_berlekamp res leading_coeff f ctx

Factorises a general polynomial f into monic irreducible factors and sets leading_coeff to the leading coefficient of f, or 0 if f is the zero polynomial.

This function first checks for small special cases, deflates f if it is of the form \(p(x^m)\) for some \(m > 1\), then performs a square-free factorisation, and finally runs Berlekamp on all the individual square-free factors.

fq_nmod_poly_factor_with_cantor_zassenhaus :: Ptr CFqNModPolyFactor -> Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_with_cantor_zassenhaus res leading_coeff f ctx

Factorises a general polynomial f into monic irreducible factors and sets leading_coeff to the leading coefficient of f, or 0 if f is the zero polynomial.

This function first checks for small special cases, deflates f if it is of the form \(p(x^m)\) for some \(m > 1\), then performs a square-free factorisation, and finally runs Cantor-Zassenhaus on all the individual square-free factors.

fq_nmod_poly_factor_with_kaltofen_shoup :: Ptr CFqNModPolyFactor -> Ptr CFqNMod -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_factor_with_kaltofen_shoup res leading_coeff f ctx

Factorises a general polynomial f into monic irreducible factors and sets leading_coeff to the leading coefficient of f, or 0 if f is the zero polynomial.

This function first checks for small special cases, deflates f if it is of the form \(p(x^m)\) for some \(m > 1\), then performs a square-free factorisation, and finally runs Kaltofen-Shoup on all the individual square-free factors.

fq_nmod_poly_iterated_frobenius_preinv :: Ptr (Ptr CFqNModPoly) -> CLong -> Ptr CFqNModPoly -> Ptr CFqNModPoly -> Ptr CFqNModCtx -> IO ()

fq_nmod_poly_iterated_frobenius_preinv rop n v vinv ctx

Sets rop[i] to be \(x^{q^i} \bmod v\) for \(0 \le i < n\).

It is required that vinv is the inverse of the reverse of v mod x^lenv.

Root Finding

fq_nmod_poly_roots :: Ptr CFqNModPolyFactor -> Ptr CFqNModPoly -> CInt -> Ptr CFqNModCtx -> IO ()

fq_nmod_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 \(F_q\). 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.