Algebra.Ring.Polynomial.Factorise

Factorisation

factorise :: (MonadRandom m, CoeffRing k, FiniteField k) => Unipol k -> m [(Unipol k, Natural)]

Factorise a polynomial over finite field using Cantor-Zassenhaus algorithm

factorQBigPrime :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer)))

Factorise the given integer-coefficient polynomial, choosing a large enough prime.

factorHensel :: MonadRandom m => Unipol Integer -> m (Integer, IntMap (Set (Unipol Integer)))

Factorise the given interger-coefficient polynomial by Hensel lifting.

Internal helper functions

distinctDegFactor

Arguments

:: (Eq k, FiniteField k)

=> Unipol k

Square-free polynomial over finite field.

-> [(Natural, Unipol k)]

Distinct-degree decomposition.

distinctDegFactor f computes the distinct-degree decomposition of the given square-free polynomial over finite field f.

equalDegreeSplitM :: forall k m. (MonadRandom m, CoeffRing k, FiniteField k) => Unipol k -> Natural -> m (Maybe (Unipol k))

equalDegreeFactorM :: (Eq k, FiniteField k, MonadRandom m) => Unipol k -> Natural -> m [Unipol k]

henselStep

Arguments

:: (Eq r, Euclidean r)

=> r

modulus

-> Unipol r

-> Unipol r

-> Unipol r

-> Unipol r

-> Unipol r

-> (Unipol r, Unipol r, Unipol r, Unipol r)

Given that f = gh (mod m) with sg + th = 1 (mod m) and leadingCoeff f isn't zero divisor mod m, henselStep m f g h s t calculates the unique (g', h', s', t') s.t. f = g' h' (mod m^2), g' = g (mod m), h' = h (mod m), s' = s (mod m), t' = t (mod m), h' monic.

clearDenom :: (CoeffRing a, Euclidean a) => Unipol (Fraction a) -> (a, Unipol a)

squareFreePart :: (Eq k, FiniteField k) => Unipol k -> Unipol k

squareFreeDecomp :: (Eq k, Characteristic k, Field k) => Unipol k -> IntMap (Unipol k)